一種基于快速傅里葉變換的求解Hankel張量特征值的方法

侯哲，唐嘉，馬昌鳳

(福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院，福建 福州，350117)

Hankel張量在眾多領(lǐng)域中都有著廣泛應(yīng)用，例如數(shù)字信號處理[1]、自動(dòng)控制[2]、醫(yī)學(xué)影像[3]和地理科學(xué)等。由于其應(yīng)用背景十分廣泛，故而吸引了眾多研究學(xué)者的廣泛關(guān)注，例如張量分解[4-5]、張量譜理論[6-7]、張量方程的求解[8-9]以及張量向量積的快速計(jì)算[10]等，其中Hankel張量特征值的求解是一個(gè)NP問題[11]。本文根據(jù)Hankel張量的結(jié)構(gòu)特性利用Cayley變換對其特征值進(jìn)行了相關(guān)研究。

1 Hankel張量及其張量向量積

本節(jié)將介紹Hankel張量的定義以及基于Hankel張量結(jié)構(gòu)特點(diǎn)且結(jié)合了快速傅里葉變換的張量向量積運(yùn)算。

定義1[12]張量T∈R[m，n]為m階n維的Hankel張量當(dāng)且僅當(dāng)該張量中的元素ti1i2im滿足

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

其中j=1，2，，m；ij=1，2，，n；向量u=(u0，u1，，um(n-1))T是Hankel張量的生成向量，其維數(shù)為l=m(n-1)+1。與Hankel張量T相對應(yīng)的逆循環(huán)張量G∈R[m，l]定義如下：

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

其中j=1，2，，m；ij=1，2，，l，不難看出Hankel張量是其相對應(yīng)的逆循環(huán)張量G的子張量，有g(shù)i1i2im=ti1i2im成立。

引理1[9]張量G∈R[m，l]是逆循環(huán)張量當(dāng)且僅當(dāng)它可以被傅里葉矩陣Fl∈Cl×l對角化，即

根據(jù)引理1，便可從逆循環(huán)張量G的張量向量積運(yùn)算中得到所需要的Hankel張量的張量向量積運(yùn)算。給定一個(gè)向量y∈Rn并定義如下向量x。

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

(1)

(2)

向量Gxm-1∈Rl的前n個(gè)元素所組成的向量便是Tym-1∈Rn。其中，符號“°”代表哈達(dá)馬積，”diag”和”fft/ifft”均為Matlab中的運(yùn)行符，”diag”表示將向量轉(zhuǎn)變?yōu)閘階對角矩陣。

2 求解Hankel張量的特征值

考慮偶數(shù)階實(shí)Hankel張量的廣義特征值問題

Tyk-1=λSyk-1

(3)

其中T是k階n維的Hankel張量;S是k階n維的對稱正定張量;向量y∈Rn。若式(3)成立，即存在一個(gè)常數(shù)λ∈R和一個(gè)非零向量y∈Rn，分別是Hankel張量的廣義特征值和對應(yīng)的廣義特征向量。

注意，當(dāng)式(3)中對稱張量S分別滿足下列條件時(shí)，可得到Z-特征對和H-特征對[13]。

2)若S=I，其中I是單位張量，此時(shí)的(λ，y)為Hankel張量的H-特征對。

將Hankel張量特征值的求解問題(3)轉(zhuǎn)化為下面的球面約束優(yōu)化問題來進(jìn)行求解

(4)

其中Sn-1={y∈Rn|‖y‖=1}是一個(gè)單位球面。式(4)中f(y)的梯度為

(5)

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

(6)

定理1 令y*∈Sn-1，那么y*是一階穩(wěn)定點(diǎn)當(dāng)且僅當(dāng)存在向量(λ*，y*)∈Rn+1滿足式(3)，其中λ*=f(y*)是Hankel張量T的特征值，y*是對應(yīng)的特征向量。

證明 對稱張量S是正定的，故對任意的向量y∈Sn-1都有Syk>0。

1)必要性。若y*是一階穩(wěn)定點(diǎn)，即g(y*)=0，則由式(5)可得

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

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

在求解Hankel張量特征值之前，先用有限存儲(chǔ)擬牛頓法(L-BFGS算法)[14]生成一個(gè)與梯度相關(guān)的下降方向hd=-Hdg(yd)，其中Hd是由L-BFGS算法產(chǎn)生的迭代矩陣且是對稱正定的。由Rayleigh商、范數(shù)定義及其相融性可知

(7)

其中0<δ1≤δ2。

接下來利用Cayley變換[15]構(gòu)造的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)產(chǎn)生，那么結(jié)合式(9)、(10)可得如下迭代格式

(11)

和

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

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

和二階矩陣的求逆公式計(jì)算矩陣I+E的逆矩陣

從而定理得證。

(12)

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

從而

3 收斂性分析

在本小節(jié)中，首先證明了函數(shù)值序列{λd=f(yd)}的收斂性以及迭代序列{yd}的每個(gè)聚點(diǎn)都是一階穩(wěn)定點(diǎn)這一性質(zhì)，然后通過Lojasiewicz不等式說明迭代序列{yd}是收斂的，以及CEHT算法(computing eigenvalues of Hankel tensors)具有線性收斂速度。若算法CEHT在有限步迭代終止，即存在迭代步d有g(shù)(yd)=0，則由定理1可知λd=f(yd)是Hankel張量 所求特征值，yd是對應(yīng)的特征向量。序列{yd}是由算法CEHT產(chǎn)生的無限迭代序列。

引理2[3]存在常數(shù)K>1有

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

引理3 存在一個(gè)常數(shù)τmin>0，對任意的迭代步d，τd都有

τmin≤τd≤1。

和

那么有

將函數(shù)f(y)在點(diǎn)yd處進(jìn)行泰勒展開，通過式(6)、(11)及引理2可得如下不等式

接下來證明迭代序列{yd}的每個(gè)聚點(diǎn)都是一階穩(wěn)定點(diǎn)。

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

即

從而定理得證。

在證明迭代序列{yd}收斂之前，先給出Lojasiewicz不等式和強(qiáng)下降條件。

定理5(Lojasiewicz不等式) 若yd是迭代序列{yd}的臨界點(diǎn)，則存在ν∈[0，1)，正數(shù)δ3以及y*的一個(gè)鄰域Ω(y*)有

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

(14)

定義2 若序列{yd}∈Rn符合下列條件，則該序列滿足強(qiáng)下降條件。

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

(15)

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

(16)

在此ξ>0。

定理6 若迭代序列{yd}是由CEHT算法產(chǎn)生的，那么可以找到一點(diǎn)yd∈Sn-1滿足

證明 由于式(4)中的f(y)滿足Lojasiewicz不等式，根據(jù)引理4，則只需證明其滿足定義2中的強(qiáng)下降條件即可。

從式(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 假設(shè)y*是迭代序列{yd}的一個(gè)聚點(diǎn)，若初始點(diǎn)y1∈Bρ(y*)?Ω(y*)滿足下列不等式

(18)

那么可得

(19)

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

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

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

(20)

定理7 假設(shè)y*是迭代序列{yd}的一個(gè)穩(wěn)定點(diǎn)，那么有下列條件成立

‖yd-y*‖≤?εd

(21)

(22)

(23)

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

?=‖y1-y*‖>0，式(21)得證。

式(23)得證。