低秩張量填充的循環(huán)算法

王俊霞, 郭雄偉, 王川龍,

(1.太原師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，晉中 030619;2.智能優(yōu)化計(jì)算與區(qū)塊鏈技術(shù)山西省重點(diǎn)實(shí)驗(yàn)室，晉中 030619;3.北京交通大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，北京 100044)

0 引言

張量填充問(wèn)題是張量研究中最活躍的熱點(diǎn)之一。張量填充可以應(yīng)用于很多領(lǐng)域，如圖像恢復(fù)[1–2]、信號(hào)處理、數(shù)據(jù)挖掘[3]、機(jī)器學(xué)習(xí)[4]、圖像壓縮、高階網(wǎng)絡(luò)鏈接分析[5]等。張量填充問(wèn)題可以表述為

其中A和T都是N-模張量，且每個(gè)模的大小相同，rank(A)表示張量A的某種秩，P?是集合?上的正交投影，?是基數(shù)等于m的隨機(jī)子集，其中m是采樣元素的個(gè)數(shù)。所以，當(dāng)(i1,i2,···,iN)∈?時(shí)，P?(A)的第(i1,i2,···,iN)個(gè)元素等于Ti1i2···iN，否則等于0。關(guān)于張量的秩的定義并不唯一，如有基于張量Tucker 分解定義的Tucker 秩，基于張量CP 分解定義的CP 秩，Tubal 秩等，并且張量的秩的計(jì)算是NP-難問(wèn)題。Liu 等人[6]首次提出張量核范數(shù)的定義，并將模型(1)轉(zhuǎn)化為

在張量填充的優(yōu)化算法方面，已有一些研究成果。文獻(xiàn)[6]中，Liu 等人給出了張量的核范數(shù)的定義，并基于模型(2)提出了三種有效算法：簡(jiǎn)單低秩張量填充算法(Simple Low Rank Tensor Completion algorithm, SiLRTC)、快速低秩張量填充算法(Fast Low Rank Tensor Completion algorithm, FaLRTC)以及高精度低秩張量填充算法(High accuracy Low Rank Tensor Completion algorithm,HaLRTC)。在文獻(xiàn)[7]中，Gandy 等人用張量的秩作為稀疏表示，將其模型轉(zhuǎn)換為更容易求解的凸模型，提出了張量恢復(fù)的Douglas-Rachford 分離算法以及交替方向乘子法。Ji 等人[8]基于文獻(xiàn)[9]，用非凸光滑能量函數(shù)logdet(X+εE)替代了張量的秩，提出了如下模型

其中Ei ∈RIi×Ii為單位矩陣，并提出了一種新的求解低秩張量填充問(wèn)題的算法(LRTCLogdet)。受矩陣填充算法的啟發(fā)，Tan 等人[10]將張量填充問(wèn)題化為矩陣填充問(wèn)題，提出了低多線性秩張量填充算法。為了保持張量原有的內(nèi)部結(jié)構(gòu)以及避免矩陣化的計(jì)算花費(fèi)，Kilmer 和Martin[11]提出了張量的奇異值分解，且能夠很好的保留張量原有的內(nèi)部結(jié)構(gòu)信息?；趶埩康钠娈愔捣纸夂蚑ubal 秩的定義，Zhang 等人[12]利用交替方向乘子法框架，給出了相應(yīng)的算法。此外，還有很多學(xué)者研究張量的CP 秩以及基于CP 秩的張量填充算法，詳見(jiàn)文獻(xiàn)[13–14]。

本文主要研究張量填充問(wèn)題，基于交替方向乘子法以及子問(wèn)題循環(huán)更新的思想，提出了一種新的張量填充算法，并討論了該算法的收斂性。通過(guò)數(shù)值實(shí)驗(yàn)，驗(yàn)證了新算法的有效性。

本文的結(jié)構(gòu)安排如下：第1 節(jié)介紹張量及矩陣的相關(guān)符號(hào)說(shuō)明和定義；第2 節(jié)基于交替方向乘子法，運(yùn)用子問(wèn)題循環(huán)更新的思想，給出了低秩張量填充的循環(huán)算法；第3 節(jié)給出算法的收斂性分析；第4 節(jié)通過(guò)數(shù)值實(shí)驗(yàn)將新算法與HaLRTC 算法、DR-TR 算法及LRTC-Logdet 算法進(jìn)行了比較；最后，第5 節(jié)對(duì)全文進(jìn)行總結(jié)。

