张量的低秩逼近课件

张量的低秩逼近白敏茹湖南大学数学与计量经济学院2014-11-15张量的低秩逼近1目录张量的基本概念张量特征值的计算张量秩1逼近和低秩逼近张量计算软件复张量的最佳秩1逼近和特征值目录张量的基本概念21.张量的基本概念

张量：多维数组1阶张量：向量2阶张量：矩阵A=(aij)3阶张量：长方体A=(aijk)1.张量的基本概念张量：多维数组1阶张量：向量2阶张量：3张量的秩张量的秩：1927年HitchcockNP-Hardn-rank秩1张量：可计算其中表示张量X的mode-kmode秩1矩阵：A=abT=(aibj)1.张量的基本概念张量的秩张量的秩：1927年HitchcockNP-Ha4张量的低秩逼近：用一个低秩的张量X近似表示张量A最佳秩R逼近Tucker逼近最佳秩1逼近：R=11.张量的基本概念张量的低秩逼近：用一个低秩的张量X近似表示张量A最佳秩R逼近51.张量的基本概念张量的完备化低秩张量M部分元素被观察到,其中是被观察到的元数的指标集.张量完备化是指:从所观察到的部分元素来恢复逼近低秩张量M1.张量的基本概念张量的完备化低秩张量M部分元素6Z（E）-特征值

H-特征值US-特征值2005,QiB-特征值2014，Cui,Dai,Nie2014，Ni,Qi,Bai张量的特征值1.张量的基本概念Z（E）-特征值H-特征值US-特征值2005,Q72.张量特征值的计算

对称非负张量的最大H-特征值的计算：

Ng,Qi,Zhou2009，Chang,Pearson,Zhang2011，L.Zhang,L.Qi2012，Qi,Q.Yang,Y.Yang2013Perron-Frobenius理论

对称张量的最大Z-特征值的计算：

ThesequentialSDPsmethod[Hu,Huang,Qi2013]Sequentialsubspaceprojectionmethod[Hao,Cui,Dai.2014]Shiftedsymmetrichigher-orderpowermethod[Kolda,Mayo2011]Jacobiansemidefiniterelaxations计算对称张量所有实的B-特征值[Cui,Dai,Nie2014]2.张量特征值的计算对称非负张量的最大H-特征值的计算：8对称张量的US-特征值的计算：

GeometricmeasureofentanglementandU-eigenvaluesoftensors,SIAMJournalonMatrixAnalysisandApplications，[Ni，Qi，Bai2014]ComplexShiftedSymmetrichigher-orderpowermethod[Ni,Bai2014]2.张量特征值的计算对称张量的US-特征值的计算：Geometricmea93.张量的秩1逼近和低秩逼近张量的秩1逼近最佳实秩1逼近的计算方法：交替方向法(ADM)、截断高阶奇异值分解(T-HOSVD)、高阶幂法(HOPM)和拟牛顿方法

等。----局部解，或稳定点Nie,Wang[2013]：半正定松弛方法----全局最优解最佳复秩1逼近的计算方法：Ni,Qi，Bai[2014]：代数方程方法----全局最优解3.张量的秩1逼近和低秩逼近张量的秩1逼近最佳实秩1逼近103.张量的秩1逼近和低秩逼近张量的低秩逼近最佳秩R逼近的计算方法：交替最小平方法(ALS)最佳Tucker逼近的计算方法：高阶奇异值（HOSVD），TUCKALS3，t-SVD3.张量的秩1逼近和低秩逼近张量的低秩逼近最佳秩R逼近的114.张量计算软件Matlab,Mathematica,Maple都支持张量计算Matlab仅支持简单运算，而对于更一般的运算以及稀疏和结构张量，需要添加软件包（如：N-wayToolbox,CuBatch,PLSToolbox,TensorToolbox）才能支持，其中除PLSToolbox外，都是免费软件。TensorToolbox是支持稀疏张量。C++语言软件：HUJITensorLibrary(HTL)，FTensor,BoostMultidimensionalArrayLibrary(Boost.MultiArray)FORTAN语言软件：TheMultilinearEngine4.张量计算软件Matlab,Mathematica,12[A]GuyanNi,LiqunQiandMinruBai,GeometricmeasureofentanglementandU-eigenvaluesoftensors,SIAMJournalonMatrixAnalysisandApplications2014,35(1):73-87[B]GuyanNi,MinruBai,ShiftedPowerMethodforcomputingsymmetriccomplextensorUS-eigenpairs,2014,submitted.5.复张量的最佳秩1逼近和特征值[A]GuyanNi,LiqunQiandMi13BasicDefinitions1.AtensorSiscalledsymmetric

