石瑩， 黃華， 王智， 高超

1.西南大學(xué) 信息化建設(shè)辦公室，重慶 400715；2.重慶工程職業(yè)技術(shù)學(xué)院，現(xiàn)代教育技術(shù)中心，重慶 402260；3.西南大學(xué) 計算機與信息科學(xué)學(xué)院，重慶 400715；4.西北工業(yè)大學(xué) 光電與智能研究院，西安 710072

在諸如協(xié)同過濾[1-2]、降維處理[3]、子空間聚類[4]、圖像和信號處理[5-6]等機器學(xué)習(xí)或數(shù)據(jù)分析領(lǐng)域，人們通常需要求解如下優(yōu)化問題

(1)

其中：M∈Rm×n為僅知道部分觀察元素的待恢復(fù)矩陣，X∈Rm×n為目標矩陣，Ω表示已知的觀察元素的位置，PΩ為正交投影算子，定義為

(2)

求解優(yōu)化問題(1)的主要任務(wù)是尋找一個最小秩矩陣X*∈Rm×n，使其滿足PΩ(X*)=PΩ(M)且使得秩函數(shù)rank(X)最小.利用正則化方法，問題(1)可等價地轉(zhuǎn)換為如下非約束最小化問題

(3)

這里‖·‖F(xiàn)表示F范數(shù)，λ>0為正則化參數(shù).

基于非凸正則化方法的優(yōu)良性能，本文對基于加權(quán)核范數(shù)正則化模型進行進一步的分析和探討，并借鑒Soft-Impute算法的思想提出一個擁有更快收斂速率和能夠得到更高精度解的低秩矩陣補全算法.在本文提出WNNM-Impute(weighted nuclear norm minimization impute)算法的迭代過程中，需要進行費時的SVD分解.針對這一問題，通過引入不精確的近鄰算子極大地降低WNNM-Impute算法的時間復(fù)雜度，從而使得算法收斂更快.同時，在算法中引入Nesterov加速策略，使得算法的總體迭代次數(shù)進一步減少.本文提出的算法基于Soft-Impute算法，但是實驗結(jié)果表明，它比Soft-Impute算法收斂更快且得到的解的精度更高.因此，本文提出的算法適合用于求解大規(guī)模低秩矩陣補全問題.

1 基礎(chǔ)知識

當使用核范數(shù)去松弛秩函數(shù)rank(X)時，數(shù)學(xué)上可將低秩矩陣補全問題建模為

(4)

這里‖X‖*表示核范數(shù)，定義為

(5)

其中r=min(m，n)，σi(X)為矩陣X的第i個奇異值.

模型(4)能夠被SVT等算法快速求解.在SVT算法中，需要求解如下奇異值閾值算子

(6)

該算子的求解需要如下引理.

引理1若記矩陣Y的SVD分解為Y=UΣVT，則(6)式的最優(yōu)解為

X*=Sλ(Y)=UDVT

(7)

其中Sλ(·)為軟閾值函數(shù)，Dii=max(Σii-λ，0).

從上述引理可以看出，主要的計算集中在求解矩陣Y的SVD分解，其時間復(fù)雜度為O(mn2)，因此它不適合求解大規(guī)模矩陣補全問題.針對這一問題，文獻[13]注意到

PΩ(M)+PΩ⊥(Xk)=PΩ(M-Xk)+Xk

(8)

其中：Xk為第k次迭代值，PΩ⊥(·)表示Ω的補集中的元素.顯然，(8)式右邊的第一部分具有稀疏的特性，第二部分具有低秩的特性.因此，利用SVT算法的思想提出了Soft-Impute算法，在第k+1次迭代時有

Xk+1=Sλ(PΩ(M)+PΩ⊥(Xk))

(9)

該算法的詳細步驟如算法1所示.

算法1Soft-Impute算法[13]

輸入：部分觀察矩陣M，參數(shù)λ>0

輸出：秩為r的矩陣X

1)初始化X1=0；

2)fork=1，2，… do

3)Y=PΩ(M)+PΩ⊥(Xk)

4)Xk+1=Sλ(Y)

5)end for

6)returnXk+1

