基于張量環(huán)分解的非精確的低秩填充算法

孟翔宇，溫瑞萍

(1.工程科學(xué)計(jì)算山西省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室,山西 晉中 030619；2.太原師范學(xué)院 數(shù)學(xué)系，山西 晉中 030619)

0 引言

大規(guī)模數(shù)據(jù)通常以泛數(shù)組的張量形式存儲(chǔ)，在信號(hào)處理[1]、數(shù)據(jù)挖掘[2]、計(jì)算機(jī)視覺(jué)[3]以及模式識(shí)別[4]等領(lǐng)域都有廣泛運(yùn)用.而在采集、存儲(chǔ)、傳輸、處理高維數(shù)據(jù)等環(huán)節(jié)，往往會(huì)造成數(shù)據(jù)丟失.因此，數(shù)據(jù)填充是必不可少的.現(xiàn)實(shí)生活的數(shù)據(jù)之間往往是有關(guān)聯(lián)性的，所以存放數(shù)據(jù)的張量就表現(xiàn)為低秩[5].利用數(shù)據(jù)間的關(guān)聯(lián)性可以由已知的數(shù)據(jù)信息去估計(jì)未知或丟失的數(shù)據(jù)信息，也就是利用低秩張量填充去實(shí)現(xiàn)數(shù)據(jù)恢復(fù).

一般的低秩張量填充模型如下:

(1)

張量分解是研究張量填充問(wèn)題的關(guān)鍵.目前已知的張量分解模型有基于CP(Canonical Polyadic)秩的張量分解模型[6]，基于Tucker秩的張量分解模型[7]，基于矩陣乘積態(tài)/張量鏈?zhǔn)椒纸?tensor train/matrix product states)[8]的模型，還有在張量鏈?zhǔn)椒纸獾幕A(chǔ)上進(jìn)行改進(jìn)的基于張量環(huán)分解的模型[9]，以及新的全連接張量網(wǎng)絡(luò)分解模型[10]等.

在以上分解模型的基礎(chǔ)上，常見(jiàn)的張量填充問(wèn)題的優(yōu)化算法有：文獻(xiàn)[11]中提出利用塊坐標(biāo)下降的方法求得全局最優(yōu)解的簡(jiǎn)單低秩張量填充算法(SiLRTC);將原始非光滑問(wèn)題轉(zhuǎn)變?yōu)楣饣瑔?wèn)題的快速低秩張量填充算法(FaLRTC); 文獻(xiàn)[12]提出一種將n維張量填充模型展成n個(gè)矩陣填充的問(wèn)題，再將求解得到的矩陣恢復(fù)成張量的低秩多線性張量填充模型(LMRTC).文獻(xiàn)[13]提出的利用塊坐標(biāo)下降實(shí)現(xiàn)分別求解的加速近端梯度算法等.

本文主要基于文獻(xiàn)[14]張量環(huán)分解的低秩填充算法，提出一種非精確的填充方法，與文獻(xiàn)[14]算法相比，本文特點(diǎn)是不要求找到每一步迭代的最優(yōu)解，只保證迭代整體下降.最后通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的有效性.

1 預(yù)備知識(shí)

(2)

(3)

(4)

定義3(張量模-kcanonical矩陣化)[9，16]∈(I1×…×In)按第k-模展開(kāi)的矩陣為則

(5)

(6)

2 相關(guān)算法

基于張量環(huán)分解的低秩張量填充有兩個(gè)途徑[16].第一種是直接基于張量環(huán)分解，需要預(yù)先給定秩來(lái)實(shí)現(xiàn)低秩; 另一種是在張量環(huán)分解的基礎(chǔ)上約束秩最小，所以需要通過(guò)凸松弛秩函數(shù)來(lái)實(shí)現(xiàn)低秩.在這一節(jié)，我們沿著途徑二進(jìn)行研究，在原始優(yōu)化模型基礎(chǔ)上，添加秩函數(shù)正則化項(xiàng)，實(shí)現(xiàn)低秩張量填充.

2.1 問(wèn)題描述

基于張量環(huán)分解的張量填充模型如下:

