求解矩陣補(bǔ)全問題的三分解方法

，(山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590)

近年來，矩陣補(bǔ)全問題廣泛應(yīng)用于圖像處理、計(jì)算機(jī)視覺、數(shù)據(jù)挖掘、模式識(shí)別和機(jī)器學(xué)習(xí)等領(lǐng)域。作為信號(hào)與圖像處理技術(shù)的一個(gè)強(qiáng)大的新興分支，矩陣補(bǔ)全已成為繼壓縮感知之后的又一種重要的信號(hào)獲取工具[1]。

一般來說，要根據(jù)信號(hào)的部分采樣元素來精確地恢復(fù)出所有元素是非常困難甚至是不可能的。但是當(dāng)信號(hào)在一組基下是稀疏的且滿足一定條件時(shí)，壓縮感知理論證實(shí)了可以通過求解l1最小化問題來精確地恢復(fù)所有元素[2]。類似的，當(dāng)信號(hào)用矩陣形式表示時(shí)，要根據(jù)其部分元素來恢復(fù)所有丟失元素也是很困難的。針對(duì)這一問題，Candès等[3]證明了當(dāng)矩陣的奇異值具有稀疏性且采樣數(shù)目滿足一定條件時(shí)，大多數(shù)矩陣可以通過求解核范數(shù)最小化問題來精確地恢復(fù)所有元素。由矩陣的部分元素恢復(fù)所有元素這一問題稱為矩陣補(bǔ)全問題，著名的Netflix問題便是一個(gè)典型的矩陣補(bǔ)全問題[4]。

給定不完整的低秩缺失矩陣W∈Rm×n，矩陣補(bǔ)全問題可以描述為如下優(yōu)化問題：

(1)

其中A∈Rm×n為待補(bǔ)全的矩陣，Ω是A的p個(gè)已知元素的指標(biāo)集。由于秩函數(shù)的非凸性和不連續(xù)性，上述秩函數(shù)最小化問題是NP難的，現(xiàn)有的算法無法有效地解決秩最小化問題?；诖?，Candès等[5]證明了可用秩函數(shù)的凸包絡(luò)—核范數(shù)來近似秩函數(shù)，即可將問題(1)凸松弛為如下核范數(shù)最優(yōu)化問題

(2)

需要指出的是，矩陣補(bǔ)全模型(2)只能對(duì)缺失的元素進(jìn)行恢復(fù)，而無法估計(jì)其所含的噪聲。然而在某些情況下，噪聲里往往會(huì)包含一些重要的信息，因此，噪聲有時(shí)也是非常重要的待恢復(fù)成分。另一方面，矩陣補(bǔ)全模型(2)對(duì)大的稀疏噪聲或野點(diǎn)非常敏感，為了克服上述模型的不足，Shi等[6]將矩陣補(bǔ)全模型(2)與魯棒主成分分析(robust principal component analysis, RPCA)模型進(jìn)行了推廣，提出如下不完全RPCA(IRPCA)模型

(3)

(4)

現(xiàn)有的求解基于核范數(shù)的矩陣秩最小化問題的大多數(shù)算法，每一步迭代都需要進(jìn)行奇異值分解，而多步奇異值分解則大大增加了算法的計(jì)算復(fù)雜度。為了降低計(jì)算復(fù)雜度，Xu等[8]將非負(fù)矩陣分解算法和矩陣補(bǔ)全模型相結(jié)合，提出了基于非負(fù)矩陣分解的矩陣補(bǔ)全模型；Zheng等[9]提出將含有噪聲的低秩矩陣近似問題等價(jià)為雙線性分解問題；Shang等[7]則將矩陣雙分解(robust bilinear factorization，RBF)方法應(yīng)用于RMC模型，得到了較好的數(shù)值結(jié)果。

基于矩陣分解在求解基于核范數(shù)的矩陣秩最小化問題中的優(yōu)勢(shì)，將矩陣的三分解[10]技術(shù)應(yīng)用到RMC模型中，利用增廣拉格朗日乘子法對(duì)模型進(jìn)行求解，并將新模型應(yīng)用于人臉識(shí)別的實(shí)際問題。數(shù)值實(shí)驗(yàn)結(jié)果顯示，本研究提出的模型相較于RMC和RBF模型，計(jì)算速度更快，實(shí)驗(yàn)效果更好。

1 三分解技巧與模型

在高維數(shù)據(jù)分析中，矩陣分解是一個(gè)常用的技巧，也是一個(gè)非常有效的工具。常用的矩陣分解主要有QR分解、LU分解、奇異值分解、非負(fù)矩陣分解等。現(xiàn)有的大多數(shù)矩陣分解技巧都是將矩陣分解為兩個(gè)具有某種特殊性質(zhì)矩陣的乘積。本研究將利用矩陣的三分解技巧及核范數(shù)的正交不變性，盡可能地降低RMC模型的規(guī)模，以達(dá)到減少計(jì)算量的目的。

