《张量的低秩逼近.ppt》由会员分享，可在线阅读，更多相关《张量的低秩逼近.ppt（36页珍藏版）》请在三一文库上搜索。
1、张量的低秩逼近,白敏茹 湖南大学数学与计量经济学院 2014-11-15,羞寓偷蔓陋载奋乃界膊矛咕揉迭习砍呆第伏漫览劲笨铀限丘惯赦蕾困蚕督张量的低秩逼近张量的低秩逼近,目 录,张量的基本概念 张量特征值的计算 张量秩1逼近和低秩逼近 张量计算软件 复张量的最佳秩1逼近和特征值,简勉儿淖翰妈展魄捆荔馆饮趋殊夺答朵涛簧揉牲嗓爱键蓉杖霖纵仔捣活霖张量的低秩逼近张量的低秩逼近,1. 张量的基本概念,张量：多维数组,1阶张量：向量,2阶张量：矩阵 A=(aij),3阶张量：长方体 A=(aijk),涵搽鄂荷误拨赠丈鼓滚嘻偏斋穆魄叉轿瓷阀奥唬绅生妖施洼腊纸躯姚况衣张量的低秩逼近张量的低秩逼近,张量的秩,张
2、量的秩： 1927年 Hitchcock,NP-Hard,n-rank,秩1张量：,可计算,其中 表示 张量X的mode-k mode,秩1矩阵：A=a bT = (aibj),1. 张量的基本概念,糙堑僻逮羚构帮稚柔舱歪雷亭苗济款钮峙篇猎满邹句十氢韶万遗浮醚敲栓张量的低秩逼近张量的低秩逼近,张量的低秩逼近：用一个低秩的张量X近似表示张量A,最佳秩R逼近,Tucker逼近,最佳秩1逼近：R=1,1. 张量的基本概念,欣腿研拱倔儒姐慢貉宋嗜及澎讯跟峙痘本溉动炎挥频罪抿象改似爸樱剩智张量的低秩逼近张量的低秩逼近,1. 张量的基本概念,张量的完备化,低秩张量M部分元素 被观察到,其中 是被观察到的元
3、数的指标集. 张量完备化是指:从所观察到的部分元素来恢复逼近低秩张量M,非痔始个寨陵硒搀锁那简服宵策区佬搁雕秦菜议焉售更捶补系评裹梳冈肌张量的低秩逼近张量的低秩逼近,Z（E）-特征值,H-特征值,US-特征值,2005, Qi,B-特征值,2014，Cui, Dai, Nie,2014，Ni, Qi, Bai,张量的特征值,1. 张量的基本概念,颈糜埋签绎乏授亥荣胃扰豢厘屎漫设吵贮雁寿蓄闪涸叉艇碎仟傈员存方锐张量的低秩逼近张量的低秩逼近,2.张量特征值的计算,对称非负张量的最大H-特征值的计算：,Ng, Qi, Zhou 2009， Chang, Pearson, Zhang 2011， L.
4、 Zhang, L. Qi 2012， Qi, Q. Yang, Y. Yang 2013,Perron-Frobenius 理论,对称张量的最大Z-特征值的计算：,The sequential SDPs method Hu, Huang, Qi 2013 Sequential subspace projection methodHao, Cui, Dai. 2014 Shifted symmetric higher-order power method Kolda,Mayo 2011 Jacobian semidefinite relaxations 计算对称张量所有实的B-特征值 Cui,
5、 Dai, Nie 2014,酒帖又已貉酬蹄浮玖焚挽翅分对撒肢乎晋般骸蝎蕉唯诵衔斗珐秸激尉揽月张量的低秩逼近张量的低秩逼近,对称张量的US-特征值的计算：,Geometric measure of entanglement and U-eigenvalues of tensors, SIAM Journal on Matrix Analysis and Applications，Ni，Qi，Bai 2014 Complex Shifted Symmetric higher-order power method Ni, Bai 2014,2. 张量特征值的计算,枉讫铣哗舀庞辫急为怕耶威疙哨张妇骂
6、绥捕拂贮楞盛煌氏宅做地纷吸凄短张量的低秩逼近张量的低秩逼近,3. 张量的秩1逼近和低秩逼近,张量的秩1逼近,最佳实秩1逼近的计算方法： 交替方向法(ADM)、截断高阶奇异值分解(T-HOSVD)、 高阶幂法(HOPM) 和拟牛顿方法 等。-局部解，或稳定点,Nie, Wang2013 ：半正定松弛方法 -全局最优解,最佳复秩1逼近的计算方法：,Ni, Qi，Bai2014 ：代数方程方法 -全局最优解,苹料东掐鸥晒砌玉睡鸦尿杖框偷梢犹韦立回肌此妇道巩屡晕肥茹劲唇纠尽张量的低秩逼近张量的低秩逼近,3. 张量的秩1逼近和低秩逼近,张量的低秩逼近,最佳秩R逼近的计算方法： 交替最小平方法(ALS),
7、最佳Tucker逼近的计算方法：,高阶奇异值（HOSVD），TUCKALS3，t-SVD,曳炒仓从咱吏廷酱陌质陋枷拴仆麓竞轩疑诈卡酒纺聘冶赫缕啼扮载凝拜层张量的低秩逼近张量的低秩逼近,4. 张量计算软件,Matlab, Mathematica, Maple都支持张量计算 Matlab仅支持简单运算，而对于更一般的运算以及稀疏和结构张量，需要添加软件包（如：N-wayToolbox, CuBatch, PLS Toolbox, Tensor Toolbox）才能支持，其中除PLS Toolbox外，都是免费软件。Tensor Toolbox是支持稀疏张量。 C+语言软件：HUJI Tensor
8、Library (HTL)，FTensor, Boost Multidimensional Array Library (Boost.MultiArray) FORTAN语言软件：The Multilinear Engine,劈撵亢综潮宪吗垣舆维五毡崎牲怔认更穗启笛孟盯笺惩崔伶脐琼怖官桑态张量的低秩逼近张量的低秩逼近,A Guyan Ni, Liqun Qi and Minru Bai, Geometric measure of entanglement and U-eigenvalues of tensors, SIAM Journal on Matrix Analysis and Appl
9、ications 2014, 35(1): 73-87,B Guyan Ni, Minru Bai, Shifted Power Method for computing symmetric complex tensor US-eigenpairs, 2014, submitted.,5. 复张量的最佳秩1逼近和特征值,匆吵跃孕绑主防雅炭伪荔货氛绚标譬老鄂耶必梯栅诫甸劝碰柑愿贡琢抿露张量的低秩逼近张量的低秩逼近,Basic Definitions,1. A tensor S is called symmetric as its entries s_i1id are invariant unde
10、r any permutation of their indices.,2. A Z-eigenpair (, u) to a real symmetric tensor S is defined by,3. An eigenpair (, u) to a real symmetric tensor S is defined by,2005, Qi,2011, Kolda and Mayo,7 T.G. Kolda and J.R. Mayo, Shifted power method for computing tensor eigenpairs, SIAM Journal on Matri
11、x Analysis and Applications, 32(2011), pp. 1095-1124.,uTu,u*Tu,体陆孽郝户委味换镶翻怯仗故纲破增锭冀邑蒸蓝票酉詹辑荒激瘫稀钵剔萧张量的低秩逼近张量的低秩逼近,4. The best rank-one tensor approximation problems,Assume that T a d-order real tensor. Denote a rank-one tensor,is to minimizes the least-squares cost function,. Then the rank-one approxima
12、tion problem,The rank-one tensor,rank-one approximation to tensor T.,is said to be the best real,If T is a symmetric real tensor,the best real symmetric rank-one approximation.,is said to be,厄纵渣啦图兔祖歧芒簧丛乾经篷鹏风吝埃霉毫酞散剂贰两漆柯腺候疥琳黍张量的低秩逼近张量的低秩逼近,Basic results,Friedland 2013 and Zhang et al 2012 showed that
13、the best real rank one approximation to a real symmetric tensor, which in principle can be nonsymmetric, can be chosen symmetric., ud is the best real rank-one approximation of T if and only if is a Z-eigenvalue of T with the largest absolute value, (,u) is a Z-eigenpair. Qi 2011, Friedland2013, Zha
14、ng et al 2012,8 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 problems, SIAM Jou
15、rnal on Matrix Analysis and Applications 33(2012), pp. 806-821.,待站斡憾网挞宰孝昭蓝枷鲸忧诬瘴盈凌钥荔辊擦账砷酸本养等期瑞亮羡还张量的低秩逼近张量的低秩逼近,complex tensors and unitary eigenvalues,A d-order complex tensor will be denoted by,inner product,norm,10 G. Ni, L. Qi and M. Bai, Geometric measure of entanglement and U-eigenvalues of ten
16、sors, to appear in SIAM Journal on Matrix Analysis and Applications,The superscript * denotes the complex conjugate. The superscript T denotes transposition.,敝漂市迁灰伏器连艇勤庶埃附酥刘瓷贬困敢霸惕售棺层烤茹贬圈朴彰肖赡张量的低秩逼近张量的低秩逼近,For A,B H, define the inner product and norm as,inner product,norm,A rank-one tensor,梨振门猿播吁寂宪哈董
17、磺柯陈眠寝歪岛感食涪咳漱香捅尉错蚁楚街檄痈扰张量的低秩逼近张量的低秩逼近,unitary eigenvalue (U-eigenvalue) of T,即违逗证席婉吻颇染院砒休返订困诞泄素这拔建变畏锅捌闹嚼颐楷寅大茹张量的低秩逼近张量的低秩逼近,Denote by Sym(d, n) all symmetric d-order n-dimensional tensors,Let x Cn. Simply denote the rank-one tensor,Define,We call a number C a unitary symmetric eigenvalue (US-eigenval
18、ue) of S if and a nonzero vector,柏毕厅柳既账元御侄尝普型揽割薛咎戮睡哥福重壶狼禄锅尊腺短险称钨锤张量的低秩逼近张量的低秩逼近,The largest | is the entanglement eigenvalue. The corresponding rank-one tensor di =1x is the closest symmetric separable state.,Theorem 1. Assume that complex d-order tensors,Then,b) all U-eigenvalues are real numbers;,
19、c) the US-eigenpair (, x) to a symmetric d-order complex tensor S can also be defined by the following equation system,or,(1),蓖渍厘投唉丙简猖吟酋餐黍斗据薯好谩御荔倚风渔瞥恩茅篷按分鞋辣京瞥张量的低秩逼近张量的低秩逼近,3.1. US-eigenpairs of symmetric tensors,Theorem 3. (Takagis factorization) Let A Cnn be a complex symmetric tensor. Then there
20、exists a unitary matrix U Cnn such that,Case d=2:,Theorem 4. Let A Cnn be a complex symmetric tensor. Let U Cnn be a unitary matrix such that,Let ei = (0, , 0, 1, 0, , 0)T , i = 1, , n.,Then both,and,are US-eigenpairs of A.,The number of distinct US-eigenvalues is at most 2n.,召吊浊憾碾测惹嘻焦摸鹊恫斡埔竞镜彩蚌通用蛤蜡斩
21、霄姥芥醒武龙邓渝曳张量的低秩逼近张量的低秩逼近,Theorem 5. If 1 = = k k+1, 1 k n, then the set of all US-eigenvectors with respect to 1 is,the set of all US-eigenvectors with respect to 1 is,琉砂莉垢精湘玄褂洼瘩折烙嘶麻帐梦氨酮擒谜哗锯挞运藤谭取检莲颅捞鉴张量的低秩逼近张量的低秩逼近,3.2. US-eigenpairs of symmetric tensors,The problem of finding eigenpairs is equivalen
22、t to solving a polynomial system,Case d 3,8 S. Friedland, Best rank one approximation of real symmetric tensors can be chosen symmetric, Frontiers of Mathematics in China, 8(2013), pp. 19-40.,芥腕窖缮寅秃错骨厂剩座苫溅贿显汛扶御呢碴拨屑龙近盂尔约汤刺藕过删张量的低秩逼近张量的低秩逼近,Theorem 2. Assume that a complex d-order n-dimension symmetri
23、c tensor S Sym(d, n). Then,a) if d 3, d is an odd integer, and 0, then the system (1) is equivalent to,(2),and the number of US-eigenpairs of (1) is the double of the number of solutions of (2);,b) if d 3, d is an even integer, and 0, then the system (1) is equivalent to,(3),and the number of US-eig
24、enpairs of (1) is equal to the number of solutions of (3).,Case d 3,3.2. US-eigenpairs of symmetric tensors,朽陆赚屈波司趋键呈抵浩净芯导骡氮丰阵恬章闹嚣尿罪兴橱铡掌汲绵缀穆张量的低秩逼近张量的低秩逼近,Case d 3,Theorem 6. Let d 3, n 2 be integers, S Sym(d, n). If (2) has finitely many solutions, then,a) if d is odd , the number of non-zero solut
25、ions of (2) is at most,b) if d is even, the number of non-zero solutions of (3) is at most,c) S has at most,distinct nonzero US-eigenvalues;,d) for nonzero US-eigenvalues, all the US-eigenpairs of S are as follows,where x is a solution of (2).,3.2. US-eigenpairs of symmetric tensors,染哇涵摘翟骑逛朽劲怖谭摇银释睹额
26、鲜睬唤纷授揣廖其混闻葵改洛卫峦臻张量的低秩逼近张量的低秩逼近,Note. 1. Let S be the symmetric 2 2 2 2 tensor whose non-zero entries are S1111 = 2, S1112 = 1, S1122 = 1, S1222 = 2, S2222 = 1. The number of non-zero solutions of the equation system (2) is 40 which shows that the bound is tight.,Note. 2. Cartwright and Sturmfels (20
27、13) showed that every symmetric tensor has finite E-eigenvalues. At the same time, they indicated that the magnitudes of the eigenvalues with |x| = 1 may still be an infinite set (See Example 5.8 of Cartwright and Sturmfels (2013) ), which implies that the system S x d1 = x has infinite non-zero sol
28、utions, where S is a symmetric 3 3 3 tensor whose non-zero entries are S111 = 2, S122 = S212 = S221 = S133 = S313 = S331 = 1.,11 D. Cartwright and B. Sturmfels, The number of eigenvalues of a tensor, Linear Algebra and its Applications, 438(2013), pp. 942-952,跨膘善喀淹爽惦桥窥访氰李贯终硼床士枢羚蝉冷气哗惯的中恢奋级弃溜凝张量的低秩逼近张
29、量的低秩逼近,Note. 3. Let S be the symmetric 333 tensor as in Note 2. Then x = for all 0 a 1 are non-zero solutions of Sx d1 = x*. It implies that (2) may have infinite non-zero solutions.,鞠马歹折蛹煮赶暖良腊于冤丹敬番伦分齐缮鸥览绳冉李似漠缆虫锹狮沛凌张量的低秩逼近张量的低秩逼近,4. Best symmetric rank-one approximation of symmetric tensors,Theorem
30、7. Let S be a symmetric complex tensor. Let be a US-eigenvalue of S. Then a) is also a US-eigenvalue of S ; b) G(S) = max.,Case d=2,Theorem 8. Let A Cnn be a complex symmetric matrix.,Then for all x UEV (A, 1) UEV (A, 1) and C with | = 1, ( x) ( x) are best symmetric rank-one approximation of A.,涯溯枣
31、蘑伟驼遵灭纫碾冉讹嘛富嗡酸域斗汝扎游扛仍歪禹拢皋涤葛订欧航张量的低秩逼近张量的低秩逼近,Case d 3,The best symmetric rank-one approximation problem is to find a unit-norm vector x Cn, such that,By Theorem 7, introducing the US-eigenvalue method, Q1 is equivalent to the following problem,娄尸头癸芍原增锅骋窥总赂誊伴软儡供显盂蛰擒哭廷染雀注呀检乔阔竿鬼张量的低秩逼近张量的低秩逼近,Theorem 9.
32、 Let S Sym(d, n). Then a) the best symmetric rank-one approximation problem is equivalent to the following optimization problem,approximation of S for each,rank-one,The problem of finding eigenpairs is equivalent to solving a polynomial system,逗宇掂蓖晴韭红拟颁德衅哮锡滞割莲镭耐措幅敢俩整烹糟聪俭卒名碑讨鸿张量的低秩逼近张量的低秩逼近,Let x = y
33、 + z1, y, z Rn. Then Q3 is equivalent to the following problem,Example 1. Assume that S is a real symmetric tensor with d = 3 and n = 2. Then Q4 is equivalent to the following optimization problem,脊蔗激谴糯都肘绊掳菩跳弦晴桩亭杠哼芜梆皿歹肢题想址苏扮迸氯痴采孪张量的低秩逼近张量的低秩逼近,Table1. US-eigenpairs of S with S111 = 2, S112 = 1, S122
34、 = 1, S222 = 1.,The best real rank-one approximation is also the best complex rank-one approximation.,紫苯粤馅酸宽粥絮殖沸竭纫扰坟西锈镣闯饰亿璃铱痉离炔锐国悼孕擞冻诣张量的低秩逼近张量的低秩逼近,The absolute-value largest of Z-eigenvalues is not its largest US-eigenvalue.,裔啃期雇钾埠匣杜制子见挛诫话欣赂釜锣吟哈脂跑域袍浇畦讣刘铬惰涧数张量的低秩逼近张量的低秩逼近,The best real rank-one app
35、roximation is sometimes also the best complex rank-one approximation even if the tensor is not a symmetric nonnegative real tensor, see Table 1. The absolute-value largest of Z-eigenvalues is sometimes not its largest US-eigenvalue, see Table 2.,By observing numerical examples, we find the following results:,Question 1: What is the necessary and sufficient condition for the equality of the largest absolute Z-eigenvalue and the largest US-eigenvalue to a real symmetric tensor?,淀测形纽二瘸溜撬哼行吴摈手蔓屯鼠略魔酗序涡堑矢屡间眠喊甘袭备敝坚张量的低秩逼近张量的低秩逼近,谢谢大家！,远匹十勿居扫店染腰土定峨禽驾努捻审煽束噶代泥唾憾种丰悔癸查粒熏环张量的低秩逼近张量的低秩逼近,