TENSORRANKANDTHEILL-POSEDNESSOFTHEBEST

arXiv:math/0607647v2[math.NA]1Apr2008TENSORRANKANDTHEILL-POSEDNESSOFTHEBESTLOW-RANKAPPROXIMATIONPROBLEMVINDESILVA∗ANDLEK-HENGLIM†Abstract.Therehasbeencontinuedinterestinseekingatheoremdescribingoptimallow-rankapproximationstotensorsoforder3orhigher,thatparallelstheEckart–Youngtheoremformatrices.Inthispaper,wearguethatthenaiveapproachtothisproblemisdoomedtofailurebecause,unlikematrices,tensorsoforder3orhighercanfailtohavebestrank-rapproximations.Thephenomenonismuchmorewidespreadthanonemightsuspect:examplesofthisfailurecanbeconstructedoverawiderangeofdimensions,ordersandranks,regardlessofthechoiceofnorm(orevenBr`egmandivergence).Moreover,weshowthatinmanyinstancesthesecounterexampleshavepositivevolume:theycannotberegardedasisolatedphenomena.Inoneextremecase,weexhibitatensorspaceinwhichnorank-3tensorhasanoptimalrank-2approximation.Thenotableexceptionstothismisbehaviorarerank-1tensorsandorder-2tensors(i.e.matrices).Inamorepositivespirit,weproposeanaturalwayofovercomingtheill-posednessofthelow-rankapproximationproblem,byusingweaksolutionswhentruesolutionsdonotexist.Forthistowork,itisnecessarytocharacterizethesetofweaksolutions,andwedothisinthecaseofrank2,order3(inarbitrarydimensions).Inourworkweemphasizetheimportanceofcloselystudyingconcretelow-dimensionalexamplesasafirststeptowardsmoregeneralresults.Tothisend,wepresentadetailedanalysisofequivalenceclassesof2×2×2tensors,andwedevelopmethodsforextendingresultsupwardstohigherordersanddimensions.Finally,welinkourworktoexistingstudiesoftensorsfromanalgebraicgeometricpointofview.Therankofatensorcanintheorybegivenasemialgebraicdescription;inotherwords,canbedeterminedbyasystemofpolynomialinequalities.Westudysomeofthesepolynomialsincasesofinteresttous;inparticularwemakeextensiveuseofthehyperdeterminantΔonR2×2×2.Keywords.numericalmultilinearalgebra,tensors,multidimensionalarrays,multiwayarrays,tensorrank,tensordecompositions,lowranktensorapproximations,hyperdeterminants,Eckart–Youngtheorem,principalcomponentanalysis,parafac,candecomp,Br`egmandivergenceoftensorsAMSsubjectclassifications.14P10,15A03,15A21,15A69,15A72,49M27,62H25,68P011.Introduction.Givenanorder-ktensorA∈Rd1×···×dk,oneisoftenrequiredtofindabestrank-rapproximationtoA—inotherwords,determinevectorsxi∈Rd1,yi∈Rd2,...,zi∈Rdk,i=1,...,r,thatminimizeskA−x1⊗y1⊗···⊗z1−···−xr⊗yr⊗···⊗zrkor,inshort,argminrank⊗(B)≤rkA−Bk.(approx(A,r))Herek·kdenotessomechoiceofnormonRd1×···×dk.Whenk=2,theproblemiscompletelyresolvedforunitarilyinvariantnormsonRm×nwiththeEckart–Youngtheorem[28],whichstatesthatifA=UΣV=Xrank(A)i=1σiui⊗vi,σi≥σi+1,isthesingularvaluedecompositionofA∈Rm×n,thenabestrank-rapproximationisgivenbythefirstrtermsintheabovesum[33].Thebestrank-rapproximation∗DepartmentofMathematics,PomonaCollege,Claremont,CA91711-4411.E-mail:[e-mail]†Correspondingauthor.InstituteforComputationalandMathematicalEngineering,StanfordUniversity,Stanford,CA94305-9025.E-mail:[e-mail]tensorsisaproblemofcentralimportanceinthestatisticalanalysisofmultiwaydata[11,16,20,21,45,50,38,56,65,66,74,75,76].Itisthereforenotsurprisingthattherehasbeencontinuedinterestinfindingasatisfactory‘singularvaluedecomposition’andan‘Eckart–Youngtheorem’-likeresultfortensorsofhigherorder.Theviewexpressedintheconclusionof[46]isrepresen-tativeofsucheffortsandwereproduceithere:“AnEckart–Youngtypeofbestrank-rapproximationtheoremfortensorscontinuestoeludeourinvestigationsbutcanperhapseventu-allybeattainedbyusingadifferentnormoryetotherdefinitionsoforthogonalityandrank.”Itwillperhapscomeasasurprisetothereaderthattheproblemoffindingan‘Eckart–Youngtypetheorem’isill-foundedbecauseofamorefundamentaldifficulty:thebestrank-rapproximationproblemapprox(A,r)hasnosolutioningeneral!Thispaperseekstoprovideananswertothisandseveralrelatedquestions.1.1.Summary.Sincethisisalongpaper,wepresentan‘executivesummary’ofselectedresults,inthissectionandthenext.Webeginwiththefivemainobjectivesofthisarticle:1.approx(A,r)isill-posedformanyr.Wewillshowthat,regardlessofthechoiceofnorm,theproblemofdeterminingabestrank-rapprox-imationforanorder-ktensorinRd1×···×dkhasnosolutioningeneralforr=2,...,min{d1,...,dk}andk≥3.Inotherwords,thebestlowrankapproximationproblemfortensorsisill-posedforallorders(higherthan2),allnorms,andmanyranks.2.approx(A,r)isill-posedformanyA.Wewillshowthatthesetoftensorsthatfailtohaveabestlowrankapproximationhaspositivevolume.Inotherwords,suchfailuresarenotrare—ifonerandomlypicksatensorAinasuitabletensorspace,thenthereisanon-zeroprobabilitythatAwillfailtohaveabestrank-rapproximationforsomerrank⊗(A).3.Weaksolutionstoapprox(A,r).Wewillproposeanaturalwaytoover-cometheill-posednessofthebestrank-rapproximationproblemwiththeintroductionof‘weaksolutions’,whichweexplicitlycharacterizeinthecaser=2,k=3.4.Semialgebraicdescriptionoftensorrank.FromtheTarski–Seidenbergtheoreminmodeltheory[71,64]wewilldeducethefollowing:foranyd1,...,dk,thereexistsafinitenumberofpolynomialfunctions,Δ1,...,Δm,definedonRd1×···×dksuchthattherankofanyA∈Rd1×···×dkiscomple