然而，在核范數(shù)極小化模型中，它同等對待目標矩陣的所有奇異值，這導(dǎo)致該模型不能很好地刻畫矩陣的低秩結(jié)構(gòu).為了解決這一困難，近年來加權(quán)核范數(shù)[21]被提出來用于更好地刻畫目標矩陣的低秩結(jié)構(gòu).對目標低秩矩陣，加權(quán)核范數(shù)模型盡可能地對較大奇異值進行較小懲罰，而對較小奇異值進行較大懲罰.對于任一矩陣X∈Rm×n，加權(quán)核范數(shù)可定義為

(10)

其中w=[w1，w2，…，wr]T和wi≥0為分配給σi(X)的非負加權(quán).核范數(shù)極小化方法為了刻畫矩陣的低秩結(jié)構(gòu)同等對待目標矩陣的奇異值，而(10)式考慮對較小奇異值進行更多懲罰，而較大的奇異值得到更少懲罰.基于此，利用(10)式去松弛秩函數(shù)rank(X)，將原始低秩矩陣補全問題建模為

(11)

模型(11)比模型(4)能夠更好地刻畫目標矩陣的低秩結(jié)構(gòu)，但是由于加權(quán)核范數(shù)的引入，得到非凸、非光滑的優(yōu)化問題，使得對該問題的求解變得非常困難.傳統(tǒng)的針對核范數(shù)正則化模型的求解方法不能直接用于求解非凸正則化模型.因此，如何設(shè)計出快速、穩(wěn)健、可擴展和可靠的算法是一個至關(guān)重要的挑戰(zhàn).本文針對這一問題，利用Soft-Impute的求解思想，融入不精準近鄰算法和Nesterov優(yōu)化理論，提出一個快速高效的低秩矩陣補全算法用于求解模型(11)，理論和實驗結(jié)果都表明所提出的算法能夠得到更快的收斂速率和更高精度的解.

2 WNNM-Impute算法

受到Soft-Impute算法的啟發(fā)，本節(jié)將融入不精準近鄰算法和Nesterov優(yōu)化理論，構(gòu)建用于求解優(yōu)化模型(11)的一階梯度算法.然而，由于加權(quán)核范數(shù)的引入，優(yōu)化模型(11)是非凸和非光滑的.因此，為了得到該模型的閉式解，需要求解如下加權(quán)核范數(shù)近鄰算子.

(12)

下面的定理表明，加權(quán)核范數(shù)近鄰問題(12)可轉(zhuǎn)化為線性約束的二次規(guī)劃問題，從而得到它的閉式解.

(13)

(14)

s.t.d1≥d2≥…≥dr≥0

該定理的證明見文獻[21].基于定理1，如取w1≤w2≤…≤wr，可以得到如下推論.

推論1對任意給定λ>0，Y∈Rm×n且其SVD分解為Y=UΣVT，w1≤w2≤…≤wr，r為矩陣Y的秩，則極小化問題

(15)

的最優(yōu)解為

X*=Sλ(Y)=UDVT

(16)

其中Dii=max(Σii-λwi，0).

該推論的證明見文獻[21].該推論表明，雖然極小化問題(15)是非凸和非光滑的，但是它仍然存在全局最優(yōu)閉式解.利用定理1和推論1的結(jié)論，我們提出如下算法用于求解優(yōu)化模型(11).

算法2WNNM-Impute算法

1)初始化V1，V2∈Rm×n為隨機的高斯矩陣，X0=X1=0，Y1=X0，λ0=η‖PΩ(M)‖2，θ0=1；

2)fork=1，2，…，Tdo

3)Rk=QR([Vk，Vk-1])//QR()表示QR分解

4)G=Yk-μ(PΩ(Yk-M))

5)Q=PowerMethod(G，Rk)

6) [U，Σ，V]=SVD(QTG)

7)U={uk|Σii>λwi}

8)V={vk|Σii>λwi}

9)D={dii|max(Σii-λk-1wi，0)}

13) else

14)Xk+1=Yk

15) end if

20) break

21) end if

22)Vk+1=V

23)end for

24)returnXk+1

