张量低秩逼近-MinruBai

目录张量的基本概念张量特征值的计算张量秩1逼近和低秩逼近张量计算软件复张量的最佳秩1逼近和特征值第一页，共35页。1.张量的基本概念

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

H-特征值US-特征值2005,QiB-特征值2014，Cui,Dai,Nie2014，Ni,Qi,Bai张量的特征值1.张量的基本概念第六页，共35页。2.张量特征值的计算

对称非负张量的最大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]第七页，共35页。对称张量的US-特征值的计算：

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

等。----局部解，或稳定点Nie,Wang[2013]：半正定松弛方法----全局最优解最佳复秩1逼近的计算方法：Ni,Qi，Bai[2014]：代数方程方法----全局最优解第九页，共35页。3.张量的秩1逼近和低秩逼近张量的低秩逼近最佳秩R逼近的计算方法：交替最小平方法(ALS)最佳Tucker逼近的计算方法：高阶奇异值（HOSVD），TUCKALS3，t-SVD第十页，共35页。4.张量计算软件Matlab,Mathematica,Maple都支持张量计算Matlab仅支持简单运算，而对于更一般的运算以及稀疏和结构张量，需要添加软件包（如：N-wayToolbox,CuBatch,PLSToolbox,TensorToolbox）才能支持，其中除PLSToolbox外，都是免费软件。TensorToolbox是支持稀疏张量。C++语言软件：HUJITensorLibrary(HTL)，FTensor,BoostMultidimensionalArrayLibrary(Boost.MultiArray)FORTAN语言软件：TheMultilinearEngine第十一页，共35页。[A]GuyanNi,LiqunQiandMinruBai,GeometricmeasureofentanglementandU-eigenvaluesoftensors,SIAMJournalonMatrixAnalysisandApplications2014,35(1):73-87[B]GuyanNi,MinruBai,ShiftedPowerMethodforcomputingsymmetriccomplextensorUS-eigenpairs,2014,submitted.5.复张量的最佳秩1逼近和特征值第十二页，共35页。BasicDefinitions1.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*Tu第十三页，共35页。4.Thebestrank-onetensorapproximationproblemsAssumethatTad-orderrealtensor.Denotearank-onetensoristominimizestheleast-squarescostfunction.Thentherank-oneapproximationproblemTherank-onetensorrank-oneapproximationtotensorT.issaidtobethebestrealIfTisasymmetricrealtensor,thebestrealsymmetricrank-oneapproximation.issaidtobe第十四页，共35页。BasicresultsFriedland[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.第十五页，共35页。complextensorsandunitaryeigenvaluesAd-ordercomplextensorwillbedenotedbyinnerproductnorm[10]G.Ni,L.QiandM.Bai,GeometricmeasureofentanglementandU-eigenvaluesoftensors,toappearinSIAMJournalonMatrixAnalysisandApplicationsThesuperscript*denotesthecomplexconjugate.ThesuperscriptT

denotestransposition.第十六页，共35页。ForA,B∈H,definetheinnerproductandnormasinnerproductnormArank-onetensor第十七页，共35页。unitaryeigenvalue(U-eigenvalue)

ofT第十八页，共35页。DenotebySym(d,n)allsymmetricd-ordern-dimensionaltensorsLetx∈

Cn.Simplydenotetherank-onetensorDefineWecallanumber

∈

Caunitarysymmetriceigenvalue(US-eigenvalue)

ofSif

andanonzerovector第十九页，共35页。Thelargest|λ|istheentanglementeigenvalue.Thecorrespondingrank-onetensor⊗di=1xistheclosestsymmetricseparablestate.Theorem1.Assumethatcomplexd-ordertensorsThenb)allU-eigenvaluesarerealnumbers;c)theUS-eigenpair(,x)toasymmetricd-ordercomplextensorScanalsobedefinedbythefollowingequationsystemor(1)第二十页，共35页。3.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.第二十一页，共35页。Theorem5.If

1=···=

k>

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

1isthesetofallUS-eigenvectorswithrespectto−λ1is第二十二页，共35页。3.2.US-eigenpairsofsymmetrictensorsTheproblemoffindingeigenpairsisequivalenttosolvingapolynomialsystemCased3[8]S.Friedland,Bestrankoneapproximationofrealsymmetrictensorscanbechosensymmetric,FrontiersofMathematicsinChina,8(2013),pp.19-40.第二十三页，共35页。Theorem2.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-eigenpairsofsymmetrictensors第二十四页，共35页。Cased3Theorem6.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-eigenpairsofsymmetrictensors第二十五页，共35页。Note.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-952第二十六页，共35页。Note.3.LetSbethesymmetric3×3×3tensorasinNote2.Thenx=forall0<a<1arenon-zerosolutionsofSxd−1=x*.Itimpliesthat(2)mayhaveinfinitenon-zerosolutions.第二十七页，共35页。4.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.第二十八页，共35页。Cased≥

3Thebestsymmetricrank-oneapproximationproblemistofindaunit-normvectorx∈

Cn,suchthatByTheorem7,introducingtheUS-eigenvaluemethod,Q1isequivalenttothefollowingproblem第二十九页，共35页。Theorem9.LetS∈Sym(d,n).Thena)thebestsymmetricrank-oneapproximationproblemisequivalenttothefollowingoptimizationproblemapproximationofSforeachrank-oneTheproblemoffindingeigenpairsisequivalenttosolvingapolynomialsystem第三十页，共35页。Letx=y+z−1,y,z∈Rn.