低秩張量補(bǔ)全算法綜述

劉慧梅，　史加榮

(西安建筑科技大學(xué) 理學(xué)院， 陜西 西安 710055)

?

低秩張量補(bǔ)全算法綜述

劉慧梅，史加榮

(西安建筑科技大學(xué) 理學(xué)院， 陜西 西安 710055)

[摘要]隨著現(xiàn)代信息技術(shù)的快速發(fā)展，待分析的數(shù)據(jù)大都具有很復(fù)雜的結(jié)構(gòu)。在獲取高維多線性數(shù)據(jù)的過程中，部分元素可能丟失，低秩張量補(bǔ)全就是根據(jù)數(shù)據(jù)集的低秩性質(zhì)來恢復(fù)出所有丟失元素。低秩張量補(bǔ)全是壓縮感知理論的高階推廣，在數(shù)學(xué)上可以描述為核范數(shù)最小化問題。對求解低秩張量補(bǔ)全的核范數(shù)最小化模型的現(xiàn)有算法進(jìn)行了綜述。介紹了張量的基礎(chǔ)知識和低秩張量補(bǔ)全模型，給出了低秩張量補(bǔ)全的幾種主流算法，如：簡單低秩張量補(bǔ)全、高精度低秩張量補(bǔ)全以及核心張量核范數(shù)的張量補(bǔ)全等，指出了現(xiàn)有低秩張量補(bǔ)全算法中值得研究與改進(jìn)的方向。

[關(guān)鍵詞]張量補(bǔ)全；低秩；核范數(shù)最小化；核心張量核范數(shù)；交替方向乘子法

隨著傳感器和存儲技術(shù)的快速發(fā)展，高階數(shù)據(jù)分析已經(jīng)應(yīng)用到信號處理、計算機(jī)視覺和數(shù)據(jù)挖掘等領(lǐng)域。低秩矩陣補(bǔ)全(Low Rank Matrix Completion，LRMC)和低秩矩陣恢復(fù)(Low Rank Matrix Recovery，LRMR)已成為數(shù)據(jù)分析與處理的研究熱點[1-3]，且矩陣秩最小化具有很強(qiáng)的全局約束能力，能很好地刻畫出矩陣二維的稀疏性。然而，實際待分析的高維數(shù)據(jù)往往具有復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，如：彩色圖像、視頻序列和多光譜圖像等。傳統(tǒng)的數(shù)據(jù)表示形式為向量和矩陣，不能很好地刻畫這些數(shù)據(jù)的多線性結(jié)構(gòu)。作為向量和矩陣的高階推廣，張量能夠很好地表達(dá)高階數(shù)據(jù)復(fù)雜的本質(zhì)結(jié)構(gòu)。

實際應(yīng)用中的高維數(shù)據(jù)一般具有較低的本征維數(shù)，也就是說它們是低秩或近似低秩的。在獲取高維數(shù)據(jù)的過程中，某些元素可能丟失，如何利用已知數(shù)據(jù)元素的信息來恢復(fù)出那些丟失的元素，這個任務(wù)被稱為低秩張量補(bǔ)全(Low Rank Tensor Completion，LRTC)問題。Liu等人[4]指出LRTC能夠充分利用數(shù)據(jù)所有維的信息，而LRMC僅僅利用數(shù)據(jù)的兩維信息。張量補(bǔ)全現(xiàn)已被成功應(yīng)用到計算機(jī)視覺[4]、EEG[5-6]和超光譜[7-8]等數(shù)據(jù)的處理中。

近年來，Liu[4,9]和Candy[8]等學(xué)者對LRTC算法進(jìn)行了大量的研究且已取得顯著成果。一般而言，對LRTC模型的求解方法主要分為三大類：第一類是把LRMC問題的秩最小化框架擴(kuò)展延伸到LRTC問題中，即張量低n-秩最小化框架，此方法得到了很多學(xué)者的青睞；第二類是應(yīng)用張量代數(shù)的思想來解決LRTC問題，如文獻(xiàn)[10-11]提出的Tucker逼近的張量補(bǔ)全算法；第三類是應(yīng)用流形的思想解決LRTC問題，如Kressner等人[12]提出的張量補(bǔ)全非線性集合CG算法。本文主要對第一類LRTC算法進(jìn)行綜述。