1 符號(hào)說(shuō)明和定義

本節(jié)給出矩陣和張量的相關(guān)符號(hào)說(shuō)明及定義。

定義1(奇異值分解)[15]秩為r的矩陣X ∈Rn1×n2的奇異值分解(Singular Value Decomposition, SVD)為

其中U ∈Rn1×r和V ∈Rn2×r是列正交矩陣，σ1≥σ2≥···≥σr ＞0。

定義2(張量的Tubal 秩)[12]X ∈RI1×I2×I3，對(duì)X進(jìn)行張量奇異值分解(T-SVD)，X=U·S·VT，S中非零奇異管的數(shù)量稱為張量X的Tubal 秩。

定義3(張量展開(kāi))[12]張量展開(kāi)，又稱張量矩陣化，是將張量按照一定規(guī)律重新排序?yàn)榫仃嚒埩縓 ∈RI1×I2×···×IN的模-k展開(kāi)表示為

與其相反的運(yùn)算定義為foldk(X(k))=X。

2 算法

在這一節(jié)中，主要研究張量填充算法。在迭代過(guò)程中，通過(guò)對(duì)子問(wèn)題的循環(huán)更新，減少了在迭代過(guò)程中張量展開(kāi)、矩陣折疊以及奇異值分解的計(jì)算花費(fèi)。

張量填充模型(3)的增廣拉格朗日函數(shù)為

算法1 低秩張量填充循環(huán)算法(Low Rank Tensor Completion Cyclic algorithm,簡(jiǎn)稱LRTCC)

引理1 給定矩陣X ∈Rm×n，考慮如下問(wèn)題

不失一般性，考慮函數(shù)

其中ε+wi ＞0。令g(wi) = (wi ?ΣX(i,i))(ε+wi)+τ，利用原函數(shù)與其一階導(dǎo)數(shù)的關(guān)系，得證。

3 收斂性分析

基于文獻(xiàn)[16]提出的關(guān)于交替方向乘子非凸問(wèn)題的收斂性分析，在合理的假設(shè)條件下，證明了算法的收斂性。

為表述方便，用s(i)表示變量Xi在第k+1 次迭代前最新的一次迭代。

假設(shè)1 給定張量X,Z ∈RI1×I2×···×IN,?i=1,2,···,N，存在常數(shù)Li，滿足

其中l(wèi){i=Rk+1}為指示函數(shù)，即當(dāng)i=Rk+1時(shí)，l{i=Rk+1}=1，否則等于0。

對(duì)于給定的參數(shù)γi(ρi)及γ，L({Xi},A,{Yi})是分別關(guān)于Xi和A的強(qiáng)凸函數(shù)。由強(qiáng)凸函數(shù)的性質(zhì)，可得

由子問(wèn)題的最優(yōu)性條件，有

上式中，Li是一個(gè)常數(shù)，ρiγi(ρi)是單調(diào)遞增的。因此，總可以找到一個(gè)足夠大的ρi，使得ρiγi(ρi)≥2L2i,?i=1,2,···,N成立。此時(shí)，拉格朗日函數(shù)為單調(diào)遞減函數(shù)。

若i/=Rk+1，則根據(jù)

定理1 若假設(shè)1 至假設(shè)3 成立，則有

由于M=N是有限的，且有

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

在本節(jié)中，通過(guò)隨機(jī)張量填充及圖像修復(fù)，將低秩張量填充循環(huán)算法與HaLRTC 算法、DR-TR 算法及LRTC-Logdet 算法進(jìn)行比較。所有的數(shù)值實(shí)驗(yàn)均在Intel(R)Core(TM)i5-1135G7@2.40 GHz，內(nèi)存16.0 GB，Windows 10 系統(tǒng)下進(jìn)行，程序在Matlab R2013a上實(shí)現(xiàn)。算法1 的參數(shù)設(shè)置為αi= 1/N,ρi= 10?7,εi= 0.01,t= 1.1,τ=10?7。HaLRTC 算法的參數(shù)設(shè)置與算法1 相同，DR-TR 算法與LRTC-Logdet 算法的參數(shù)，除τ=10?7以外，其余參數(shù)分別采取文獻(xiàn)[7]和文獻(xiàn)[8]的建議。

