Some algorithmic aspects of subspace identificatio

Int.J.Appl.Math.Comput.Sci.,2001,Vol.11,No.1,55{7555SOMEALGORITHMICASPECTSOFSUBSPACEIDENTIFICATIONWITHINPUTSAlessandroCHIUSO,GiorgioPICCIIthasbeenexperimentallyveriedthatmostcommonlyusedsubspacemethodsforidenticationoflinearstate-spacesystemswithexogenousinputsmay,incertainexperimentalconditions,runintoill-conditioningandleadtoambiguousresults.Ananalysisofthecriticalsituationshasleadustoproposeanewal-gorithmicstructurewhichcouldbeusedeithertotestdicultcasesand/ortoimplementasuitablecombinationofnewandoldalgorithmspresentedintheliteraturetohelpxingtheproblem.Keywords:subspaceidentication,multivariablesystems,identicationwithinputs,ill-conditioning1.IntroductionItiswell-knownthatthe`classical'approachtosystemidenticationisbasedonparameteroptimization,i.e.,thesystemparametersareobtainedbyminimizationofasuitablecostfunction.Thesemethodshavebeenwidelyusedandshownasreasonablysuccessfulinmodellingsingle-inputsingle-outputsystemsbyARMAorARMAXmodels,seetheclassicaltextbook(Ljung,1987)foranup-to-dateillustrationofthisapproach.However,whenonehastoattackgeneralmulti-inputmulti-outputmodels,thesemethodssuerfromvariousdrawbacks.Since,unlessattentionisrestrictedtorathertrivialmodelclasses,thedependenceofthecostfunctionontheparametersisingen-eralnon-linear,iterativetechniquesarerequiredforminimization.Formultivariablesystemsthesemaywellturnouttobeverytime-consuming.Duetotheexistenceoflocalminimaandnon-convexity,theoutcomeisingeneralverysensitivetothechoiceoftheparameterizationandofthestartingpointintheoptimizationproce-dure.Thereisgenerallynoguaranteeofglobaloptimalitybutonlyofanendingclosetoalocalminimum.Furthermore,toattackgeneralmulti-inputmulti-outputmodelsbyparameteroptimizationmethods,choosingcanonicalparameterizationsisunavoid-able.Infact,theuseofcanonicalparameterizationshasbeenrecognizedasacriticalissueinMIMOidenticationsincetheearly1970's(Guidorzi,1981;Ober,1996),andrepresentsabottleneckinextendingfromSISOtoMIMOidentication.DipartimentodiElettronicaeInformatica,UniversitadiPadova,35131Padua,Italy,e-mail:chiuso,[e-mail],or`subspace',orrealization-basedmethodsrelyontheideasofstochasticrealizationtheorywhichhavebeendeveloped(mainlyfortimeseries)bymanyauthors,forinstance,Akaike(1974;1975),Faurre(1976),LindquistandPicci(1979;1991),Picci(1976),andRuckebusch(1976;1978).Roughlyspeaking,subspacemethodstranslatetheconstructionsofstochasticrealizationtheoryintoproceduresformodelbuildingwhichworkonmeasureddata(LindquistandPicci,1996a).Theyowethename`subspace'tothefactthatthebasicobjectswhichareconstructedinthealgorithmsaresubspacesgeneratedbythedata,andgeometricoperationssuchasorthogonalandobliqueprojectionsareallwhatisneededtocomputeestimatesoftheparameters.Theappealingfeaturesofsubspacemethodsarethatthereisnoneedforcanonicalparameterizations;noiterativenonlinearoptimizationisrequired;onlysimpleandnumericallyrobusttoolsofnumericallinearalgebrasuchasQR,SVD,QSVDareused;nally,sincethemethodsrelyonthetheoreticalbackgroundofstochasticrealizationtheory,adeepersystem-theoreticunderstandingoftheinvolvedproceduresispossible.ThebasicsofsubspacemethodsmayprobablybetracedbacktotheoldworksofHotelling(1936),HoandKalman(1966),Akaike(1974;1975),Faurre(1976),Aoki(1990),andMoonenetal.(1989),butprobablytherst`true'subspacealgorithmisthe`stochastic'algorithmofvanOverscheeandDeMoor(1993)fortheidenticationoftimeseries.Varioussubspacealgorithmshavebeenintroducedforidenticationofsystemswithexogenousinputs,someofthebasicreferencesbeing(MoonenandVandewalle,1990;Moonenetal.,1989;VanOverscheeandDeMoor,1994;1996;Verhaegen,1994;VerhaegenandDewilde,1992;Viberg,1995).Eventhoughthesemethodshavebeenaroundforawhile,itisfairtosaythatforsubspacemethodswithinputsthereisstillanumberofquestionswhicharenotcompletelyunderstood.1.Oneofthesequestonsisnumericalill-conditioning,whichhasbeenexperimen-tallyveriedinanumberofsituations(ChiusoandPicci,1999;Kawauchietal.,1999).Oneshouldunderstandwhenill-conditioningmayoccurandhowtoset-tletheproblem.Recently,in(ChiusoandPicci,2000c)ithasbeenarguedthatusingorthogonaldecompositionandblock-parameterizedmodels,togetherwiththeorthogonaldecompositionalgorithmof(ChiusoandPicci,1999;PicciandKatayama,1996a),maybeapossiblesolutiontotheproblemofill-conditioning.SimulationresultsandcomparisonwiththeN4SIDalgorithmarediscussedin(ChiusoandPicci,1999;2000b;2000c).2.Asiswell-known,thedynamicsoftheinputsignaliscrucialfortheoutcomeofanidenticationexperiment.Itisimportanttohaveboundsontheperformanceofanalgorithmasa`function'oftheinputcharacteristic(bandwith,persistenceofexcitation,etc.).Inparticular,forcomparingresultsofsimulations,aspeci-cationof`probinginputs'forthevalidationofidenticationalgorithms(ChiusoandPicci,2000b)isneeded.Bythe`probinginputs'wemeantheinputswhicharetailoredtorevealthemainlimitationsofthealgorithms.3.Subspaceidenticationinthepresenceoffeedbackhasbeenaddressedbysomeauthors(ChouT.andVerhaegen,1997;Verhaegen,1993),buttheproblemseemstobeveryfarfrombeingcompletely