低秩張量填充的循環算法

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

(1.太原師范學院數學與統計學院，晉中 030619;2.智能優化計算與區塊鏈技術山西省重點實驗室，晉中 030619;3.北京交通大學數學與統計學院，北京 100044)

0 引言

張量填充問題是張量研究中最活躍的熱點之一。張量填充可以應用于很多領域，如圖像恢復[1–2]、信號處理、數據挖掘[3]、機器學習[4]、圖像壓縮、高階網絡鏈接分析[5]等。張量填充問題可以表述為

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

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

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

本文主要研究張量填充問題，基于交替方向乘子法以及子問題循環更新的思想，提出了一種新的張量填充算法，并討論了該算法的收斂性。通過數值實驗，驗證了新算法的有效性。

本文的結構安排如下：第1 節介紹張量及矩陣的相關符號說明和定義；第2 節基于交替方向乘子法，運用子問題循環更新的思想，給出了低秩張量填充的循環算法；第3 節給出算法的收斂性分析；第4 節通過數值實驗將新算法與HaLRTC 算法、DR-TR 算法及LRTC-Logdet 算法進行了比較；最后，第5 節對全文進行總結。

1 符號說明和定義

本節給出矩陣和張量的相關符號說明及定義。

定義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，對X進行張量奇異值分解(T-SVD)，X=U·S·VT，S中非零奇異管的數量稱為張量X的Tubal 秩。

定義3(張量展開)[12]張量展開，又稱張量矩陣化，是將張量按照一定規律重新排序為矩陣。張量X ∈RI1×I2×···×IN的模-k展開表示為

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

2 算法

在這一節中，主要研究張量填充算法。在迭代過程中，通過對子問題的循環更新，減少了在迭代過程中張量展開、矩陣折疊以及奇異值分解的計算花費。

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

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

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

不失一般性，考慮函數

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

3 收斂性分析

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

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

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

其中l{i=Rk+1}為指示函數，即當i=Rk+1時，l{i=Rk+1}=1，否則等于0。

對于給定的參數γi(ρi)及γ，L({Xi},A,{Yi})是分別關于Xi和A的強凸函數。由強凸函數的性質，可得

由子問題的最優性條件，有

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

若i/=Rk+1，則根據

定理1 若假設1 至假設3 成立，則有

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

4 數值實驗

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

4.1 隨機張量填充

通過隨機產生的張量進行算法比較，隨機張量通過張量的Tucker 分解生成

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

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

表1 至表3 為不同采樣率下新算法與HaLRTC 算法、DR-TR 算法及LRTC-Logdet 算法的張量填充的實驗結果，從表1 至表3 可以看出，在滿足誤差估計條件下，新算法在時間花費上要明顯優于HaLRTC 算法、DR-TR 算法及LRTC-Logdet 算法，體現出新算法的優越性。

表1 當p=0.2 時，新算法LRTCC 與HaLRTC、DR-TR 和LRTC-Logdet 的比較

表2 當p=0.3 時，新算法LRTCC 與HaLRTC、DR-TR 和LRTC-Logdet 的比較

表3 當p=0.4 時，新算法LRTCC 與HaLRTC、DR-TR 和LRTC-Logdet 的比較

4.2 圖像修復

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

圖1 原始切片圖像

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

圖3 LRTCC 算法修復的圖像

圖4 HaLRTC 算法修復的圖像

圖5 DR-TR 算法修復的圖像

圖6 LRTC-Logdet 算法修復的圖像

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

其中n表示張量中像素的個數，Tmax表示原始張量的最大像素值。

從表4 中可看出，新算法的時間花費最少，且峰值信噪比值要高于HaLRTC 算法、DR-TR 算法及LRTC-Logdet 算法，進一步驗證了新算法的有效性。

5 結論

本文提出了一種新的低秩張量填充算法。該算法基于交替方向乘子法框架，對子問題采取循環更新的方法，減少了在迭代過程中張量展開、矩陣折疊及奇異值分解的計算花費。通過隨機張量填充和圖像修復試驗與HaLRTC 算法、DR-TR 算法及LRTCLogdet 算法進行對比，新算法顯示出較強的優越性。