1基本知識

本節(jié)介紹一些矩陣與張量代數(shù)的基本知識。用大寫斜體字母表示矩陣(如：X)，小寫字母表示向量(如：x)，用Euclid字母表示張量(如：X)。令X∈RI1×I2×…×IN是一個維數(shù)為I1×I2×…×IN的N階張量，它的(i1，…，iN)元素為xi1…iN，其中I1，…，IN為正整數(shù)。

2低秩張量補(bǔ)全模型及算法

2.1問題描述

Liu[4]和Candy[8]等人提出的低秩張量補(bǔ)全模型可表示為下列最優(yōu)化模型：

(1)

其中rank(X(n))為張量X的n-模式秩，T∈RI1×I2×…×IN，Ω表示采樣指標(biāo)集合。不幸的是，問題(1)是NP難的。由于矩陣核范數(shù)是秩函數(shù)的凸包絡(luò)[17]，所以可對模型(1)進(jìn)行凸松弛，得到張量核范數(shù)最小化模型：

(2)

下面綜述求解上述張量核范數(shù)最小化問題的幾種主流算法。

2.2簡單低秩張量補(bǔ)全算法

(3)

在模型(3)中，目標(biāo)函數(shù)關(guān)于M是可分離的，從而可進(jìn)一步轉(zhuǎn)化為下面含罰項的優(yōu)化問題：

(4)

其中λn>0。優(yōu)化問題(4)是凸的但非光滑，可采用塊坐標(biāo)下降法[19]進(jìn)行求解：對其中一個塊變量進(jìn)行優(yōu)化時，固定其余的塊變量。因此把最優(yōu)化問題(4)劃分為N+1個子優(yōu)化問題，并分別進(jìn)行求解。

當(dāng)更新X時，固定其它N個塊變量，求解下列最優(yōu)化問題：

(5)

易得此問題的最優(yōu)解為：

(6)

其中foldn(X(n))表示將矩陣X(n)重新合成張量X。

更新Mn時，需求解下列優(yōu)化問題：

(7)

簡單低秩張量補(bǔ)全算法(Simple Low Rank Tensor Completion，SiLRTC)[4]雖然很容易實現(xiàn)，但是在實際實施過程中會發(fā)現(xiàn)它的收斂速度比較慢。

2.3高精度低秩張量補(bǔ)全算法

(8)

模型(8)的增廣拉格朗日函數(shù)為：

(9)

更新M時，對于每個Mn(n=1，2，…，N)有

(10)

更新X時，只需求解如下子優(yōu)化問題：

(11)

式(11)是一個光滑可微的優(yōu)化問題，通過一階最優(yōu)性條件可得它的最優(yōu)解：

(12)

這里Ωc為Ω的補(bǔ)集。

Yn的更新： Yn:=Yn-λ(Mn-X)。

懲罰參數(shù)λ的更新：λ:=tλ，其中t>1。

高精度低秩張量補(bǔ)全算法(High Accuracy Low Rank Tensor Completion，HALRTC)[4]實質(zhì)上就是ADMM算法[8]。在實際的應(yīng)用中，HALRTC收斂速度較快且具有較高的精度。

2.4核心張量核范數(shù)的張量補(bǔ)全算法

由定理2可知：當(dāng)張量X的Tucker分解的模式矩陣Un屬于Stiefel流形[16]時，X的核范數(shù)與它的核心張量核范數(shù)等同。于是最優(yōu)化問題(2)可轉(zhuǎn)化為：

(13)

(14)

上式模型的部分增廣拉格朗日函數(shù)為：

(15)

更新V時，對于每個Vn(n=1，2，…，N)有：

(16)

更新C時：

(17)

更新U時，每個Un(n=1，2，…，N)只需通過求解下列優(yōu)化模型：

其一，PBL教學(xué)模式在調(diào)動高職院校學(xué)生英語口語訓(xùn)練動力與興趣方面的作用；其二，PBL教學(xué)模式在提高學(xué)生英語口語表達(dá)能力上的作用與具體表現(xiàn)；其三，PBL教學(xué)模式在提高學(xué)生綜合素質(zhì)方面的作用。