下面對(duì)所采用的矩陣三分解方法(TFM)進(jìn)行介紹。設(shè)A∈Rm×n，rank(A)=r，則由參考文獻(xiàn)[10]知，存在矩陣X∈Rm×r，Y∈Rr×r，Z∈Rr×n，使A=XYZT。其中X，Z為具有正交規(guī)范列的矩陣，即XTX=Ir，ZTZ=Ir。

上述分解稱為矩陣A的三分解。本文就是基于矩陣三分解理論對(duì)RMC模型(4)進(jìn)行修改。

(5)

由矩陣三分解的定義可知，當(dāng)矩陣A的秩較小時(shí)，通過矩陣的三分解可將問題的規(guī)模大大降低。將主要針對(duì)上述等價(jià)模型(5)進(jìn)行求解和分析。

2 模型求解與算法

本節(jié)中，將利用交替方向乘子法(alternating direction multiplier method, ADMM)對(duì)TFMC模型進(jìn)行求解。

模型(5)的増廣拉格朗日函數(shù)為

交替方向乘子法的基本迭代公式如下

(6-1)

(6-2)

(6-3)

(6-4)

(6-5)

2.1 收縮算子Y的更新

將變量E,X,Z固定，更新Y的最優(yōu)化模型(6-1)可等價(jià)為

(7)

為了求解上述核范數(shù)最小化問題，給出以下引理：

本研究仍然使用奇異值分解的方法求解問題(7)，與未使用矩陣三分解的模型需要對(duì)m×n維的矩陣進(jìn)行奇異值分解不同，只需要對(duì)r×r維的矩陣進(jìn)行奇異值分解，其中r?min(m,n)。

因此，TFM方法可以大大降低計(jì)算的復(fù)雜度。由引理知，模型(7)的最優(yōu)解為

(8)

2.2 利用軟閾值算子更新E

為了求解變量E，固定變量Y,X,Z，可將模型(6-2)轉(zhuǎn)化為如下優(yōu)化模型

為了得到Ek+1的最優(yōu)解，需先確定EΩ和EΩC分別對(duì)應(yīng)的兩個(gè)子問題。其中，EΩ對(duì)應(yīng)的子問題為

(9)

對(duì)問題(9)利用軟閾值算子進(jìn)行求解，可得其最優(yōu)解為

(10)

另外，EΩC對(duì)應(yīng)的子問題為

(11)

由問題(11)的最優(yōu)性條件可得其最優(yōu)解為

(12)

2.3 利用Orthogonal Procrustes更新X和Z

為了求解變量X和Z，分別將模型(6-3)和(6-4)轉(zhuǎn)化為以下兩個(gè)子問題

(13)

(14)

可得X和Z的最優(yōu)解分別為

(15)

(16)

求解模型(5)的算法如下：

算法：求解模型(5)的增廣拉格朗日方法輸入：數(shù)據(jù)矩陣W∈Rm×n，λ>0；初始化：令E=E0，X=X0，Y=Y0，Z=Z0，Λ=Λ0；步驟1：根據(jù)(8)式計(jì)算Yk+1；步驟2：根據(jù)(10)式和(12)式計(jì)算Ek+1；步驟3：根據(jù)(15)式計(jì)算Xk+1；步驟4：根據(jù)(16)式計(jì)算Zk+1；步驟5：根據(jù)(6?5)式更新拉格朗日乘子Λk+1；直到收斂；輸出：Y?=Yk+1，E?=Ek+1，X?=Xk+1，Z?=Zk+1

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

將提出的基于矩陣三分解方法的RMC模型應(yīng)用于人臉識(shí)別的實(shí)際問題中，利用Yale-B人臉數(shù)據(jù)集中的Man face數(shù)據(jù)集和Woman face數(shù)據(jù)集，與原始RMC模型和使用RBF方法的RMC模型進(jìn)行迭代次數(shù)、運(yùn)行時(shí)間的比較。實(shí)驗(yàn)運(yùn)行環(huán)境為Pentium E5500 2.77 GHz雙核處理器，內(nèi)存2.00 GB。所有算法程序均由Matlab R2014a編寫。

3.1 參數(shù)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果

將本研究提出的TFMC模型與RMC模型和使用RBF方法的RMC模型進(jìn)行對(duì)比實(shí)驗(yàn)，迭代次數(shù)與運(yùn)行時(shí)間的比較結(jié)果見表1?？梢?，在不同數(shù)據(jù)集中，本研究所用算法較RMC和RBF方法的迭代次數(shù)和運(yùn)行時(shí)間均有很大程度的降低。

表1 迭代次數(shù)與運(yùn)行時(shí)間的比較結(jié)果Tab.1 Comparison results of iteration times and running time

