高阶对称复张量的逐次秩一分解.pdf 10页

'˖ڍመ੾᝶஠ڙጲhttp://www.paper.edu.cn高阶对称复张量的逐次秩一分解张仉辉，白敏茹湖南大学数学与计量经济学院,长沙　410082摘要：为了得到高阶对称复张量的标准分解，本文将矩阵中的逐次分解方法推广到张量情形，提出高阶对称复张量的逐次对称秩一复逼近方法。本文指出，对称实值张量在实数域和复数域上的逐次分解可能有所不同。并且，给出了一类张量，即酉对角化张量，可以利用逐次秩一分解来获得对称标准分解。数值部分分析了求解子问题的求解方法。数值结果验证了算法的有效性。关键词：运筹学与控制论，对称张量，复张量，秩一张量，分解SuccessiveRank-OneDecompositionofHigher-OrderSymmetricComplexTensorsZHANGZhang-Hui,BAIMin-RuCollegeofMathematicsandEconometrics,HunanUniversity,ChangSha410082Abstract:Inordertogetthesymmetriccanonicaldecompositionofthehigher-ordersymmetriccomplextensors,thispaperextendsthesuccessivedecompositionmethodtothetensorcase,andproposesasuccessivesymmetricrank-onecomplexapproximationmethodtodecomposethehigher-ordersymmetriccomplextensors.Itnotesthatthesuccessivedecompositionofrealtensorsmayactuallybedifferentovertherealfieldandthecomplexfield.Wefurthershowthatasymmetriccanonicaldecompositioncouldbeobtainedwhenthemethodisappliedtoaunitarydiagonalizabletensor.Numericalpartanalyzesthesolvingmethodofsolvingthesub-problem.Numericalresultsverifytheefficiencyoftheproposedmethod.Keywords:OperationalResearchandCybernetics,symmetrictensor,complextensor,rank-onetensor,decompositionFoundations:NationalNaturalScienceFoundationofChina(GrantNo.11571098),HunanProvincialNaturalScienceFoundationofChina(GrantNo.14JJ2053)andtheInnovationPlatformOpenFundsofHunanProvincialHigherEducationInstitutionsofChina(GrantNo.14K018).AuthorIntroduction:ZhangHuiZhang(1990-)，male，graduatestudent，majorresearchdirection：Tensoroptimiza-tionandapplication.Correspondenceauthor：MinRuBai（1968-），female，professor，majorresearchdirection：Tensoroptimizationandapplication，email:minru-bai@163.com.-1- ˖ڍመ੾᝶஠ڙጲhttp://www.paper.edu.cn0IntroductionAtensorisamultidimensionalarray.Moreformally,anm-wayormth-ordertensorisanelementofthetensorproductofmvectorspaces,eachofwhichhasitsowncoordinatesystem[1].Inrecentyears,interestintensordecompositionshasexpandedtolotsoffields,suchassig-nalprocessing,computervision,numericalanalysis,datamining,graphanalysis,neuroscienceandmore.Rank-onetensorshavemanyinterestingpropertiesandplayanimportantroleintensordecompositions[2].Byanalogytothematrixcase,thesuccessivesymmetricrank-oneapproximationmethodhasproposedforsymmetrictensordecompositionsintherealfield[3,4].Foranearlyor-thogonallydecomposablesymmetrictensor,itisprovedin[3]thateveninthepresenceofperturbation,itssuccessivesymmetricrank-oneapproximationcanstillrobustlyrecoverthesymmetriccanonicaldecomposition.In[4],basedoniterativelycomputingthebestsymmetricrank-oneapproximationoftheresidualtensors,agreedymethodisproposedtoobtainasucces-sivesymmetricrank-onedecomposition.However,manyimportantapplicationsarisewithinacomplexvariablesframework[5,6,7],suchasthegeometricmeasureofentanglementproblem.Inthispaper,weextendthesuccessivesymmetricrank-oneapproximationmethodtodecomposethehigher-ordersymmetriccomplextensorsintothesumsofrank-onecomplexten-sors.Toobtainthedecomposition,ateachstepofthemethod,wecomputethebestsymmetricrank-onecomplexapproximationoftheresidualtensorbynonlinearleast-squaremethod.Themaincontributionsofthispaperareasfollows.•Weproposeasuccessivesymmetricrank-onecomplexapproximationmethodtodecom-posethehigher-ordersymmetriccomplextensors.•Wegiveanexampletoshowthatthesuccessivesymmetricrank-onedecompositioninthecomplexfieldisverydifferentfromthatintherealfield.•Weprovethatthesymmetriccanonicaldecompositioncouldbeobtainedwhenthesuc-cessivesymmetricrank-onecomplexapproximationmethodisappliedtoaunitarydiag-onalizablesymmetrictensor.•Somenumericalexperimentsaregiventoverifytheefficiencyoftheproposedmethod.Notations.Ascaleisdenotedbylowercaseletter,e.g.,a;Avectorisdenotedbyboldfacelowercaseletter,e.g.,a;Amatrixisdenotedbyboldfaceuppercaseletter,e.g.,A;Ahigher-ordertensorisdenotedbyEulerscriptletters,e.g.,A.Weuselowercasesubscriptstodenoteitscomponents;e.g.,ajisthej-thentryofvectora,ajkisthe(j;k)-thentryofmatrixA,aisthe(i;i;···;i)-thentryoftensorA.Forspecialtensors,S[m;n]denotesthei1i2···im12msetofmth-ordern-dimensionalsymmetriccomplextensors.Furthermore,thelowercaseletter-2- ˖ڍመ੾᝶஠ڙጲhttp://www.paper.edu.cniwithoutsubscriptsisimaginaryunit,thesuperscript·∗;·Harecomplexconjugateandthecomplexconjugatedtranspose,respectively.1preliminaryAmth-ordercomplextensorisdenotedasA∈CI1×I2×···×Im.ItiscalledsymmetricifI1=I2=···=Im=nanditsentriesareinvariantunderanypermutationoftheirindices.Itiscalleddiagonalifai1i2···im̸=0onlyifi1=i2=···=im.Asymmetricrank-onetensorisdefinedasam-foldouterproductmu=u⊗u⊗···⊗u;|{z}mwhereu∈Cnand⊗denotestheouterproductbetweenvectors.Thedecompositionofasymmetrictensorintothesumsofsymmetricrank-onetensorsisthesymmetriccanonicaldecomposition.FortwotensorsA;B∈CI1×I2×···×Im,theinnerproductbetweenthemisdefinedas∑I1∑I2∑Im∗=···ai1i2···imbi1i2···im:i1i2imTheFrobeniusnormofatensorA∈CI1×I2×···×Imisdefinedas√∥A∥F=:Forconvenience,∥·∥Fisabbreviatedas∥·∥intherestofthepaper.Thek-mode(matric)productofatensorA∈CI1×I2×···×ImwithamatrixQ∈CJ×IkisdefinedasA×kQwithsizeI1×I2×···×Ik−1×J×Ik+1×···×Im,where∑Ik(A×kQ)i1···ik1jik+1···im=ai1i2···imqjik:ik=1US-eigenpair[5].LetA∈S[m;n].Ifthereareanumber∈Randu∈Cnsuchthat⟨A;um−1⟩=u∗and⟨um−1;A⟩=uwith∥u∥=1,thenwecall(;u)aunitarysymmetriceigenpair(US-eigenpair),callaunitarysymmetriceigenvalue(US-eigenvalue),andcalluaunitarysymmetriceigenvector(US-eigenvector).Thebestrank-oneapproximationofhigher-ordertensors.Inthepaper[8],ithasshowthattensorsoforder-3orhighercanfailtohavebestrank-r(r≥2)approximation,butfortunately,italwayshavearank-oneapproximation.AssumetensorA∈S[m;n].Letmmf(;u)=∥A−u∥;g(u)=∥A−u∥;(1)where∈Randu∈Cn.Then,thebestsymmetricrank-onecomplexapproximationtotensorAisdefinedbymin∈R;∥u∥=1;u∈Cnf(;u)ormin∥u∥=1;u∈Cng(u),whichequalstoeachother[6].-3- ˖ڍመ੾᝶஠ڙጲhttp://www.paper.edu.cnAccordingtoTheorem3.1,Theorem3.2andTheorem3.3in[6],wehavethefollowingresult.Theorem1.AssumethattensorA∈S[m;n],thentheproblemofthebestsymmetricrank-onecomplexapproximationtoAisequivalenttothemaximumproblemmmmaxRe⟨A;u⟩=max|⟨A;u⟩|:(2)∥u∥=1;u∈Cn∥u∥=1;u∈Cnwhere‘Re⟨A;um⟩’denotestherealpartof⟨A;um⟩.Itisshowedin[5]thatthemaximumof(2)isthelargestUS-eigenvalueoftensorA.Namely,ifisaUS-eigenvalueoftensorAwiththelargestvalueand(;u)isaUS-eigenpairofA,thenumisthebestrank-onecomplexapproximationofA.2symmetriccomplextensordecompositionNotethatm2222∥A−u∥=∥A∥−≤∥A∥:Obviously,theresidualtensorA~=A−umisalsoasymmetriccomplextensorwhichtheorderisunchanged.AnditsnormisgettingsmallerthanthatofAstrictlyifonlyif̸=0.Basedonthisfact,wegivethesuccessivesymmetricrank-onedecompositionofhigher-ordersymmetriccomplextensor(SSROD).Algorithm1SSRODInput:symmetriccomplextensorA∈S[m;n].(1)1:initialize"≥0,letk=1,andA=A.(k)2:if∥A∥≤"then3:stop4:else(k)(k)m5:Computeu=argmax∥u∥=1;u∈Cn{Re⟨A;u⟩}(k)(k)m6:Letk=Re⟨A;(u)⟩(k+1)(k)(k)m7:A:=A−k(u)8:k:=k+19:endifProposition1.Foranon-zerotensorA∈S[m;n],itholdsthatmnmax{Re⟨A;u⟩:u∈C;∥u∥=1}>0:-4- ˖ڍመ੾᝶஠ڙጲhttp://www.paper.edu.cnProof.WhenAisareal-valuedtensor.From[5],weknowthatthelargestUS-eigenvalueofanon-zerosymmetrictensorisnolessthanzero,andithas|US|≥|Z|,whereUS;ZmaxmaxmaxmaxarethelargestUS-eigenvalueandthelargestZ-eigenvalue,respectively.InLemma2.2of[4],ithasshowthat|Z|̸=0forarealnon-zerosymmetrictensor.FromTheorem1,wegetthemaxresult.WhenAisacomplex-valuedtensor,wecanproveitsimilarlytothatofLemma2.2in[4].Proposition2.Forasequence{A(k)}⊂S[m;n]producedbyAlgorithm1.If(u(k))misthekbestrank-oneapproximationofA(k).Then→0onlyif∥A(k)∥→0.kProof.BynotingthedifferenceoftheinnerproductoftwotensorsbetweenRandC,wecanproveitsimilarlytothatofLemma2.3in[4].Basedonthesepropositions,wealsohavethefollowingtheorem.Theorem2.Suppose"=0,ifAlgorithm1isappliedtoasymmetriccomplextensorA∈S[m;n],anditgeneratesaninfinitesequenceofsymmetricrank-onetensors{(u(k))m},thenk∑∞∑∞(k)m22A=k(u);∥A∥=k:kkProof.ByProposition1andProposition2,theproofissimilartothatofTheorem2.1in[4]andisomitted.Theorem2showsthatwecangetasuccessivesymmetricrank-oneapproximationoftensorinS[m;n]byAlgorithm1.Thefollowingexampleshowsthatthesuccessivedecompositionofrealtensorsmayactuallybedifferentovertherealfieldandthecomplexfield.Example1.[9]AsymmetrictensorAisdefinedas:[3;2]A∈S;a111=2;a221=a122=a212=−2:ByusingtheAlgorithm1with"=10−5,wegetthenumericalresultshowedintheFigure1.FortensorA,wegetasymmetriccanonicaldecompositioninthecomplexfield,butonlygetanapproximationintherealfield.So,itisnecessarytostudythesuccessivedecompositioninthecomplexfield.3UnitarydiagonalizabletensordecompositionInthissection,weconsiderthesuccessiverank-onedecompositionofaunitarydiagonaliz-abletensor.-5- ˖ڍመ੾᝶஠ڙጲhttp://www.paper.edu.cn4realfieldcomplexfield3.532.521.51Frobeniusnormofresidualtensors0.500510152025iterationsteps图1:NumericalresultofExample1.Definition1.ComplextensorA∈S[m;n]iscalledaunitarydiagonalizabletensor,ifthereisaunitarymatrixP∈Cn×nsuchthatA×PH×PH×···×PH:=A(PH)misadiagonal123mtensor.Toobtainsymmetriccanonicaldecomposition,westudysomepropositionsofmultilineartransformationandtheUS-eigenvalues.Proposition3.ForaunitarydiagonalizabletensorA∈S[m;n],aunitarymatrixP∈Cn×nandavectoru∈Cn,thenthefollowshold.mmm(1)uP=(Pu);mHm(2)P(A(P))=A:(3)Proof.(1)TheresultcanbeobtaineddirectlybyLemma4in[7].(2)Bystraightforwardcalculation,wehave()mHmP(A(P))i1i2···im∑∑=pp···papHpH···pHi1j1i2j2imjmi1i2···imi1^j1i2^j2im^jmj1j2···jm^j1^j2···^jm()()()∑∑∑HHH=ai1i2···impi1j1pi1j1pi2j2pi2j2···pimjmpimjmj1j2jm=ai1i2···im;∀i1;i2;···;im=1;2;···;n:Thiscompletestheproof.Proposition4.SupposetwotensorsA;B∈S[m;n],andthereexitsaunitarymatrixP∈Cn×nsuchthatA=B(PH)m.Ifumisthebestrank-oneapproximationtoA,then(Pu)misthebestrank-oneapproximationtoB.-6- ˖ڍመ੾᝶஠ڙጲhttp://www.paper.edu.cnProof.First,anyglobalmaximizeru∈Cnoftheoptimizationproblemmnmax{Re⟨A;u⟩:∥u∥=1;u∈C}(4)correspondstothebestsymmetricrank-oneapproximationtothetensorAwiththeeigenvalue=Re⟨A;um⟩fromTheorem1.Ontheotherhand,fromTheorem2.2in[10],weknowthatanyglobalmaximizeru∈Cnoftheoptimizationproblem(4)correspondstotheglobalmaximizerPuoftheoptimizationproblemmnmax{Re⟨B;(Pu)⟩:∥u∥=1;u∈C}So(Pu)misthebestsymmetricrank-oneapproximationtothetensorB.Next,wegivethesymmetriccanonicaldecompositionofaunitarydiagonalizabletensorbyapplyingAlgorithm1.Theorem3.Suppose"=0.IfAlgorithm1isappliedtoaunitarydiagonalizabletensorA∈S[m;n],thenitterminatesatmostnsteps.Proof.ForaunitarydiagonalizabletensorA∈S[m;n],thereexitsaunitarymatrixPsuchthatA(PH)misadiagonaltensorwithdiagonalelements;;···;∈Candr≤n.So12r∑r∑rA(PH)m=em=||e~m;kkkkk=1k=1whereeiskthcolumnofthen×nunitmatrix,ande~=ke.kk|k|kFromProposition3,onehas∑rmA=|k|(Pe~k):k=1Withoutlossofgenerality,weassumethat{|k|}isnon-increasing.FromTheorem1,itiseasytoseethat||e~isthebestsymmetricrank-oneapproximationtothetensorA(PH)m−k+1k+1∑k||e~m,fork=0;1;2;···;r−1.FromProposition4,weknowthat||(Pe~)misthej=1jjk+1k+1∑kbestrank-oneapproximationtothetensorA−||(Pe~)m.SoAlgorithm1generatesthej=1jj∑rbestrank-oneapproximationtothetensorA−||(Pe~)mateachstep,andthedesiredk=1kkresultisobtained.4NumericalexperimentsInthissection,wewillshowseveralnumericalexperimentstoverifytheconclusions.ThecomputationsareimplementedinMatlabVersion2014a.Wechoosetheaccuracytolerance"=10−5.-7- ˖ڍመ੾᝶஠ڙጲhttp://www.paper.edu.cnThesubprobleminAlgorithm1isequivalenttofindtheglobalminimizeroftheconstrainedoptimizationproblem(k)m2min∥A−u∥:(5)∈R;∥u∥=1;u∈CnIthasknownthatitisveryexpensivetocomputetheglobalminimizerof(5).Infact,alocalminimizerof(5)suffices.Supposeaunitnormvectoru∈Cnisalocalone.Ifwetake=Re⟨A(k);um⟩,then∥A(k)−um∥2=∥A(k)∥2−2.So,if̸=0,then∥A(k)−um∥<∥A(k)∥.Itshowsthatthesequence{A(k)}strictlydecreasesevenifu∈Cnisalocalminimizer.WecanrunAlgorithm1withseveralstartingpointseveniftheworstcase,whichmeansthe=0,happens.Hence,wecanusethenonlinearleast-squaremethodtosolvetheproblem(5)byusingcommandccpd_nlsoftoolboxTensorLab[11]inthefollowingnumericalexperiments.Example2.[4]ThesymmetrictensorAisdefinedas:a1111=0:2883;a1112=−0:0031;a1113=0:1973;a1122=−0:2485;a1123=−0:2939;a1133=0:3847;a1222=0:2972;a1223=0:1862;a1233=0:0919;a1333=−0:3619;a2222=0:1241;a2223=−0:3420;a2233=0:2127;a2333=0:2727;a3333=−0:3054:TheresultisshowedinFigure2.Inthisexample,wegetanapproximationofA.2.521.51Frobeniusnormofresidualtensors0.500102030405060iterationsteps图2:NumericalresultofExample2.Example3.AunitarydiagonalizabletensorA∈S[3;3]isdefinedas:a111=−8−13i;a121=32+34i;a131=−28−14i;a221=−20−10i;a231=4+20i;a331=10+14i;a222=26+49i;a232=−16+10i;a332=14+34i;a333=−19+13i;ByusingtheAlgorithm1,wegetacanonicaldecomposition−0:64−0:17i0:29+0:17i−0:42+0:52iA=114:55∗0:64+0:17i+81:00∗0:58+0:33i+60:37∗−0:21+0:26i:−0:32−0:09i0:58+0:33i0:42−0:52i-8- ˖ڍመ੾᝶஠ڙጲhttp://www.paper.edu.cnThisverifiesthetrueofTheorem3.5ConclusionInthispaper,weextendthesuccessiverank-oneapproximationmethodfromtherealfieldtothecomplexfield.Wepointoutthatthesuccessivesymmetricrank-onedecompositioninthecomplexfieldisverydifferentfromthatintherealfield.Foraunitarydiagonalizabletensor,weshowthatasymmetriccanonicaldecompositioncouldbeobtainedbythemethod.Somenumericalexperimentsillustratethattheproposedmethodiseffective.参考文献（References）[1]Kolda,T.G.,Bader,B.W.:Tensordecompositionsandapplications.SIAMReview51,455-500(2009).[2]Zhang,T.,Golub,G.:Rank-OneApproximationtoHighOrderTensors.SIAMJournalonMatrixAnalysisandApplications23,534-550(2006).[3]Mu,C.,Hsu,D.,Goldfarb,D.:SuccessiveRank-OneApproximationsforNearlyOrthog-onallyDecomposableSymmetricTensors.SIAMJournalonMatrixAnalysisandApplica-tions36,1638-1659(2015).[4]Wang,Y.,Qi,L.:Onthesuccessivesupersymmetricrank-onedecompositionofhigher-ordersupersymmetrictensors.NumericalLinearAlgebrawithApplications14,503-519(2010).[5]Ni,G.,Qi,L.,Bai,M.:GeometricmeasureofentanglementandU-eigenvaluesoftensors.SIAMJournalonMatrixAnalysisandApplications35,73-87(2014).[6]Ni,G.,Bai,M,:SphericaloptimizationwithcomplexvariablesforcomputingUS-eigenpairs.ComputationalOptimizationandApplications65,1-22(2016).[7]Jiang,B.,Yang,F.,Zhang,S.:TensorandItsTuckerCore:theInvarianceRelationships.arXiv:1601.01469(2016).[8]DeSilva,V.,Lim,L-H.:Tensorrankandtheill-posednessofthebestlow-rankapproxi-mationproblem.SIAMJournalonMatrixAnalysisandApplications30,1084-1127(2008).[9]Comon,P.:Tensors:apartialsurvey.SignalProcessingMagazine(2014).[10]Che,M.,Qi,L.,Wei,Y.:IterativealgorithmsforcomputingUS-andU-eigenpairsofcomplextensors.JournalofComputationalandAppliedMathematics317,547-564(2017).-9- ˖ڍመ੾᝶஠ڙጲhttp://www.paper.edu.cn[11]Vervliet,N.,Debals,O.,Sorber,L.,VanBarel,M.,DeLathauwer,L.:Tensorlab3.0,Availableonline,Mar.2016.URL:http://www.tensorlab.net/.-10-'