(18)

此模型對應(yīng)高階正交迭代(HOOI)分解[21]。通過每次迭代求解式(18)，更新每個Un(n=1，2，…，N)。為了簡便，采用非精確迭代策略，即對每個Un僅僅更新一次，則有如下更新公式：

(19)

其中算子SVD(rn,M(n))表示對矩陣M(n)進(jìn)行奇異值分解后，取其前rn個最大奇異值對應(yīng)的左奇異向量。

更新X時，需求解下列最優(yōu)化問題：

(20)

易得到上式(20)的解如下：

(21)

懲罰參數(shù)μ的更新規(guī)則與HALRTC算法中的λ的更新規(guī)則相同。

核心張量核范數(shù)的補(bǔ)全(Core Tensor Nuclear Norm Tensor Completion，CNNT)[17]算法是基于經(jīng)典的張量Tucker分解，并給最優(yōu)化問題(2)附加一定的條件，使得張量核范數(shù)和它的核心張量核范數(shù)相等，從而達(dá)到降低變量維數(shù)的目的。

2.5基于Parafac分解的因子矩陣核范數(shù)最小化張量補(bǔ)全算法

模型(2)應(yīng)用張量的另一經(jīng)典Parafac分解并松弛得：

(22)

(23)

式(23)的部分增廣拉格朗日函數(shù)為：

(24)

更新M時，對于每個變量Mn(n=1，2，…，N)有：

(25)

更新U時，對于每個Un(n=1，2，…，N)，需求解下列子優(yōu)化問題：

(26)

在求解(26)時，若A=V1°V2°…°VN，則A(n)=Vn(VN⊙…⊙Vn+1⊙Vn-1⊙…⊙V1)T，此處⊙為Khatri-Rao積[16]。令Bn=(UN⊙…⊙Un+1⊙Un-1⊙…⊙U1)T) ，則優(yōu)化問題(26)轉(zhuǎn)化為如下形式：

(27)

與CNNT算法相同，采用非精確更新策略，得到Un的閉形式解為：

(28)

其中I為單位矩陣。

更新X時，需求解如下優(yōu)化問題：

(29)

易得到優(yōu)化問題(29)的解為：

(30)

懲罰因子μ的更新規(guī)則與CNNT算法中的μ更新一致。

基于Parafac分解的因子矩陣核范數(shù)最小化張量補(bǔ)全算法(NNCP)[16]對張量的Parafac分解要求很高，所以并不適用于任一低秩張量補(bǔ)全模型。但是總的來說，這種模型可以降低時間復(fù)雜度。

2.6矩陣分解的張量補(bǔ)全算法

對于最優(yōu)化問題(2)，給出相應(yīng)矩陣分解的張量補(bǔ)全優(yōu)化模型[16,20]：

(31)

(32)

更新變量L和R時，對于每個Ln和Rn(n=1，2，…，N)，分別解下列子優(yōu)化問題：

(33)

(34)

通過解式(33)和(34)得變量Ln和Rn的閉形式解：

(35)

其中QR(·)表示對矩陣進(jìn)行QR分解。

更新變量X時，需求解

(36)

通過式(36)的一階最優(yōu)化條件，易得如下式的閉形式解：

(37)

矩陣分解的張量補(bǔ)全(Matrix Factorization Method for Tensor Completion，MFTC)[16]算法與前面綜述的CNNT算法和NNCP算法的目的都是為了降低計算復(fù)雜度。此算法不管是在精度上還是運行時間上都有明顯的優(yōu)越性。

上述幾種低秩張量補(bǔ)全算法主要通過秩極小化的框架來求解優(yōu)化問題(2)。當(dāng)然，除了前面我們綜述的這幾種算法外，還有其它算法值得關(guān)注，如：Shi等人[22]為了降低低秩張量補(bǔ)全算法的時間復(fù)雜度而提出基于Tuker分解的低秩張量補(bǔ)全算法，此算法通過采用瘦的QR分解來替代奇異值分解達(dá)到降低計算復(fù)雜度的目的；Kressner等人[12]提出基于黎曼流形的非線性集合CG算法，減少了大規(guī)模的奇異值的分解；Candy等人[8]提出基于Douglas-Rachford分離技術(shù)的張量補(bǔ)全算法，此算法考慮了噪聲的存在。由于篇幅問題，我們不再一一贅述。