4.1 隨機(jī)張量填充

通過(guò)隨機(jī)產(chǎn)生的張量進(jìn)行算法比較，隨機(jī)張量通過(guò)張量的Tucker 分解生成

其中G ∈Rr1×r2×···×rN是核張量，Un ∈RIn×rn,n= 1,2,···,N為矩陣。實(shí)驗(yàn)中，核張量G和矩陣Un由Matlab 中命令randn(r1,r2,···,rN)和randn(rn,In)生成。因此，這樣生成的隨機(jī)張量T ∈RI1×I2×···×IN的秩為(r1,r2,···,rN)。

其中T和A分別表示原始張量和算法輸出的最優(yōu)解。

表1 至表3 為不同采樣率下新算法與HaLRTC 算法、DR-TR 算法及LRTC-Logdet 算法的張量填充的實(shí)驗(yàn)結(jié)果，從表1 至表3 可以看出，在滿足誤差估計(jì)條件下，新算法在時(shí)間花費(fèi)上要明顯優(yōu)于HaLRTC 算法、DR-TR 算法及LRTC-Logdet 算法，體現(xiàn)出新算法的優(yōu)越性。

表1 當(dāng)p=0.2 時(shí)，新算法LRTCC 與HaLRTC、DR-TR 和LRTC-Logdet 的比較

表2 當(dāng)p=0.3 時(shí)，新算法LRTCC 與HaLRTC、DR-TR 和LRTC-Logdet 的比較

表3 當(dāng)p=0.4 時(shí)，新算法LRTCC 與HaLRTC、DR-TR 和LRTC-Logdet 的比較

4.2 圖像修復(fù)

使用維數(shù)為181×217×181 的MRI 數(shù)據(jù)比較新算法與HaLRTC 算法、DR-TR 算法及LRTC-Logdet 算法的圖像填充效果。為展示其填充效果，隨機(jī)選取MRI 的某一正向切片，在不同采樣率的情況下，其填充效果圖見(jiàn)圖1 至圖6。其中圖1 為原始切片圖像，圖2(a)、圖2(b)和圖2(c)分別為采樣0.2、0.3 和0.4 的圖像，圖3 為L(zhǎng)RTCC 算法修復(fù)的圖像，圖4 為HaLRTC 算法修復(fù)的圖像，圖5 為DR-TR 算法修復(fù)的圖像，圖6 為L(zhǎng)RTCLogdet 算法修復(fù)的圖像。從圖1 至圖6 可看出，在不同采樣率下，四種算法都有較好的圖像填充效果。為了體現(xiàn)新算法在時(shí)間花費(fèi)上的優(yōu)勢(shì)，在表4 中給出了圖像填充的時(shí)間花費(fèi)，并用峰值信噪比(Peak Signal to Noise Ratio, PSNR)體現(xiàn)填充效果，其表達(dá)式為

圖1 原始切片圖像

圖2 采樣0.2、0.3 和0.4 的圖像

圖3 LRTCC 算法修復(fù)的圖像

圖4 HaLRTC 算法修復(fù)的圖像

圖5 DR-TR 算法修復(fù)的圖像

圖6 LRTC-Logdet 算法修復(fù)的圖像

表4 MRI 在不同采樣率下的算法比較

其中n表示張量中像素的個(gè)數(shù)，Tmax表示原始張量的最大像素值。

從表4 中可看出，新算法的時(shí)間花費(fèi)最少，且峰值信噪比值要高于HaLRTC 算法、DR-TR 算法及LRTC-Logdet 算法，進(jìn)一步驗(yàn)證了新算法的有效性。

5 結(jié)論

本文提出了一種新的低秩張量填充算法。該算法基于交替方向乘子法框架，對(duì)子問(wèn)題采取循環(huán)更新的方法，減少了在迭代過(guò)程中張量展開(kāi)、矩陣折疊及奇異值分解的計(jì)算花費(fèi)。通過(guò)隨機(jī)張量填充和圖像修復(fù)試驗(yàn)與HaLRTC 算法、DR-TR 算法及LRTCLogdet 算法進(jìn)行對(duì)比，新算法顯示出較強(qiáng)的優(yōu)越性。