asitsentriess_{i1···id}

areinvariantunderanypermutationoftheirindices.2.AZ-eigenpair

(,u)toarealsymmetrictensorSisdefinedby3.Aneigenpair

(,u)toarealsymmetrictensorSisdefinedby2005,Qi2011,KoldaandMayo[7]T.G.KoldaandJ.R.Mayo,Shiftedpowermethodforcomputingtensoreigenpairs,SIAMJournalonMatrixAnalysisandApplications,32(2011),pp.1095-1124.uTuu*TuBasicDefinitions1.AtensorS144.Thebestrank-onetensorapproximationproblemsAssumethatTad-orderrealtensor.Denotearank-onetensoristominimizestheleast-squarescostfunction.Thentherank-oneapproximationproblemTherank-onetensorrank-oneapproximationtotensorT.issaidtobethebestrealIfTisasymmetricrealtensor,thebestrealsymmetricrank-oneapproximation.issaidtobe4.Thebestrank-onetensorap15BasicresultsFriedland[2013]andZhangetal[2012]showedthatthebestrealrankoneapproximationtoarealsymmetrictensor,whichinprinciplecanbenonsymmetric,canbechosensymmetric.

udis

thebestrealrank-oneapproximationofTifandonlyif

isaZ-eigenvalueofTwiththelargestabsolutevalue,(,u)isaZ-eigenpair.[Qi2011,Friedland2013,Zhangetal2012][8]S.Friedland,Bestrankoneapproximationofrealsymmetrictensorscanbechosensymmetric,FrontiersofMathematicsinChina,8(2013),pp.19-40.[9]X.Zhang,C.LingandL.Qi,Thebestrank-1approximationofasymmetrictensorandrelatedsphericaloptimizationproblems,SIAMJournalonMatrixAnalysisandApplications33(2012),pp.806-821.BasicresultsFriedland[201316complextensorsandunitaryeigenvaluesAd-ordercomplextensorwillbedenotedbyinnerproductnorm[10]G.Ni,L.QiandM.Bai,GeometricmeasureofentanglementandU-eigenvaluesoftensors,toappearinSIAMJournalonMatrixAnalysisandApplicationsThesuperscript*denotesthecomplexconjugate.ThesuperscriptT

plextensorsandunitaryei17ForA,B∈H,definetheinnerproductandnormasinnerproductnormArank-onetensorForA,B∈H,definetheinner18unitaryeigenvalue(U-eigenvalue)

ofTunitaryeigenvalue(U-eigenval19DenotebySym(d,n)allsymmetricd-ordern-dimensionaltensorsLetx∈

Cn.Simplydenotetherank-onetensorDefineWecallanumber

∈

Caunitarysymmetriceigenvalue(US-eigenvalue)

ofSif

andanonzerovectorDenotebySym(d,n)allsymmet20Thelargest|λ|istheentanglementeigenvalue.Thecorrespondingrank-onetensor⊗di=1xistheclosestsymmetricseparablestate.Theorem1.Assumethatcomplexd-ordertensorsThenb)allU-eigenvaluesarerealnumbers;c)theUS-eigenpair(,x)toasymmetricd-ordercomplextensorScanalsobedefinedbythefollowingequationsystemor(1)Thelargest|λ|istheentangl213.1.US-eigenpairsofsymmetrictensorsTheorem3.(Takagi’sfactorization)LetA∈

Cn×n

beacomplexsymmetrictensor.ThenthereexistsaunitarymatrixU∈

Cn×n

suchthatCased=2:Theorem4.LetA∈

Cn×n

beacomplexsymmetrictensor.LetU∈

Cn×n

beaunitarymatrixsuchthatLetei

=(0,···,0,1,0,···,0)T,i=1,···,n.ThenbothandareUS-eigenpairsofA.ThenumberofdistinctUS-eigenvaluesisatmost2n.3.1.US-eigenpairsofsymmetri22Theorem5.If