3結(jié)束語

本文綜述了低秩張量補(bǔ)全模型的幾種求解算法，并評價了這些算法優(yōu)缺點。當(dāng)前，對LRTC的研究不管是在理論和算法上，還是在實際應(yīng)用上都處于初步研究階段。因此，對低秩張量補(bǔ)全算法的研究仍將是一個熱點。下面列出的幾方面在今后的研究中還需值得關(guān)注：(1)張量秩的上界估計，許多算法對于張量秩的上界的估計都是依經(jīng)驗給出，而如何使秩自學(xué)習(xí)給出是值得我們深究的；(2)低秩張量補(bǔ)全算法的求解基本上都需要計算每一模式展開的SVD，這項工作的計算復(fù)雜度是極其大的，如何降低這一計算復(fù)雜度的工作仍需努力；(3)現(xiàn)有算法基本上都地在假設(shè)不存在噪聲的情況下提出的，考慮數(shù)據(jù)中存在噪聲的低秩張量補(bǔ)全算法較少。

[參考文獻(xiàn)]

[1]CANDèS E J，LI Xiao-dong，MA Yi，et al.Robust principal component analysis？[J].Journal of ACM，2011，58(3)：1-37.

[2]CANDèS E J，RECHT B.Exact matrix completion via convex optimization[J].Foundations of Computational Mathematics，2008，9(6)：717-772.

[3]KESHAVAN R H，MONTANARI A.Matrix completion from noisy entries[J].Journal of Machine Learning Research，2010，11(3)：2057-2078.

[4]LIU Ji，MUSIALSKI P，WONKA P，et al.Tensor completion for estimating missing values in visual data[J].IEEE Translations on Pattern Analysis and Machine Intelligence，2013，35(1)：208-220.

[5]ACAR E，DUNLAVY D M，KOLDA T，et al.Scalable tensor factorization for incomplete data[J].Chemometrics and Intelligent Laboratory Systems，2011，106(1)：41-56.

[6]M?RUP M，HANSEN L K，HERRMANN C S，et al.Parallel factor analysis as an exploratory tool for wavelet transformed event-relatedEEG[J].NeuroImage，2006，29(3)：938-947.

[7]SIGNORETTO M，PLAS R，MOOR B，et al.Tensor versus matrix completion：a comparison with application to spectral data[J].IEEE Signal Processing Letters，2011，18(7)：403-406.

[8]GANDY S，RECHT B，YAMADAI.Tensor completion and low-n-rank tensor recovery via convex optimization[J].Inverse Problem，2011，27(2)：25-43.

[9]LIU Ji，LIU Jun，WONKA P，et al.Sparse non-negative tensor factorization using columwise coordinate decent[J].Pattern Recognition，2012，45(1)：649-656.

[10]史加榮，焦李成，尚凡華.張量補(bǔ)全算法及其在人臉識別中的應(yīng)用[J].模式識別與人工智能，2011，24(2)：255-261.

[11]史加榮.多尺度張量逼近及應(yīng)用[D].西安：西安電子科技大學(xué)，2012.

[12]KRESSNER D，STEINLECHNER M，VANDEREYCKEN B.Low-rank tensor completion by Riemannian optimization[J].BIT Numerical Mathematics，2014，54(2)：447-468.

[13]CAI Jian-feng，CANDèS E J，SHIN Zuo-wei.A singular value thresholding algorithm for matrix completion[J].Siam Journal on Optimization，2010，20(4)：1956-1982.

[14]KOLDA T G，BADER B W.Tensor decompositions and applications[J].Siam Review，2009，51(3)：455-500.

[15]KOLDA T G，GIBSON T.Multilinear operators for higher order decompositions[R].Albuquerque：Sandia National Laboratories，2006.

