张量的低秩逼近课件.ppt

1、张量的低秩逼近张量的低秩逼近白敏茹湖南大学数学与计量经济学院2014-11-15目 录1.1.张量的基本概念张量的基本概念2.2.张量特征值的计算张量特征值的计算3.3.张量秩张量秩1 1逼近和低秩逼近逼近和低秩逼近4.4.张量计算软件张量计算软件5.5.复张量的最佳秩复张量的最佳秩1 1逼近和特征值逼近和特征值1.1.张量的基本概念张量的基本概念121 2NNnnni iiXxR 张量张量：多维数组1阶张量阶张量：向量2阶张量阶张量：矩阵 A=(aij)3阶张量阶张量：长方体 A=(aijk)()2()1()()2()1(2121 ,NiiiiiiNNNaaaxaaaX其中(1)(2)()1

2、()min|RNiiiirank XR Xaaa张量的秩张量的秩张量的秩张量的秩：1927年 HitchcockNP-Hard(1)()()(),()nNrankXrank Xrank Xn-rank秩秩1张量张量：可计算其中 表示 张量X的mode-k mode )(kX秩秩1矩阵矩阵：A=a bT =(aibj)1.1.张量的基本概念张量的基本概念(1)(2)()1min|RNiiiiiAaaa(1)()12(1)(2)()123,()()()min|.,X,1,NNiiiNNS XXRRRnRii TiRASXXXst SRRXXIiN 张量的低秩逼近张量的低秩逼近：用一个低秩的张量X近

3、似表示张量A最佳秩最佳秩R逼近逼近Tucker逼近逼近121 21 21 12 212(1)(2)()111()NNNN NNRRRNi iirrri ri ri rrrrxga aa 最佳秩最佳秩1逼近：逼近：R=11.1.张量的基本概念张量的基本概念1.1.张量的基本概念张量的基本概念min rank()s.t.XXMM 张量的完备化张量的完备化低秩张量M部分元素 被观察到,其中 是被观察到的元数的指标集.张量完备化是指:从所观察到的部分元素来恢复逼近低秩张量MnmmmCxCBxBxAx,1111mmxAx*1*1*1,mmTnS xxSxxx xC xC Z（E）-特征值 H-特征值 U

4、S-特征值 B-特征值11.mmAxx 张量的特征值张量的特征值1.1.张量的基本概念张量的基本概念2.2.张量特征值的计算张量特征值的计算对称非负张量的最大对称非负张量的最大H-特征值的计算特征值的计算：1.Ng,Qi,Zhou 2009，2.Chang,Pearson,Zhang 2011，3.L.Zhang,L.Qi 2012，4.Qi,Q.Yang,Y.Yang 2013Perron-Frobenius 理论对称张量的最大对称张量的最大Z-特征值的计算特征值的计算：The sequential SDPs method Hu,Huang,Qi 20132.Sequential subsp

5、ace projection methodHao,Cui,Dai.20143.Shifted symmetric higher-order power method Kolda,Mayo 20114.Jacobian semidefinite relaxations 计算对称张量所有实的计算对称张量所有实的B-特征值特征值 Cui,Dai,Nie 2014 对称张量的对称张量的US-特征值的计算：特征值的计算：1.Geometric measure of entanglement and U-eigenvalues of tensors,SIAM Journal on Matrix Analy

6、sis and Applications，Ni，Qi，Bai 20142.Complex Shifted Symmetric higher-order power method Ni,Bai 20142.2.张量特征值的计算张量特征值的计算3.3.张量的秩张量的秩1 1逼近和低秩逼近逼近和低秩逼近 张量的秩张量的秩1逼近逼近最佳最佳实实秩秩1逼近的计算方法逼近的计算方法：交替方向法(ADM)、截断高阶奇异值分解(T-HOSVD)、高阶幂法(HOPM)和拟牛顿方法 等。-局部解，或稳定点Nie,Wang2013：半正定松弛方法 -全局最优解最佳最佳复复秩秩1逼近的计算方法逼近的计算方法：Ni,Q

7、i，Bai2014：代数方程方法 -全局最优解3.3.张量的秩张量的秩1 1逼近和低秩逼近逼近和低秩逼近 张量的低秩逼近张量的低秩逼近最佳秩最佳秩R逼近的计算方法逼近的计算方法：交替最小平方法(ALS)最佳最佳Tucker逼近的计算方法逼近的计算方法：高阶奇异值（HOSVD），TUCKALS3，t-SVD4.4.张量计算软件张量计算软件 Matlab,Mathematica,Maple都支持张量计算 Matlab仅支持简单运算，而对于更一般的运算以及稀疏和结构张量，需要添加软件包（如：N-wayToolbox,CuBatch,PLS Toolbox,Tensor Toolbox）才能支持，其中

8、除PLS Toolbox外，都是免费软件。Tensor Toolbox是支持稀疏张量。C+语言软件：HUJI Tensor Library(HTL)，FTensor,Boost Multidimensional Array Library(Boost.MultiArray)FORTAN语言软件：The Multilinear EngineA Guyan Ni,Liqun Qi and Minru Bai,Geometric measure of entanglement and U-eigenvalues of tensors,SIAM Journal on Matrix Analysis a

9、nd Applications 2014,35(1):73-87B Guyan Ni,Minru Bai,Shifted Power Method for computing symmetric complex tensor US-eigenpairs,2014,submitted.5.5.复张量的最佳秩复张量的最佳秩1 1逼近和特征值逼近和特征值1d7 T.G.Kolda and J.R.Mayo,Shifted power method for computing tensor eigenpairs,SIAM Journal on Matrix Analysis and Applicati

10、ons,32(2011),pp.1095-1124.T*TBasic results8 S.Friedland,Best rank one approximation of real symmetric tensors can be chosen symmetric,Frontiers of Mathematics in China,8(2013),pp.19-40.9 X.Zhang,C.Ling and L.Qi,The best rank-1 approximation of a symmetric tensor and related spherical optimization pr

11、oblems,SIAM Journal on Matrix Analysis and Applications 33(2012),pp.806-plex tensors and unitary eigenvalues 10 G.Ni,L.Qi and M.Bai,Geometric measure of entanglement and U-eigenvalues of tensors,to appear in SIAM Journal on Matrix Analysis and Applications The superscript *denotes the complex conjug

12、ate.The superscript T denotes transposition.unitary eigenvalue(U-eigenvalue)of T3.1.US-eigenpairs of symmetric tensors3.2.US-eigenpairs of symmetric tensors8 S.Friedland,Best rank one approximation of real symmetric tensors can be chosen symmetric,Frontiers of Mathematics in China,8(2013),pp.19-40.3

13、.2.US-eigenpairs of symmetric tensors3.2.US-eigenpairs of symmetric tensors11 D.Cartwright and B.Sturmfels,The number of eigenvalues of a tensor,Linear Algebra and its Applications,438(2013),pp.942-9524.Best symmetric rank-one approximation of symmetric tensorsCase d 3The best symmetric rank-one app

14、roximation problem is to find a unit-norm vector x Cn,such thatBy Theorem 7,introducing the US-eigenvalue method,Q1 is equivalent to the following problemExample 1.Assume that S is a real symmetric tensor with d=3 and n=2.Then Q4 is equivalent to the following optimization problemTable1.US-eigenpairs of S with S111=2,S112=1,S122=1,S222=1.谢谢大家！谢谢大家！