1=···=

k>

k+1,1≤k≤n,thenthesetofallUS-eigenvectorswithrespectto

1isthesetofallUS-eigenvectorswithrespectto−λ1isTheorem5.If1=···=233.2.US-eigenpairsofsymmetrictensorsTheproblemoffindingeigenpairsisequivalenttosolvingapolynomialsystemCased3[8]S.Friedland,Bestrankoneapproximationofrealsymmetrictensorscanbechosensymmetric,FrontiersofMathematicsinChina,8(2013),pp.19-40.3.2.US-eigenpairsofsymmetri24Theorem2.Assumethatacomplexd-ordern-dimensionsymmetrictensorS∈Sym(d,n).Thena)ifd≥

3,disanoddinteger,and

0,thenthesystem(1)isequivalentto(2)andthenumberofUS-eigenpairsof(1)isthedoubleofthenumberofsolutionsof(2);b)ifd≥

3,disaneveninteger,and

0,thenthesystem(1)isequivalentto(3)andthenumberofUS-eigenpairsof(1)isequaltothenumberofsolutionsof(3).Cased33.2.US-eigenpairsofsymmetrictensorsTheorem2.Assumethatacompl25Cased3Theorem6.Letd≥3,n≥

2beintegers,S∈Sym(d,n).If(2)hasfinitelymanysolutions,thena)ifdisodd,thenumberofnon-zerosolutionsof(2)isatmostb)ifdiseven,thenumberofnon-zerosolutionsof(3)isatmostc)ShasatmostdistinctnonzeroUS-eigenvalues;d)fornonzeroUS-eigenvalues,alltheUS-eigenpairsofSareasfollowswherexisasolutionof(2).3.2.US-eigenpairsofsymmetrictensorsCased3Theorem6.Letd≥326Note.1.LetSbethesymmetric2×

2×

2×

2tensorwhosenon-zeroentriesareS1111=2,S1112=−1,S1122=−1,S1222=−2,S2222=1.Thenumberofnon-zerosolutionsoftheequationsystem(2)is40whichshowsthattheboundistight.Note.2.CartwrightandSturmfels(2013)showedthateverysymmetrictensorhasfiniteE-eigenvalues.Atthesametime,theyindicatedthatthemagnitudesoftheeigenvalueswith||x||=1maystillbeaninfiniteset(SeeExample5.8of[CartwrightandSturmfels(2013)]),whichimpliesthatthesystemSxd−1=xhasinfinitenon-zerosolutions,whereSisasymmetric3×

3×

3tensorwhosenon-zeroentriesareS111=2,S122=S212=S221=S133=S313=S331=1.[11]D.CartwrightandB.Sturmfels,Thenumberofeigenvaluesofatensor,LinearAlgebraanditsApplications,438(2013),pp.942-952Note.1.LetSbethesymmetri27Note.3.LetSbethesymmetric3×3×3tensorasinNote2.Thenx=forall0<a<1arenon-zerosolutionsofSxd−1=x*.Itimpliesthat(2)mayhaveinfinitenon-zerosolutions.Note.3.LetSbethesymmetri284.Bestsymmetricrank-oneapproximationofsymmetrictensorsTheorem7.LetSbeasymmetriccomplextensor.Let

beaUS-eigenvalueofS.Thena)−

isalsoaUS-eigenvalueofS;b)G(S)=

max.Cased=2Theorem8.LetA∈

Cn×n

beacomplexsymmetricmatrix.Thenforallx∈UEV(A,

1)∪UEV(A,−

1)and

∈

Cwith||=1,(

x)⊗

(

x)arebestsymmetricrank-oneapproximationofA.4.Bestsymmetricrank-oneapp29Cased≥

3Thebestsymmetricrank-oneapproximationproblemistofindaunit-normvectorx∈