[16]劉圓圓.快速低秩矩陣與張量恢復(fù)的算法研究[D].西安：西安電子科技大學(xué)，2013.

[17]FAZEL M.Matrix rank minimization with applications[DJ].Palo Alto：Stanford University，2002.

[18]TSENG P.Convergence of block coordinate descent method for nondifferentiable minimization[J].Optimization Theory Application，2001，109(3)：475-494.

[19]IN Zhou-chen，CHEN Min-ming，MA Yi.The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[R].Urbana-Champaign：University of Illinois at Urbana-Champaign，2009.

[20]LIU Yuan-yuan，JIAO L C，SHANG Fan-hua. A fast tri-factorization method for low-rank matrix recovery and completion[J].Pattern Recognition，2013，46(1)：163-173.

[21]SHEEHAN B N，SAAD Y.Higher order orthogonal iteration of tensors (HOOI) and its relation to PCA and GLRAM[C].Proceedings of the Seventh SIAM International Conference on Data Mining，2007：355-365.

[22]SHI Jia-rong，YANG Wei，YONG Long-quan，et al.Low-rank tensor completion via tucker decompositions[J].Journal of Computational Information Systems，2015，11(10)：3759-3768.

[23]CHEN Cai-hua，HE Bing-sheng，YUAN Xiao-ming.Matrix completion via an alternating direction method[J].Ima Journal of Numerical Analysis，2012，32(1)：227-245.

[24]CANDèS E J，TAO T.The power of convex relaxation：near optimal matrix completion[J]. IEEE Transactions on Information Theory，2009，56(5)：2053-2080.

[25]LIU Yuan-yuan，JIAO L C，SHANG Fan-hua.An efficient matrix factorization based low-rank representation for subspace clustering[J].Pattern Recognition，2013，46(1)：284-282.

[26]HILLAR C J，LIM L H.Most tensor problems are NP-hard[J].CORR，2009，60(6)：1333-1360.

[27]GENG Juan，WANG Lai-sheng，XU Yi-tian，et al.A weighted nuclear norm method for tensor completion[J].International Journal of Signal Processing Image Processing and Pattern Recognition，2014，7(1)：1-12.

[28]M?RUP M.Applications of tensors (multiway array) factorizations and decompositions in data mining[J].Wiley Interdisciplinary Reviews：Data Ming and Knowledge Discovery，2011，1(1)：24-40.

[責(zé)任編輯：謝 平]

Survey on algorithms to low-rank tensor completion

LIU Hui-Mei,SHI Jia-Rong

(School of Science, Xi’an University of Architecture and Technology, Xi’an 710055, China)

Abstract:With the fast development of modern information technology, most data to be analyzed have very complex structures. In the process of high-dimensional multi-linear data acquisition, some elements may be lost. Low Rank Tensor Completion (LRTC) is just a technique to recover all missing elements by the low rank property of the investigated data. LRTC is the higher-order generalization of compressed sensing and is mathematically described as a nuclear norm minimization problem. This paper reviews the existing algorithms to LRTC. First, preliminaries on tensor algebra and models of LRTC are briefly introduced. Then this paper reviews several mainstream algorithms to LRTC including simple low-rank tensor completion, high accuracy low-rank tensor completion, core tensor nuclear norm of tensor completion and so on. Finally, the paper points out the research directions of LRTC needed to be investigated and improved.

Key words:tensor completion；low rank；nuclear norm minimization；core tensor nuclear norm；alternating direction method of multipliers

[中圖分類號]TP391

[文獻(xiàn)標(biāo)識碼]A

作者簡介：劉慧梅(1989—),女，陜西省延安市人，西安建筑科技大學(xué)碩士研究生，主要研究方向為概率統(tǒng)計應(yīng)用；[通信作者]史加榮(1979—)，男，山東省聊城市人，西安建筑科技大學(xué)副教授，博士，主要研究方向為機(jī)器學(xué)習(xí)與模式識別。

基金項目：國家自然科學(xué)基金資助項目(61403298)；陜西省自然科學(xué)基礎(chǔ)研究計劃項目(2014JQ8323)

收稿日期：2015-12-02修回日期：2016-02-25

[文章編號]1673-2944(2016)02-0080-07