從定理2和推論1可以看出，在對極小化模型(11)的求解過程中，需要對觀察矩陣Y∈Rm×n做SVD分解，它的時間復(fù)雜度為O(mn2).因此，當矩陣的規(guī)模較大時，這是相當費時的.為此，在算法2中，我們引入PowerMethod算法得到一個正交矩陣Q∈Rm×t，其中t>r且t?n.這樣，對矩陣G的SVD分解可以轉(zhuǎn)為對矩陣QTG的SVD分解.但是，QTG的規(guī)模僅為m×t，遠小于矩陣G的規(guī)模m×n.從而，時間復(fù)雜度降為O(mt2).該過程可概述為如下引理.

引理2假定矩陣G∈Rm×n有r個奇異值大于λw，G=QQTG，其中Q∈Rm×t為正交矩陣且t>r，則

1)range(G)?range(Q)；

2)Sλ(G)=QSλ(QTG).

該引理的證明過程與文獻[22]中的引理1類似，這里省略.需要指出的是，引理2是處理的加權(quán)核范數(shù)正則子，而非核范數(shù)正則子.

由于PowerMethod算法[22]的引入，得到閾值算子的值將是不精確的.因此，需要判斷當前值是否可行.于是，在算法2中，我們采用如下式子來確保目標函數(shù)F是單調(diào)遞減的，從而保證目標函數(shù)收斂到某一穩(wěn)定點：

(17)

為了提升算法的收斂速率，在算法2中引入Nesterov加速準則，該準則被廣泛地應(yīng)用于機器學(xué)習(xí)算法中，如nmAPG，F(xiàn)aNCL-acc，niAPG等.基于此，在算法2中采用如下加速策略

(18)

(19)

實驗部分將進一步表明，由于(18)和(19)式加速策略的引入，使得算法2的收斂速率得到大幅地提高.

(20)

這里0<η<1.

在算法2的迭代過程中，得到的解Xk不斷地逼近真實解，且目標函數(shù)F單調(diào)遞減，直到收斂到某一穩(wěn)定點.下面的定理保證了算法2的收斂性，該定理的證明參照文獻[20].

定理2假定{Xk}為算法2在迭代過程中產(chǎn)生的解序列，則

2)目標函數(shù)F單調(diào)遞減，且收斂到F(X*)，這里X*為序列{Xk}的任一聚點；

3 實驗仿真

為了測試WNNM-Impute算法的效率和準確性，本節(jié)將在模擬數(shù)據(jù)集和真實數(shù)據(jù)集上進行一系列的對比實驗.在接下來的實驗中，將包括如下經(jīng)典或最新算法.

1)SVT算法：經(jīng)典的、被廣泛應(yīng)用于低秩矩陣補全問題中的方法，它將線性Bregman迭代用于求解低秩矩陣優(yōu)化問題；

2)APG算法：基于核范數(shù)的低秩矩陣補全方法，是快速迭代收縮閾值算法的矩陣版本；

3)R1MP算法：該方法是將正交匹配追蹤算法用于求解低秩矩陣補全問題；

4)Soft-Impute算法：該方法是在SVT方法的基礎(chǔ)上，利用迭代過程存在“低秩+稀疏”的特性，達到快速求解低秩補全問題的目的；

5)WNNM算法：基于加權(quán)核范數(shù)的低秩矩陣補全方法.

1)計算

其中：X為結(jié)果矩陣，Ω⊥為除觀察值以外的位置；

2)結(jié)果矩陣X的秩r；

3)運行時間t.

在實驗中，我們對不同規(guī)模的矩陣進行了測試，即m∈{500，1 000，1 500，3 000}.每個算法獨立運行10次，報告其平均NMSE值.

實驗結(jié)果如表1所示.從表1可以看出，WNNM-Impute算法無論是精度還是效率都要優(yōu)于其他算法.具體來說，WNNM-Impute算法在所有的數(shù)據(jù)集上均得到了最小的NMSE，且運行的平均時間是最短的.此外，在實驗中，SVT，WNNM和WNNM-Impute算法能夠得到秩為5的近似解，而APG，R1MP和Soft-Impute算法得到的近似解的秩遠高于5.實驗同時揭示了在WNNM-Impute算法中引入不精確的近鄰算法和Nesterov加速準則能夠極大地提升算法的效率.

表1 不同算法在不同規(guī)模和不同采樣率下的矩陣補全結(jié)果

第二組實驗為在真實圖像數(shù)據(jù)集上的低秩矩陣補全.實驗中所使用的圖像數(shù)據(jù)如圖1所示，每張圖片的大小為512×512.