Cn,suchthatByTheorem7,introducingtheUS-eigenvaluemethod,Q1isequivalenttothefollowingproblemCased≥3Thebestsymmetric30Theorem9.LetS∈Sym(d,n).Thena)thebestsymmetricrank-oneapproximationproblemisequivalenttothefollowingoptimizationproblemapproximationofSforeachrank-oneTheproblemoffindingeigenpairsisequivalenttosolvingapolynomialsystemTheorem9.LetS∈Sym(d,n).31Letx=y+z−1,y,z∈Rn.ThenQ3isequivalenttothefollowingproblemExample1.AssumethatSisarealsymmetrictensorwithd=3andn=2.ThenQ4isequivalenttothefollowingoptimizationproblemLetx=y+z−1,y,z∈Rn.32Table1.US-eigenpairsofSwithS111=2,S112=1,S122=−1,S222=1.Thebestrealrank-oneapproximationisalsothebestcomplexrank-oneapproximation.Table1.US-eigenpairsofSwit33Theabsolute-valuelargestofZ-eigenvaluesisnotitslargestUS-eigenvalue.Theabsolute-valuelargestof34Thebestrealrank-oneapproximationissometimesalsothebestcomplexrank-oneapproximationevenifthetensorisnotasymmetricnonnegativerealtensor,seeTable1.Theabsolute-valuelargestofZ-eigenvaluesissometimesnotitslargestUS-eigenvalue,seeTable2.Byobservingnumericalexamples,wefindthefollowingresults:

Question1:Whatisthenecessaryandsufficientconditionfor theequalityofthelargestabsoluteZ-eigenvalueand thelargestUS-eigenvaluetoarealsymmetrictensor?Thebestrealrank-oneapproxi35谢谢大家！谢谢大家！36张量的低秩逼近白敏茹湖南大学数学与计量经济学院2014-11-15张量的低秩逼近37目录张量的基本概念张量特征值的计算张量秩1逼近和低秩逼近张量计算软件复张量的最佳秩1逼近和特征值目录张量的基本概念381.张量的基本概念

张量：多维数组1阶张量：向量2阶张量：矩阵A=(aij)3阶张量：长方体A=(aijk)1.张量的基本概念张量：多维数组1阶张量：向量2阶张量：39张量的秩张量的秩：1927年HitchcockNP-Hardn-rank秩1张量：可计算其中表示张量X的mode-kmode秩1矩阵：A=abT=(aibj)1.张量的基本概念张量的秩张量的秩：1927年HitchcockNP-Ha40张量的低秩逼近：用一个低秩的张量X近似表示张量A最佳秩R逼近Tucker逼近最佳秩1逼近：R=11.张量的基本概念张量的低秩逼近：用一个低秩的张量X近似表示张量A最佳秩R逼近411.张量的基本概念张量的完备化低秩张量M部分元素被观察到,其中是被观察到的元数的指标集.张量完备化是指:从所观察到的部分元素来恢复逼近低秩张量M1.张量的基本概念张量的完备化低秩张量M部分元素42Z（E）-特征值

H-特征值US-特征值2005,QiB-特征值2014，Cui,Dai,Nie2014，Ni,Qi,Bai张量的特征值1.张量的基本概念Z（E）-特征值H-特征值US-特征值2005,Q432.张量特征值的计算

对称非负张量的最大H-特征值的计算：

Ng,Qi,Zhou2009，Chang,Pearson,Zhang2011，L.Zhang,L.Qi2012，Qi,Q.Yang,Y.Yang2013Perron-Frobenius理论

对称张量的最大Z-特征值的计算：

ThesequentialSDPsmethod[Hu,Huang,Qi2013]Sequentialsubspaceprojectionmethod[Hao,Cui,Dai.2014]Shiftedsymmetrichigher-orderpowermethod[Kolda,Mayo2011]Jacobiansemidefiniterelaxations计算对称张量所有实的B-特征值[Cui,Dai,Nie2014]2.张量特征值的计算对称非负张量的最大H-特征值的计算：44对称张量的US-特征值的计算：

GeometricmeasureofentanglementandU-eigenvaluesoftensors,SIAMJournalonMatrixAnalysisandApplications，[Ni，Qi，Bai2014]ComplexShiftedSymmetrichigher-orderpowermethod[Ni,Bai2014]2.张量特征值的计算对称张量的US-特征值的计算：Geometricmea453.张量的秩1逼近和低秩逼近张量的秩1逼近最佳实秩1逼近的计算方法：交替方向法(ADM)、截断高阶奇异值分解(T-HOSVD)、高阶幂法(HOPM)和拟牛顿方法

