基于Tensor Train分解的Sylvester張量方程求解

吳玉倩，陳 榮，陳中明

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

0 引 言

Sylvester張量方程是一類重要的張量優(yōu)化問題，廣泛應(yīng)用于控制系統(tǒng)、圖像處理、模型降階和流體力學(xué)等領(lǐng)域。文獻(xiàn)[1]在求解熱輻射領(lǐng)域的三維輻射傳遞方程時，采用Chebyshev配置點譜方法進(jìn)行離散化，并提出了三階Sylvester張量方程，給出一種基于Schur分解的直接解法。文獻(xiàn)[2]給出了一種預(yù)處理迭代法。目前已有的一些用于求解Sylvester張量方程的方法，如Schur分解法、Krylov子空間法[3]等，往往需要直接存儲整個張量數(shù)據(jù)，其元素個數(shù)隨著階數(shù)呈指數(shù)增長，在求解高階Sylvester方程時，這些算法面臨巨大的存儲量和計算量等問題[4]。為此，本文提出一種基于Tensor Train分解的交替隨機(jī)梯度下降法，有效降低了計算復(fù)雜度。

1 問題模型

本文中，Sylvester張量方程如下：

(1)

(i1…ik…id

當(dāng)d=2時，方程(1)退化為Sylvester矩陣方程

AX+XBT=C

2 TT分解

vec()=G1,G2,…,Gd

下面介紹本文用到的相關(guān)定義和性質(zhì)，更多有關(guān)張量TT分解的運(yùn)算，包括張量加法、范數(shù)等參見文獻(xiàn)[5]。

Pk+1=(Ink?Pk)reshape(Gk,rk-1nk,rk)(Ink?Pk)Lk

3 交替隨機(jī)梯度下降法

本文提出的交替隨機(jī)梯度下降法(簡稱TT-SGD)，采用隨機(jī)采樣的思想。首先，運(yùn)用張量TT格式下的模乘運(yùn)算，將方程(1)左邊轉(zhuǎn)化為TT格式；然后，運(yùn)用交替最小二乘法(Alternating Least Squares Method，ALS)依次更新TT核，并得到子問題；最后，對子問題中的系數(shù)矩陣進(jìn)行隨機(jī)采樣。關(guān)于TT格式下ALS方法的收斂性分析可參考文獻(xiàn)[7]。

將式(1)向量化后，轉(zhuǎn)化為求解最小二乘問題，得到：

(2)

A=Ind?…?In2?A(1)+…+A(d)?Ind-1?…?In1

其中，gk=vec(Gk)∈Rrk-1nkrk。在ALS中，分別固定d-1個核G1,…,Gk-1,Gk+1,…,Gd，依次更新核Gk，相應(yīng)子問題的目標(biāo)函數(shù)可寫成：

(3)

由定義可知，當(dāng)階數(shù)d很大時，無法直接計算梯度fk(gk)，于是考慮對Hk的行進(jìn)行隨機(jī)采樣。首先，給出矩陣Hk另一種等價形式。對于式(1)，令

于是有:

由此，得到關(guān)于gk=vec(Gk)系數(shù)矩陣的另一種等價表示

(4)

(5)

(6)

(7)

TT-SGD具體流程如下。

輸入:矩陣{A(k)}dk=1,張量,采樣數(shù)NS,TT秩{rk}dk=0,相對誤差ω=1,算法精度0<ε<1輸出:構(gòu)成張量的TT核{(lán)Gk}dk=1初始化右正交化核{(lán)Gk}dk=2while ω>ε 隨機(jī)采樣得到指標(biāo)向量集S,按式(6)從右往左計算采樣矩陣Qk,1和Qk,2 for k=1,2,…,d 根據(jù)式(4)計算采樣系數(shù)矩陣Hk,再根據(jù)式(7)計算隨機(jī)梯度?fk(gk) 更新gk←gk-α?fk(gk),并左正交化核Gk 根據(jù)式(5)計算采樣矩陣Pk,1和Pk,2 end 計算相對誤差ω=Hkx-c22/c22end輸出核Gk(k=1,2,…,d)

4 收斂性分析

在第t步迭代更新TT核Gk中，相應(yīng)子問題(3)的目標(biāo)函數(shù)記為：

對式(2)中的函數(shù)f(x)做出如下假設(shè)：

于是有

(8)

式中，δ是系數(shù)矩陣A的最大奇異值。

(9)

(10)

設(shè)f*是f(x)的最優(yōu)值，故E[f(x(T))]≥f*，于是有:

令αt=1/(t+1)，當(dāng)?shù)綌?shù)T趨向無窮大時，有:

證畢。

5 數(shù)值實驗

(11)

圖1 相對誤差隨迭代次數(shù)變化情況

從圖1可以看出，由于采用隨機(jī)梯度，相對誤差并非單調(diào)下降，但隨著迭代次數(shù)增加，相對誤差逐漸趨于穩(wěn)定，并達(dá)到給定精度，TT-SGD算法收斂。

表1 不同精度下不同算法的運(yùn)行時間 單位：s

從表1可以看出，與PM-BTF算法相比，TT-SGD算法達(dá)到相同精度所需的運(yùn)行時間更短；且隨著算法精度的提高，2種算法運(yùn)行時間的差距更大，TT-SGD算法的優(yōu)勢更明顯。因為PM-BTF算法直接處理張量數(shù)據(jù)，而TT-SGD算法采用隨機(jī)梯度交替更新TT核，有效降低了算法的復(fù)雜度。

6 結(jié)束語

針對Sylvester張量方程，本文提出一種基于TT分解的交替隨機(jī)梯度下降法。運(yùn)用TT格式緊湊的形式，有效降低了算法的存儲和計算復(fù)雜度，通過對子問題中系數(shù)矩陣的隨機(jī)采樣，實現(xiàn)了大規(guī)模問題的求解。下一步將針對更有效的隨機(jī)采樣方法展開研究。