一种基于快速傅里叶变换的求解Hankel张量特征值的方法

侯哲，唐嘉，马昌凤

(福建师范大学 数学与信息学院，福建 福州，350117)

Hankel张量在众多领域中都有着广泛应用，例如数字信号处理[1]、自动控制[2]、医学影像[3]和地理科学等。由于其应用背景十分广泛，故而吸引了众多研究学者的广泛关注，例如张量分解[4-5]、张量谱理论[6-7]、张量方程的求解[8-9]以及张量向量积的快速计算[10]等，其中Hankel张量特征值的求解是一个NP问题[11]。本文根据Hankel张量的结构特性利用Cayley变换对其特征值进行了相关研究。

1 Hankel张量及其张量向量积

本节将介绍Hankel张量的定义以及基于Hankel张量结构特点且结合了快速傅里叶变换的张量向量积运算。

定义1[12]张量T∈R[m，n]为m阶n维的Hankel张量当且仅当该张量中的元素ti1i2im满足

ti1i2im=u(i1+i2++im-m)

其中j=1，2，，m；ij=1，2，，n；向量u=(u0，u1，，um(n-1))T是Hankel张量的生成向量，其维数为l=m(n-1)+1。与Hankel张量T相对应的逆循环张量G∈R[m，l]定义如下：

gi1i2im=u(i1+i2++im-m mod l)

其中j=1，2，，m；ij=1，2，，l，不难看出Hankel张量是其相对应的逆循环张量G的子张量，有gi1i2im=ti1i2im成立。

引理1[9]张量G∈R[m，l]是逆循环张量当且仅当它可以被傅里叶矩阵Fl∈Cl×l对角化，即

根据引理1，便可从逆循环张量G的张量向量积运算中得到所需要的Hankel张量的张量向量积运算。给定一个向量y∈Rn并定义如下向量x。

此处l=m(n-1)+1，有

(1)

(2)

向量Gxm-1∈Rl的前n个元素所组成的向量便是Tym-1∈Rn。其中，符号“∘”代表哈达马积，”diag”和”fft/ifft”均为Matlab中的运行符，”diag”表示将向量转变为l阶对角矩阵。

2 求解Hankel张量的特征值

考虑偶数阶实Hankel张量的广义特征值问题

Tyk-1=λSyk-1

(3)

其中T是k阶n维的Hankel张量;S是k阶n维的对称正定张量;向量y∈Rn。若式(3)成立，即存在一个常数λ∈R和一个非零向量y∈Rn，分别是Hankel张量的广义特征值和对应的广义特征向量。

注意，当式(3)中对称张量S分别满足下列条件时，可得到Z-特征对和H-特征对[13]。

2)若S=I，其中I是单位张量，此时的(λ，y)为Hankel张量的H-特征对。

将Hankel张量特征值的求解问题(3)转化为下面的球面约束优化问题来进行求解

(4)

其中Sn-1={y∈Rn|‖y‖=1}是一个单位球面。式(4)中f(y)的梯度为

(5)

对于任意的向量y∈Sn-1有

(6)

定理1 令y*∈Sn-1，那么y*是一阶稳定点当且仅当存在向量(λ*，y*)∈Rn+1满足式(3)，其中λ*=f(y*)是Hankel张量T的特征值，y*是对应的特征向量。

证明 对称张量S是正定的，故对任意的向量y∈Sn-1都有Syk>0。

1)必要性。若y*是一阶稳定点，即g(y*)=0，则由式(5)可得

2)充分性。若(λ*，y*)是Hankel张量T的特征对，即

T(y*)k-1=λ*S(y*)k-1

在求解Hankel张量特征值之前，先用有限存储拟牛顿法(L-BFGS算法)[14]生成一个与梯度相关的下降方向hd=-Hdg(yd)，其中Hd是由L-BFGS算法产生的迭代矩阵且是对称正定的。由Rayleigh商、范数定义及其相融性可知

(7)

其中0<δ1≤δ2。

接下来利用Cayley变换[15]构造的n阶正交矩阵Q来保证迭代过程中的每一步都在单位球面Sn-1中，即

