基于加權(quán)核范數(shù)的低秩矩陣補(bǔ)全算法研究

石瑩， 黃華， 王智， 高超

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

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

(1)

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

(2)

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

(3)

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

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

1 基礎(chǔ)知識(shí)

當(dāng)使用核范數(shù)去松弛秩函數(shù)rank(X)時(shí)，數(shù)學(xué)上可將低秩矩陣補(bǔ)全問(wèn)題建模為

(4)

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

(5)

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

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

(6)

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

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

X*=Sλ(Y)=UDVT

(7)

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

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

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

(8)

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

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

(9)

該算法的詳細(xì)步驟如算法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ù)極小化模型中，它同等對(duì)待目標(biāo)矩陣的所有奇異值，這導(dǎo)致該模型不能很好地刻畫矩陣的低秩結(jié)構(gòu).為了解決這一困難，近年來(lái)加權(quán)核范數(shù)[21]被提出來(lái)用于更好地刻畫目標(biāo)矩陣的低秩結(jié)構(gòu).對(duì)目標(biāo)低秩矩陣，加權(quán)核范數(shù)模型盡可能地對(duì)較大奇異值進(jìn)行較小懲罰，而對(duì)較小奇異值進(jìn)行較大懲罰.對(duì)于任一矩陣X∈Rm×n，加權(quán)核范數(shù)可定義為

(10)

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

(11)

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

2 WNNM-Impute算法

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

(12)

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

(13)

(14)

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

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

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

(15)

的最優(yōu)解為

X*=Sλ(Y)=UDVT

(16)

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

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

算法2WNNM-Impute算法

1)初始化V1，V2∈Rm×n為隨機(jī)的高斯矩陣，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可以看出，在對(duì)極小化模型(11)的求解過(guò)程中，需要對(duì)觀察矩陣Y∈Rm×n做SVD分解，它的時(shí)間復(fù)雜度為O(mn2).因此，當(dāng)矩陣的規(guī)模較大時(shí)，這是相當(dāng)費(fèi)時(shí)的.為此，在算法2中，我們引入PowerMethod算法得到一個(gè)正交矩陣Q∈Rm×t，其中t>r且t?n.這樣，對(duì)矩陣G的SVD分解可以轉(zhuǎn)為對(duì)矩陣QTG的SVD分解.但是，QTG的規(guī)模僅為m×t，遠(yuǎn)小于矩陣G的規(guī)模m×n.從而，時(shí)間復(fù)雜度降為O(mt2).該過(guò)程可概述為如下引理.

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

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

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

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

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

(17)

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

(18)

(19)

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

(20)

這里0<η<1.

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

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

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

3 實(shí)驗(yàn)仿真

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

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

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

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

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

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

1)計(jì)算

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

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

3)運(yùn)行時(shí)間t.

在實(shí)驗(yàn)中，我們對(duì)不同規(guī)模的矩陣進(jìn)行了測(cè)試，即m∈{500，1 000，1 500，3 000}.每個(gè)算法獨(dú)立運(yùn)行10次，報(bào)告其平均NMSE值.

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

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

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

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

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

2)運(yùn)行時(shí)間t.

實(shí)驗(yàn)結(jié)果如表2和圖2所示.

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

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

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

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

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

1)Jester1：包括24 983名用戶對(duì)36個(gè)或更多笑話的評(píng)價(jià)；

2)Jester2：包括23 500名用戶對(duì)36個(gè)或更多笑話的評(píng)價(jià)；

3)Jester3：包括24 983名用戶評(píng)價(jià)了15到35個(gè)笑話；

4)MovieLens-100K：包含942名用戶對(duì)1 682部影片的100 000個(gè)評(píng)價(jià)；

5)MovieLens-1M：包含6 040名用戶對(duì)3 900部影片的1 000 000個(gè)評(píng)價(jià)；

6)MovieLens-10M：包含69 878名用戶對(duì)10 677部影片的1 000 000個(gè)評(píng)價(jià).

在本組實(shí)驗(yàn)中，采用如下方式來(lái)評(píng)估所有算法的性能：

1)計(jì)算

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

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

3)運(yùn)行時(shí)間t.

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

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

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

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

4 結(jié)束語(yǔ)

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