等。----局部解，或稳定点Nie,Wang[2013]：半正定松弛方法----全局最优解最佳复秩1逼近的计算方法：Ni,Qi，Bai[2014]：代数方程方法----全局最优解3.张量的秩1逼近和低秩逼近张量的秩1逼近最佳实秩1逼近463.张量的秩1逼近和低秩逼近张量的低秩逼近最佳秩R逼近的计算方法：交替最小平方法(ALS)最佳Tucker逼近的计算方法：高阶奇异值（HOSVD），TUCKALS3，t-SVD3.张量的秩1逼近和低秩逼近张量的低秩逼近最佳秩R逼近的474.张量计算软件Matlab,Mathematica,Maple都支持张量计算Matlab仅支持简单运算，而对于更一般的运算以及稀疏和结构张量，需要添加软件包（如：N-wayToolbox,CuBatch,PLSToolbox,TensorToolbox）才能支持，其中除PLSToolbox外，都是免费软件。TensorToolbox是支持稀疏张量。C++语言软件：HUJITensorLibrary(HTL)，FTensor,BoostMultidimensionalArrayLibrary(Boost.MultiArray)FORTAN语言软件：TheMultilinearEngine4.张量计算软件Matlab,Mathematica,48[A]GuyanNi,LiqunQiandMinruBai,GeometricmeasureofentanglementandU-eigenvaluesoftensors,SIAMJournalonMatrixAnalysisandApplications2014,35(1):73-87[B]GuyanNi,MinruBai,ShiftedPowerMethodforcomputingsymmetriccomplextensorUS-eigenpairs,2014,submitted.5.复张量的最佳秩1逼近和特征值[A]GuyanNi,LiqunQiandMi49BasicDefinitions1.AtensorSiscalledsymmetric

asitsentriess_{i1···id}

areinvariantunderanypermutationoftheirindices.2.AZ-eigenpair

(,u)toarealsymmetrictensorSisdefinedby3.Aneigenpair

(,u)toarealsymmetrictensorSisdefinedby2005,Qi2011,KoldaandMayo[7]T.G.KoldaandJ.R.Mayo,Shiftedpowermethodforcomputingtensoreigenpairs,SIAMJournalonMatrixAnalysisandApplications,32(2011),pp.1095-1124.uTuu*TuBasicDefinitions1.AtensorS504.Thebestrank-onetensorapproximationproblemsAssumethatTad-orderrealtensor.Denotearank-onetensoristominimizestheleast-squarescostfunction.Thentherank-oneapproximationproblemTherank-onetensorrank-oneapproximationtotensorT.issaidtobethebestrealIfTisasymmetricrealtensor,thebestrealsymmetricrank-oneapproximation.issaidtobe4.Thebestrank-onetensorap51BasicresultsFriedland[2013]andZhangetal[2012]showedthatthebestrealrankoneapproximationtoarealsymmetrictensor,whichinprinciplecanbenonsymmetric,canbechosensymmetric.

udis

thebestrealrank-oneapproximationofTifandonlyif

isaZ-eigenvalueofTwiththelargestabsolutevalue,(,u)isaZ-eigenpair.[Qi2011,Friedland2013,Zhangetal2012][8]S.Friedland,Bestrankoneapproximationofrealsymmetrictensorscanbechosensymmetric,FrontiersofMathematicsinChina,8(2013),pp.19-40.[9]X.Zhang,C.LingandL.Qi,Thebestrank-1approximationofasymmetrictensorandrelatedsphericaloptimizationproblems,SIAMJournalonMatrixAnalysisandApplications33(2012),pp.806-821.BasicresultsFriedland[201352complextensorsandunitaryeigenvaluesAd-ordercomplextensorwillbedenotedbyinnerproductnorm[10]G.Ni,L.QiandM.Bai,GeometricmeasureofentanglementandU-eigenvaluesoftensors,toappearinSIAMJournalonMatrixAnalysisandApplicationsThesuperscript*denotesthecomplexconjugate.ThesuperscriptT

plextensorsandunitaryei53ForA,B∈H,definetheinnerproductandnormasinnerproductnormArank-onetensorForA,B∈H,definetheinner54unitaryeigenvalue(U-eigenvalue)

ofTunitaryeigenvalue(U-eigenval55DenotebySym(d,n)allsymmetricd-ordern-dimensionaltensorsLetx∈

Cn.Simplydenotetherank-onetensorDefineWecallanumber

∈

Caunitarysymmetriceigenvalue(US-eigenvalue)

ofSif

andanonzerovectorDenotebySym(d,n)allsymmet56Thelargest|λ|istheentanglementeigenvalue.Thecorrespondingrank-onetensor⊗di=1xistheclosestsymmetricseparablestate.Theorem1.Assumethatcomplexd-ordertensorsThenb)allU-eigenvaluesarerealnumbers;c)theUS-eigenpair(,x)toasymmetricd-ordercomplextensorScanalsobedefinedbythefollowingequationsystemor(1)Thelargest|λ|istheentangl573.1.US-eigenpairsofsymmetrictensorsTheorem3.(Takagi’sfactorization)LetA∈