yd+1=Qyd∈Sn-1

(8)

任取一反对称矩阵E∈Rn×n，有(I+E)是可逆矩阵，则

Q=(I+E)-1(I-E)

(9)

矩阵E为

E=μυT-υμT

(10)

注意Q是不包含特征值为-1的正交矩阵。

定理2 若迭代过程中的每一步都是由式(8)产生，那么结合式(9)、(10)可得如下迭代格式

(11)

和

证明yd+1(τ)=Qyd=(I+E)-1(I-E)yd。先利用Sherman-Morrison-Woodbury公式

(I+ABT)-1=I-A(I+BTA)-1BT，

和二阶矩阵的求逆公式计算矩阵I+E的逆矩阵

从而定理得证。

(12)

其中ω∈(0，2)且g(yd)≠0。

从而

3 收敛性分析

在本小节中，首先证明了函数值序列{λd=f(yd)}的收敛性以及迭代序列{yd}的每个聚点都是一阶稳定点这一性质，然后通过Lojasiewicz不等式说明迭代序列{yd}是收敛的，以及CEHT算法(computing eigenvalues of Hankel tensors)具有线性收敛速度。若算法CEHT在有限步迭代终止，即存在迭代步d有g(yd)=0，则由定理1可知λd=f(yd)是Hankel张量 所求特征值，yd是对应的特征向量。序列{yd}是由算法CEHT产生的无限迭代序列。

引理2[3]存在常数K>1有

|f(y)|≤K， ‖g(y)‖≤K， ‖g2(y)‖≤K， ∀y∈Sn-1。

引理3 存在一个常数τmin>0，对任意的迭代步d，τd都有

τmin≤τd≤1。

和

那么有

将函数f(y)在点yd处进行泰勒展开，通过式(6)、(11)及引理2可得如下不等式

接下来证明迭代序列{yd}的每个聚点都是一阶稳定点。

证明 由式(7)和(12)得

即

从而定理得证。

在证明迭代序列{yd}收敛之前，先给出Lojasiewicz不等式和强下降条件。

定理5(Lojasiewicz不等式) 若yd是迭代序列{yd}的临界点，则存在ν∈[0，1)，正数δ3以及y*的一个邻域Ω(y*)有

|f(y)-f(y*)|ν≤δ3‖g(y)‖， ∀y∈Ω(y*)

(14)

定义2 若序列{yd}∈Rn符合下列条件，则该序列满足强下降条件。

φ(yd)-φ(yd+1)≥ξ‖φ(yd)‖·‖yd+1-yd‖

(15)

[φ(yd+1)=φ(yd)]→[yd+1=yd]

(16)

在此ξ>0。

定理6 若迭代序列{yd}是由CEHT算法产生的，那么可以找到一点yd∈Sn-1满足

证明 由于式(4)中的f(y)满足Lojasiewicz不等式，根据引理4，则只需证明其满足定义2中的强下降条件即可。

从式(7)，(11)可得

由式(12)得

(17)

通过逆否命题来证明式(16)成立。令yd≠yd+1，有‖g(y)‖≠0。由式(17)有

f(yd)-f(yd+1)≥ωτdδ1‖g(yd)‖2≥ωτminδ1‖g(yd)‖2>0，

最后给出所提CEHT算法的收敛速度证明。

引理5 假设y*是迭代序列{yd}的一个聚点，若初始点y1∈Bρ(y*)⊆Ω(y*)满足下列不等式

(18)

那么可得

(19)

其中yd∈Bρ(y*)，d=1，2，。

引理6 存在δ4>0满足下列不等式

‖yd+1-yd‖≥δ4‖g(yd)‖。

(20)

定理7 假设y*是迭代序列{yd}的一个稳定点，那么有下列条件成立

‖yd-y*‖≤ϑεd

(21)

(22)

(23)

‖yd+1-y*‖≤Gd+1≤εdG1=εd‖y1-y*‖，

ϑ=‖y1-y*‖>0，式(21)得证。

式(23)得证。