(7)

式(7)添加秩函數(shù)正則化項(xiàng)，

(8)

為了方便找到它的最優(yōu)解，將秩函數(shù)凸松弛為張量的核范數(shù).文獻(xiàn)[17]中將填充張量的秩定義為其模-k展開(kāi)秩的和，

(9)

文獻(xiàn)[14]中利用張量秩和所對(duì)應(yīng)張量核秩的關(guān)系提出了一種新的模型，通過(guò)張量核因子的模-2展開(kāi)的核范數(shù)來(lái)刻畫低秩，再考慮對(duì)TR核因子的低秩約束，得到模型(10)，

(10)

(11)

對(duì)式(11)使用增廣拉格朗日函數(shù)進(jìn)行處理得到模型(12)，實(shí)現(xiàn)交替方向分步求解.

(12)

2.2 相關(guān)算法

為了提高計(jì)算的速度，每一步迭代不需要求到最好的下降效果，只要保證整體下降即可.于是我們利用張量核因子存儲(chǔ)信息的2-模展開(kāi)來(lái)代替控制結(jié)構(gòu)的1-模和3-模.根據(jù)模型(12)得到了非精確的TRLRF算法.

3 數(shù)值實(shí)驗(yàn)

本節(jié)將通過(guò)數(shù)值實(shí)驗(yàn)來(lái)驗(yàn)證本文算法的有效性.所有數(shù)值實(shí)驗(yàn)均在處理器為Intel(R) Core(TM)i7-3770 CPU @ 3.40 GHz的Windows 10系統(tǒng)的計(jì)算機(jī)上利用Matlab(R2019b)運(yùn)行.在圖像填充實(shí)驗(yàn)中，選擇一張大小為509×609×3遙感圖像，一張?jiān)?003年ICCV會(huì)議上的圖像數(shù)據(jù)集里大小為256×384×3的建筑圖像以及一小段yuv格式的視頻大小為144×176×3×10 進(jìn)行實(shí)驗(yàn)驗(yàn)證(見(jiàn)圖1).實(shí)驗(yàn)結(jié)果見(jiàn)表1、表2、表3.

圖1 分辨率為(176×144)的Qcif視頻轉(zhuǎn)化為10幀大小為(144×176×3)的圖像

遙感圖像(509×609×3)缺失率TR秩算法迭代次數(shù)運(yùn)行時(shí)間RES(相對(duì)平方誤差)0.66×6×60.69×9×90.8 6×6×60.8 9×9×9TRLRF8312.972 40.093ieTRLRF284.403 70.102TRLRF7925.766 40.089ieTRLRF5116.579 40.100TRLRF12426.065 60.120ieTRLRF408.230 00.125TRLRF5521.937 70.120ieTRLRF3012.369 60.123

表2 TRLRF與ieTRLRF實(shí)驗(yàn)數(shù)據(jù)比較

表3 TRLRF與ieTRLRF實(shí)驗(yàn)數(shù)據(jù)比較

從實(shí)驗(yàn)結(jié)果可以看出在圖像像素缺失率為0.6以及0.8的情況下，非精確的低秩填充算法(ieTRLRF)與精確(TRLRF)算法相比，填充效果一致，但是在耗費(fèi)時(shí)間上TRLRF是ieTRLRF算法的近三倍.除此之外，兩種算法的相對(duì)平方誤差相差不大并且ieTRLRF算法的迭代次數(shù)遠(yuǎn)遠(yuǎn)少于TRLRF算法的迭代次數(shù)．這些都說(shuō)明本文算法的有效性和可行性.

4 總結(jié)

本文提出了一種非精確的基于張量環(huán)分解的低秩填充算法.它不要求每次迭代下降取最優(yōu)，只考慮整體下降.利用張量核因子中起到存儲(chǔ)信息的模-2展開(kāi)來(lái)代替控制結(jié)構(gòu)的模-1和模-3.在保證填充效果差異很小的情況下，減少了計(jì)算時(shí)間，提高了填充效率.最后通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證了本文的算法能夠較好地填充缺失數(shù)據(jù)，充分證明了本文算法的有效性.