Cn×n

beacomplexsymmetrictensor.ThenthereexistsaunitarymatrixU∈

Cn×n

suchthatCased=2:Theorem4.LetA∈

Cn×n

beacomplexsymmetrictensor.LetU∈

Cn×n

beaunitarymatrixsuchthatLetei

=(0,···,0,1,0,···,0)T,i=1,···,n.ThenbothandareUS-eigenpairsofA.ThenumberofdistinctUS-eigenvaluesisatmost2n.3.1.US-eigenpairsofsymmetri58Theorem5.If

1=···=

k>

k+1,1≤k≤n,thenthesetofallUS-eigenvectorswithrespectto

1isthesetofallUS-eigenvectorswithrespectto−λ1isTheorem5.If1=···=593.2.US-eigenpairsofsymmetrictensorsTheproblemoffindingeigenpairsisequivalenttosolvingapolynomialsystemCased3[8]S.Friedland,Bestrankoneapproximationofrealsymmetrictensorscanbechosensymmetric,FrontiersofMathematicsinChina,8(2013),pp.19-40.3.2.US-eigenpairsofsymmetri60Theorem2.Assumethatacomplexd-ordern-dimensionsymmetrictensorS∈Sym(d,n).Thena)ifd≥

3,disanoddinteger,and

0,thenthesystem(1)isequivalentto(2)andthenumberofUS-eigenpairsof(1)isthedoubleofthenumberofsolutionsof(2);b)ifd≥

3,disaneveninteger,and

0,thenthesystem(1)isequivalentto(3)andthenumberofUS-eigenpairsof(1)isequaltothenumberofsolutionsof(3).Cased33.2.US-eigenpairsofsymmetrictensorsTheorem2.Assumethatacompl61Cased3Theorem6.Letd≥3,n≥

2beintegers,S∈Sym(d,n).If(2)hasfinitelymanysolutions,thena)ifdisodd,thenumberofnon-zerosolutionsof(2)isatmostb)ifdiseven,thenumberofnon-zerosolutionsof(3)isatmostc)ShasatmostdistinctnonzeroUS-eigenvalues;d)fornonzeroUS-eigenvalues,alltheUS-eigenpairsofSareasfollowswherexisasolutionof(2).3.2.US-eigenpairsofsymmetrictensorsCased3Theorem6.Letd≥362Note.1.LetSbethesymmetric2×

2×

2×

2tensorwhosenon-zeroentriesareS1111=2,S1112=−1,S1122=−1,S1222=−2,S2222=1.Thenumberofnon-zerosolutionsoftheequationsystem(2)is40whichshowsthattheboundistight.Note.2.CartwrightandSturmfels(2013)showedthateverysymmetrictensorhasfiniteE-eigenvalues.Atthesametime,theyindicatedthatthemagnitudesoftheeigenvalueswith||x||=1maystillbeaninfiniteset(SeeExample5.8of[CartwrightandSturmfels(2013)]),whichimpliesthatthesystemSxd−1=xhasinfinitenon-zerosolutions,whereSisasymmetric3×

3×

3tensorwhosenon-zeroentriesareS111=2,S122=S212=S221=S133=S313=S331=1.[11]D.CartwrightandB.Sturmfels,Thenumberofeigenvaluesofatensor,LinearAlgebraanditsApplications,438(2013),pp.942-952Note.1.LetSbethesymmetri63Note.3.LetSbethesymmetric3×3×3tensorasinNote2.Thenx=forall0<a<1arenon-zerosolutionsofSxd−1=x*.Itimpliesthat(2)mayhaveinfinitenon-zerosolutions.Note.3