张量分解在齐次多项式中的应用

潘珺珺,卢琳璋

(厦门大学数学科学学院,福建厦门361005)

张量分解在齐次多项式中的应用

潘珺珺,卢琳璋*

(厦门大学数学科学学院,福建厦门361005)

针对n元m次齐次实系数多项式,提出了对应的m阶n维系数张量的定义,并应用张量分解,给出了该类多项式因子分解的充要条件.证明了该类多项式总是可以写成若干个因式之和,因此通过构造系数张量就能得到所需要的因式之和.

齐次多项式;张量;TT格式

n元m次齐次多项式的研究是一个古老而有意义的课题.在很多方面有着重要的应用,比如,由Qi[1-2]和Lim[3]中提出的Z特征值问题,可以转化成多项式最优化问题来求解.我们知道对于二次型的研究,矩阵分解有着非常重要的作用.考虑n元m次齐次多项式在实数域上的情况,将矩阵在二次型的应用自然推广到张量上.

1 预备知识

这一节简单回顾齐次多项式的定义以及相关的张量知识.

定义1[4]n元m次齐次多项式(按字典排列)

所谓张量就是高维数组,例如,向量可看成一阶张量,矩阵可看成二阶张量,对于m阶n维张量∈Rn×n×…×n,我们采用Kolda等在文献[5]中的定义,记为∈R[m,n].

定义∏m为(1,2,…,m)所有置换的集合,有

定义2[5-6]∈R[m,n]为超对称张量,如果αi1,i2,…,im=αip(1),ip(2),…,ip(m),其中{i1,i2…,im}∈{1,2,…,n},p∈∏m.

定义3[6]若写成m个向量外积,即

其中α(i)=[α(i)1,α(i)2,…,α(i)n]∈Rn,“◦”表示外积.

定义4[6]设张量∈R[m,n],向量x∈Rn,二者的乘积定义为

定义5[7-8]张量∈R[m,n]总可以写成

张量TT-svd分解由Oseledets在文献[7]提出的,这种分解方式是在张量的展开矩阵的svd分解基础上进行的.我们以3阶张量为例,来说明TT分解的过程.

再将矩阵V1重新排列,对重排的V1进行奇异值分解,如下:

令U3(α2;i3)=V2(α2;i3),那么有

在MATLAB中,可以直接使用由Oseledets给出的TT工具包[9],任意一个张量的TT分解实现很简单,仅需要“TT-tensor”这个命令.

2 主要结果

令x=[x1,x2,…,xn]∈Rn,那么f(x)可以等价写为

对任何的{i1,i2…,im}∈{1,2,…,n},p∈∏m,有

若固定{i1,i2…,im},有xj11xj22…xjnn与之对应,则有

下面举个例子说明式(12)成立.

例1 设f(x)是一个二元三次多项式,有

按照式(10),有

则

由式(13),可知:

即式(12)成立.容易知道满足以上等式的aijk有无数个.设(i,j,k)=aijk,显然∈R2×2×2是一个3阶2维张量.

其中bj1,j2,…,jn为式(1)所定义的系数.称张量为n元m次多项式(1)的系数张量.易知,对应式(1)的系数张量有无数个,称包含所有系数张量集合为对应于多项式(1)的系数张量集,记为φ().

根据定义4,多项式(10)可以写成

当m=2时,f(x)为n元2次齐次多项式,f(x)= xTAx,当A对称时便为我们所熟悉的二次型.

定理1 若m次齐次多项式f(x)形如式(1)可以写成m个一次实系数因式的乘积的充要条件是存在秩1张量∈φ().

证明 m=1时,显然.

当m=2时,A为秩1阵⇔A=αβT,其中α=(α1,…,αn)T,β=(β1,…,βn)T,⇔

定理2 m次齐次多项式f(x)形如式(1)总是可以写成若干个因式的和,每个因式为m个一次因式乘积.

其中1≤i1,i2,…,im≤n,A1(i1)∈R1×r1,Ak(ik)∈

Rrk¯1×rk,Am(im)∈Rrm¯1×1.则

将y(k)展开,即得.

根据定理2的证明,容易得到

因为Ak(ik)是数,故f(x)表示成如上的m个一次实系数因式的乘积,证得.

我们给出例2,从直观上来说明上述这些理论.

构造系数张量1:

简化为

得到f(x)的因式分解.

构造系数张量2:

该系数向量为超对称张量.应用TT分解,得到

其中A1(i1)∈R1×3,A2(i2)∈R3×3,A3(i3)∈R3×1,i1, i2,i3=1,2,3.令,得到

那么

3 结论及进一步的工作

本文主要讨论了张量分解与实系数齐次多项式的关系,提出了对应的系数张量的定义,给出了该类多项式因子分解的充要条件.我们发现通过构造系数张量,利用张量分解,多项式总是能得到对应的因式之和.这些结论都是由矩阵在n元2次齐次多项式应用自然推广的,但同时对于特征值分解可以将二次型化为标准型这一结论,张量没有对应的分解方式,对于一般的n次型还无法实现标准型的转化.这些将是进一步的工作.

[1] Qi L.Eigenvalues of a real supersymmetric tensor[J].J Symb Comput,2005,40:1302-1324.

[2] Qi L.Eigenvalues and invariants of tensors[J].J Math A-nal Appl,2007,325:1363-1377.

[3] Lim L H.Singular values and eigenvalues of tensors:a variational approach[J].Proceeding of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing,2005,1:129-132.

[4] 北京大学数学系.高等代数[M].3版.北京:高等教育出版社,2003:34-39.

[5] Kolda T G,Mayo J R.Shifted power method for computing tensor eigenpairs[J].SIAM J Matrix Anal Appl, 2011,32(4),1095-1124.

[6] Kolda T G,Bader B W.Tensor decompositions and applications[J].SIAM REV,2009,51:455-500.

[7] Oseledets I V.Tensor train decomposition[J].SIAM J Sci Comp,2011,33:2295-2317.

[8] Oseledets I V,Tyrtyshnikov E E.Breaking the curse of dimensionality,or how to use svd in many dimensions [J].SIAM J Sci Comp,2009,31:3744-3759.

[9] Oseledets I V.TT-Toolbox 2.2[EB/OL].[2012-01-09]. http://spring.inm.ras.ru/osel/page-id=24.

[10] Lathauwer L D,Moor B D,Vandewalle J.A multilinear singular value decomposition[J].SIAM J Matrix Anal Appl,2000,21:1253-1278.

Applications of Tensor Decomposition in Homogeneous Polynomials

PAN Jun-jun,LU Lin-zhang*
(School of Mathematical Sciences,Xiamen University,Xiamen 361005,China)

:We consider n-variable homogeneous polynomials of degree m with real coefficients.We propose the corresponding coefficient tensors of order m and n-dimension.A necessary and sufficient condition for the polynomial factorization isgiven by using tensor decomposition to its coefficient tensor.We prove that the polynomial can be written as a sum of factors.Therefore,we can obtain the sum we desire by reconstructing its coefficient tensor.

homogeneous polynomial;tensor;TT-format

O 151.23

A

0438-0479(2015)03-0347-04

10.6043/j.issn.0438-0479.2015.03.009

2014-08-14 录用日期:2014-12-04

国家自然科学基金(11261012)

*通信作者:lzlu@xmu.edu.cn

潘珺珺,卢琳璋.张量分解在齐次多项式中的应用[J].厦门大学学报:自然科学版,2015,54(3):347-350.

:Pan Junjun,Lu Linzhang.Applications of tensor decomposition in homogeneous polynomial[J].Journal of Xiamen University:Natural Science,2015,54(3):347-350.(in Chinese)