在實驗中，我們直接對原始圖像進行處理.由于原始圖像可能不是嚴格低秩的，因此使用秩為50的矩陣去近似原始圖像.對于每一張圖像，隨機地去掉圖像中50%的數(shù)據(jù)，余下的數(shù)據(jù)作為觀察值.在本組實驗中，采用如下方式來評估所有算法的性能：

1)PSNR(peak signal-to-noise ratio)；

2)運行時間t.

實驗結(jié)果如表2和圖2所示.

圖2 WNNM-Impute算法在Lena圖像上的恢復(fù)結(jié)果

表2 不同算法在圖像數(shù)據(jù)集上的恢復(fù)結(jié)果

從表2可以看出，在大多數(shù)測試圖像數(shù)據(jù)上WNNM-Impute算法得到更大的PNSR值.進一步分析發(fā)現(xiàn)，雖然WNNM-Impute算法的效率略低于R1MP算法，但是本文提出的算法得到的PNSR值遠好于R1MP算法.因此，綜合考慮精度和效率，本次實驗再一次證實本文提出的WNNM-Impute算法的有效性.

為了進一步測試WNNM-Impute算法的有效性，接下來將在真實數(shù)據(jù)集上進行實驗.這些數(shù)據(jù)集包括：Jester1，Jester2，Jester3，MovieLens-100K，MovieLens-1M和MovieLens-10M.這些數(shù)據(jù)集的特性如表3所示，其中Jester數(shù)據(jù)集來源于一個笑話推薦系統(tǒng)，而MovieLens數(shù)據(jù)集來自于MovieLens網(wǎng)站.

表3 協(xié)同過濾數(shù)據(jù)集的特征

1)Jester1：包括24 983名用戶對36個或更多笑話的評價；

2)Jester2：包括23 500名用戶對36個或更多笑話的評價；

3)Jester3：包括24 983名用戶評價了15到35個笑話；

4)MovieLens-100K：包含942名用戶對1 682部影片的100 000個評價；

5)MovieLens-1M：包含6 040名用戶對3 900部影片的1 000 000個評價；

6)MovieLens-10M：包含69 878名用戶對10 677部影片的1 000 000個評價.

在本組實驗中，采用如下方式來評估所有算法的性能：

1)計算

其中：這里Ω⊥表示測試數(shù)據(jù)集，X為結(jié)果矩陣；

2)結(jié)果矩陣的秩r；

3)運行時間t.

在實驗中，隨機地從每個協(xié)調(diào)過濾數(shù)據(jù)集中選取50%的數(shù)據(jù)作為觀察數(shù)據(jù)，余下的為測試數(shù)據(jù).實驗結(jié)果如表4和表5所示.

表4 不同算法在Jester笑話數(shù)據(jù)集上的恢復(fù)結(jié)果

表5 不同算法在MovieLens數(shù)據(jù)集上的恢復(fù)結(jié)果

從表4和表5可以看出，在6個協(xié)調(diào)過濾數(shù)據(jù)集上WNNM-Impute算法幾乎總能得到最小的RMSE值，在效率方面僅比R1MP慢一點.在實驗中發(fā)現(xiàn)SVT，WNNM和WNNM-Impute算法能夠得到秩更低的解，而APG，R1MP和Soft-Impute算法不能得到近似低秩矩陣解.該組實驗進一步說了，WNNM-Impute算法在真實協(xié)調(diào)過濾數(shù)據(jù)集上是高效的.

4 結(jié)束語

本文利用加權(quán)核范數(shù)去松弛原始低秩極小化問題，得到一個非凸非光滑的優(yōu)化問題.為了高效地求解該問題，文中利用Soft-Impute的算法思想，融入不精確近鄰算子和Nesterov優(yōu)化理論，提出了一個快速、準確的低秩矩陣補全算法.實驗結(jié)果表明，在不同規(guī)模和不同采樣率的模擬數(shù)據(jù)集上WNNM-Impute算法能夠得到更加精確的解且效率更高；在采樣率相同和不同規(guī)模的協(xié)同過濾數(shù)據(jù)集上WNNM-Impute算法能夠得到秩更低且更好質(zhì)量的解.因此，本文提出的WNNM-Impute算法是一個具有較強競爭力的低秩矩陣補全算法.