考慮到矩陣補(bǔ)全的目的是恢復(fù)含有損失函數(shù)的數(shù)據(jù)矩陣，因此為了進(jìn)一步顯示本文方法的有效性，Man face數(shù)據(jù)集取秩分別為10、12、15，Woman face數(shù)據(jù)集取秩分別為6、7、8進(jìn)行數(shù)值實(shí)驗(yàn)。由圖1、圖2可以看出，本研究方法均可以比較完美的恢復(fù)原有的模樣。另一方面，雖然已知數(shù)據(jù)的尺寸非常大，但由于本研究采用的矩陣三分解方法對(duì)問題進(jìn)行了大幅度的降階，使得當(dāng)r較小時(shí)，算法的運(yùn)算時(shí)間大大減少。Man face數(shù)據(jù)集中，當(dāng)r=10,12,15時(shí)，算法的運(yùn)算時(shí)間分別為62.1、76.5和83.2 s. Woman face數(shù)據(jù)集中，當(dāng)r=6,7,8時(shí)，算法的運(yùn)算時(shí)間分別為1.884、2.081和2.020 s。

其中Input-40表示輸入的第40張?jiān)紙D片；Mask中紅色表示閉塞像素，黃色表示飽和像素；第一行的后三列表示秩為10、12、15的恢復(fù)圖片；第二行后三列表示秩為10、12、15的噪聲圖片。圖1 Manface數(shù)據(jù)集秩分別為10、12、15時(shí)對(duì)應(yīng)的恢復(fù)效果圖Fig.1 The recovered images from Man face data set’s rank-10, rank-12 and rank-15 factorization

其中Input-6表示輸入的第6張?jiān)紙D片；Mask中紅色表示閉塞像素，黃色表示飽和像素；第一行的后三列表示秩為6、7、8的恢復(fù)圖片；第二行后三列表示秩為6、7、8的噪聲圖片。圖2 Woman face數(shù)據(jù)集秩分別為6、7、8時(shí)對(duì)應(yīng)的恢復(fù)效果圖Fig.2 The recovered images from Woman face data set’s rank-6, rank-7 and rank-8 factorization

4 總結(jié)

針對(duì)人臉識(shí)別中的矩陣補(bǔ)全模型，求解過程中存在計(jì)算復(fù)雜度過大的問題提出使用三分解方法降低計(jì)算的復(fù)雜度，并應(yīng)用交替方向乘子法進(jìn)行求解。數(shù)值實(shí)驗(yàn)結(jié)果表明，設(shè)計(jì)的模型迭代次數(shù)少，計(jì)算時(shí)間短。隨著數(shù)據(jù)集中數(shù)據(jù)量的不斷增大，本模型和算法將有更廣闊的應(yīng)用前景。

參考文獻(xiàn)：

[1]彭義剛，索津莉，戴瓊海，等.從壓縮傳感到低秩矩陣恢復(fù):理論與應(yīng)用[J].自動(dòng)化學(xué)報(bào)，2013，39(7):981-994.

PENG Yigang,SUO Jinli，DAI Qionghai，et al.From compressed sensing to low-rank Matrix recovery:Theory and applications[J].Acta Automatica Sinica，2013，39(7):981-994.

[2]馬堅(jiān)偉, 徐杰, 鮑躍全,等. 壓縮感知及其應(yīng)用:從稀疏約束到低秩約束優(yōu)化[J]. 信號(hào)處理, 2012, 28(5):609-623.

MA Jianwei，XU Jie，BAO yuequan，et al.Compressive sensing and its application: From sparse to low-rank regularized optimization[J]. Signal Processing，2012, 28(5):609-623.

[4]張婷婷.基于低秩矩陣填充與恢復(fù)的圖像去噪方法研究[D].天津：河北工業(yè)大學(xué)，2015.

[6]SHI J，ZHENG X，YONG L.Incomplete robust principal component analysis[J].ICIC Express Letters.Part B，Applications:An International Journal of Research and Surveys，2014，5(6):1531-1538.

[7]SHANG F，LIU Y，TONG H，et al.Robust bilinear factorization with missing and grossly corrupted observations[J].Information Sciences，2015，307:53-72.

[8]XU Y，YIN W，WEN Z，et al.An alternating direction algorithm for matrix completion with nonnegative factors[J].Frontiers of Mathematics in China，2012，7(2):365-384.

[9]ZHENG Y，LIU G，SUGIMOTO S，et al.Practical low-rank matrix approximation under robust l1-norm[C]∥IEEE Conference on Computer Vision and Pattern Recognition (CVPR)，2012:1410-1417.

[10]DING C，LI T，PENG W，et al.Orthogonal nonnegative matrix t-factorizations for clustering[C]∥Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，2006:126-135.

[11] LIU Y, JIAO L C, SHANG F. An efficient matrix factorization based low-rank representation for subspace clustering[J]. Pattern Recognition, 2013, 46(1):284-292.

[12]CAI J F，CANDS E J，SHEN Z.A singular value thresholding algorithm for matrix completion[J].SIAM Journal on Optimization，2010,20(4):1956-1982.