利用加權(quán)對數(shù)范數(shù)分解的矩陣填充算法*

賴燁輝,黃慧英,彭紹婷,胡文玉

(贛南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,江西 贛州 341000)

0 引言

低秩矩陣填充問題是指基于矩陣的低秩特性,利用已知的部分元素合理精確地將未知元素進(jìn)行填充.具體來說,給定不完整數(shù)據(jù)的觀察矩陣Y∈m1×m2,矩陣填充問題可轉(zhuǎn)化為求解如下優(yōu)化問題[1]:

(1)

其中X∈m1×m2是待恢復(fù)的準(zhǔn)確數(shù)據(jù),Ω表示與觀測數(shù)據(jù)元素對應(yīng)的位置集合.

然而,由于秩函數(shù)的非凸性和不連續(xù)性,上述秩極小化問題是NP-難問題.因此,秩函數(shù)通常被核范數(shù)替代.然而,作為一種凸的近似替代函數(shù),核范數(shù)極小化結(jié)果通常會偏離實(shí)際秩極小化的結(jié)果,這是因?yàn)楹朔稊?shù)無差別地將X的所有非零奇異值相加,造成矩陣的大奇異值被過度懲罰,而在實(shí)際秩極小化問題中,所有非零奇異值都受到等量對待.為了克服上述問題,研究人員選擇用非凸替代函數(shù)來近似秩函數(shù),從而獲到了更好的實(shí)驗(yàn)結(jié)果.例如,Gu等[2]提出了基于加權(quán)核范數(shù)的極小化問題(Weighted Nuclear Norm Minimization, WNNM),其利用加權(quán)核范數(shù)代替核范數(shù)作為模型的低秩懲罰項(xiàng),降低了對大奇異值的懲罰度;Chen等[3]提出使用對數(shù)范數(shù)代替核范數(shù)作為模型的低秩懲罰項(xiàng),進(jìn)一步降低對大奇異值的懲罰度.

上面提出的方法都需要計(jì)算完整的奇異值分解(Singular Value Decomposition, SVD).在處理大規(guī)模數(shù)據(jù)時(shí),SVD需要大量的計(jì)算成本和時(shí)間,這限制了它們在處理大規(guī)模問題時(shí)的適用性[4].為了解決這個(gè)問題,研究人員提出了基于低秩分解的矩陣填充方法.例如Cabral等[4]提出了一種核范數(shù)的雙線性分解方法,他們證明:任何矩陣都可以分解為兩個(gè)因子矩陣的乘積,并且矩陣的核范數(shù)等于兩個(gè)因子矩陣的Frobenius范數(shù)(F范數(shù))平方之和的一半.Lin等[5]推廣至一種更一般的魯棒矩陣分解方法(Robust Matrix Factorization, RMF).然而,這些只是核范數(shù)的雙線性分解,結(jié)果仍然偏離實(shí)際的秩極小化結(jié)果.為此,Chen等[6]結(jié)合重加權(quán)核范數(shù)極小化和雙線性分解,提出了重加權(quán)低秩矩陣分解(Reweighted Low-Rank Factorization, RLMF).此外,Chen等[3]提出了一種對數(shù)范數(shù)矩陣分解(Logarithmic norm Regularized Matrix Factorization, LRMF).以上方法雖然一定程度上能夠抑制大奇異值的過度懲罰問題,但是在低秩分解上由于缺少可調(diào)控參數(shù),靈活度不夠.

為此,本文提出一種利用加權(quán)對數(shù)范數(shù)矩陣分解(Weighted Logarithmic norm Matrix Factorization,WLMF)的矩陣填充算法,其中使用加權(quán)對數(shù)范數(shù)作為秩函數(shù)的非凸替代函數(shù),通過引入權(quán)重參數(shù)和指數(shù)參數(shù),能更靈活的進(jìn)行矩陣分解并進(jìn)一步地抑制大奇異值的過度懲罰.

1 相關(guān)工作

給定一個(gè)不完整的觀測矩陣Y∈m1×m2,矩陣Y的部分元素缺失,其他可觀測的元素可能被噪聲污染.設(shè)W∈m1×m2為一個(gè)0-1指示矩陣,元素1和0取值分別映射被觀察到和缺失元素的位置[4].考慮到噪聲的存在,矩陣填充問題的一般模型為:

(2)

其中⊙表示Hadamard積,第一項(xiàng)φ(·)是與X秩函數(shù)相關(guān)的低秩正則化項(xiàng),第二項(xiàng)h(·)是消除噪聲的數(shù)據(jù)擬合項(xiàng),λ>0為懲罰參數(shù).針對不同的噪聲類型,可以使用不同的擬合項(xiàng).例如,稀疏噪聲常用1范數(shù)刻畫,高斯噪聲常用F范數(shù)刻畫.由于直接極小化矩陣秩函數(shù)是NP-難的,低秩正則化項(xiàng)通常使用凸的核范數(shù)來替代,即其中σi(X)表示X的第i大奇異值,其順序按大小遞減排列.為了抑制大奇異值的過度懲罰,Gu等[2]提出加權(quán)核范數(shù)作為秩函數(shù)的非凸替代函數(shù),即

但是,使用式(2)中的極小化框架,矩陣填充需要執(zhí)行完整的SVD.為了解決這個(gè)問題,研究人員設(shè)計(jì)了一個(gè)具有可分離的低秩正則化雙因子框架來代替式(2):

(3)

其中U∈m1×r和V∈m2×r是因子矩陣,滿足r?min{m1,m2}.式(3)在優(yōu)化求解過程中只需要在兩個(gè)因子矩陣上計(jì)算SVD,不需要像式(2)優(yōu)化時(shí)需要計(jì)算大規(guī)模矩陣的SVD,從而顯著降低計(jì)算成本和時(shí)間.在此框架內(nèi),Cabral等[4]提出了矩陣核范數(shù)的雙因子等價(jià)替代,等式如下:

(4)

但這種方法沒有避免核范數(shù)極小化結(jié)果偏離真實(shí)秩極小化結(jié)果的問題.為此,Chen等[6]提出了重加權(quán)核范數(shù)的雙因子等價(jià)替代,等式如下:

(5)

(6)

2 利用加權(quán)對數(shù)范數(shù)因子分解的矩陣填充

首先介紹加權(quán)對數(shù)范數(shù)因子分解的相關(guān)定義與理論性質(zhì),然后給出基于加權(quán)對數(shù)范數(shù)因子分解的矩陣填充模型和求解算法.

2.1 加權(quán)對數(shù)范數(shù)因子分解

在秩極小化問題中,研究人員使用秩的非凸替代函數(shù)代替秩函數(shù).基于此,本文提出如下的加權(quán)對數(shù)范數(shù)作為秩的非凸替代函數(shù).對于任意矩陣X∈m1×m2,定義

(7)

其中σi(X)表示X的第i個(gè)奇異值,0

圖1 秩函數(shù)與不同秩代替函數(shù)的對比圖σ表示奇異值,f(σ)表示函數(shù)值

嚴(yán)格來說,加權(quán)對數(shù)范數(shù)只是一種偽范數(shù),因其不滿足范數(shù)的三角不等式.從圖1可以看出與其他秩替代函數(shù)相比,它可以更大程度上抑制大的奇異值懲罰度,懲罰的程度可以通過調(diào)整參數(shù)p來靈活控制.同時(shí),權(quán)重w的引入,不僅可以進(jìn)一步降低大奇異值的懲罰程度,還可以降低小奇異值的懲罰程度.其中小的奇異值通常被認(rèn)為是噪聲,這使得模型更加具有魯棒性.雖然加權(quán)對數(shù)范數(shù)整體的函數(shù)值小于秩函數(shù),但是不同大小的奇異值的懲罰度更加相近.

類似于式(4)中核范數(shù)與雙因子矩陣F范數(shù)的等價(jià)關(guān)系,本文提出加權(quán)對數(shù)范數(shù)的雙因子等價(jià)替代,結(jié)果見如下定理1.與Chen等提出的結(jié)果(式(6))相比,其矩陣分解只能在p=1/2時(shí)進(jìn)行,而本文提出的雙因子分解具有更高的調(diào)控靈活性,p可取(0,1]范圍內(nèi)的任意值時(shí)進(jìn)行分解.同時(shí),權(quán)重w的引入也增強(qiáng)了本文提出模型的可擴(kuò)展性.

引理2設(shè)f(ex)=log(wepx+1),0

(8)

其中σi(U)、σi(V)、σi(X)分別是矩陣U、V、X的第i個(gè)奇異值.

證明要證明不等式(8)成立,只需要證明函數(shù)f(ex)=log(wepx+1)是一個(gè)關(guān)于x的單調(diào)遞增的凸函數(shù).對任意x≥0,f(ex)關(guān)于x的一階導(dǎo)數(shù)(1/wepx+1)(wpepx)≥0,說明它是一個(gè)關(guān)于x的單調(diào)遞增函數(shù);再者,其二階導(dǎo)p2wepx(wepx+1)-2≥0,說明它是一個(gè)關(guān)于x的凸函數(shù).由引理1可知,不等式(8)成立.

定理1假設(shè)矩陣X∈m1×m2可以分解為X=UVT,其中U∈m1×r,V∈r×m2和rank(X)≤r≤min{m1,m2},則有如下等式成立:

(9)

其中c可取(0,2],0

證明首先,根據(jù)不等式(8),有如下不等式:

其中第二個(gè)不等式由楊氏不等式[8]2ab≤a2+b2,?a,b≥0可得.根據(jù)加權(quán)對數(shù)范數(shù)的定義和rank(X)≤r,可得:

(10)

(11)

綜合式(10)和式(11),定理1結(jié)果得證.

除了雙因子分解形式,定理1還可以推廣到多因子分解形式.在給出結(jié)論之前,先給出以下引理:

引理3設(shè)有函數(shù)fp(ex)=log(wepx+1),x∈[0,+∞),0

n·fc/n(x1x2…xn)≤fc(x1)+fc(x2)+…+fc(xn),

(12)

其中p=c/n,n∈N+.

證明

接下來,提出加權(quán)對數(shù)范數(shù)的多因子分解等價(jià)定理.

定理2給定矩陣X∈m1×m2,設(shè)X可以分解為其中X1∈m1×r1,Xi∈ri-1×ri(i=2,…,n-1),Xn∈rn-1×m2,rank(X)≤ri≤min{m1,m2}(i=1,…,n-1),則有

(13)

其中第一個(gè)不等式自然成立;第二個(gè)不等式由引理3得到;第三個(gè)不等式是基于r≤min{m1,r1},r≤min{m2,rn-1}以及r≤min{ri-1,ri}(i=2,…,n-1).因此,以下不等式成立:

(14)

(15)

結(jié)合式(14)(10)和式(15),定理2結(jié)論得證.

2.2 矩陣填充模型

在式(2)的秩極小化框架下,使用加權(quán)對數(shù)范數(shù)作為矩陣填充問題的低秩正則化項(xiàng),考慮高斯噪聲,提出如下模型:

(16)

根據(jù)定理2,上式可以等價(jià)地轉(zhuǎn)化為多因子分解形式,模型如下:

(17)

其中X1∈m1×r1,Xi∈ri-1×ri(i=2,…,n-1),Xn∈rn-1×m2,而W∈m1×m2表示0-1指示矩陣.式(16)和式(17)中的變量滿足如下關(guān)系:其中rank(X)≤r≤min{m1,m2}(i=1,…,n-1).

2.3 模型求解

由于式(17)中的耦合變量難以優(yōu)化,本文應(yīng)用臨近交替極小化框架(Proximal Alternating Minimization, PAM)[9]對模型進(jìn)行高效求解.在臨近交替極小化框架中,不同的優(yōu)化變量被分解為耦合因子,這些矩陣因子依次進(jìn)行更新.例如,對于第k次迭代,在固定其他因子的情況下,極小化關(guān)于第i個(gè)因子矩陣Xi的優(yōu)化問題:

(18)

(19)

(20)

接下來,討論子問題式(20)的求解.給定一個(gè)矩陣A∈m1×m2,設(shè)其進(jìn)行奇異值分解為A=UAΣAVAT,其中ΣA=diag(σ1(X),…,σmin{m1,m2}(X)).設(shè)α>0,考慮如下優(yōu)化問題:

(21)

根據(jù)范數(shù)的酉不變性,可得

其中Tr(·)表示跡范數(shù),式中的不等式是基于von Neumann跡不等式[12],且當(dāng)X的奇異值分解使用UA和VA分別作為左奇異向量和右奇異向量時(shí),等式成立.從而,式(21)可以改寫為:

(22)

其中σi(X)(i=1,…,min{m1,m2})和σi(A)(i=1,…,min{m1,m2})分別是X和A的第i個(gè)奇異值.

在問題(22)中,可以使用廣義奇異值閾值算子(Generalized Singular Value Thresholding, GSVT)[13]來求解形式如下的問題:

(23)

(24)

其中xi=σi(X),ai=σi(A),g(x)=αlog(wxc+1).

問題(24)通過GSVT計(jì)算最大的局部最小值點(diǎn)為xi,然后比較0和xi處的函數(shù)值大小,得到最優(yōu)解

?fai(xi)=0,0

算法:WLMF算法輸入:Y∈?m1×m2,λ,n,c,μmin,kmax;輸出:Xki ;1.初始化:{X0i}={X1i},t1=1,ω1=0,k=1,i=1;2.更新μki=max{L(di(Xki),μmin)},其中L(di(Xki))=‖Qk1,i‖2·‖Qk2,i‖2是di(Xki)的Lipschitz常數(shù);3.更新ωki=min{(tk-1-1)/tk,0.9999μk-1i/μki},其中tk=(1+1+4t2k-1)/2;4.更新[Xki]=Xki+ωki(Xki-Xk-1i);5.根據(jù)式(23)更新Xk+1i=UAdiag(Proxg(A))VAT;6.i=i+1;7.若i>n,則k=k+1,i=1;8.若k=kmax或收斂,輸出結(jié)果,否則轉(zhuǎn)至2;

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

(25)

同時(shí)為了驗(yàn)證本文算法的收斂性,提出算法的終止準(zhǔn)則是連續(xù)兩個(gè)重構(gòu)矩陣的相對變化(RelCha)足夠小.RelCha表示為:

(26)

其中η>0是一個(gè)給定的容許值.

表1 不同模型的合成數(shù)據(jù)修復(fù)結(jié)果

3.1 合成數(shù)據(jù)修復(fù)

針對合成數(shù)據(jù)的修復(fù),構(gòu)造了一個(gè)大小為600×600的秩為30的隨機(jī)非負(fù)矩陣.構(gòu)造方法為先生成兩個(gè)大小為600×30的隨機(jī)非負(fù)矩陣U和V,然后兩者相乘得到合成矩陣,即X=UVT,并隨機(jī)抽取5%的元素作為觀測矩陣.使用n=2和c=0.8的WLMF進(jìn)行實(shí)驗(yàn),并設(shè)置秩參數(shù)r=35.各模型實(shí)驗(yàn)結(jié)果取十次實(shí)驗(yàn)的平均值.表1展示了各模型在合成數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果.

從表1的實(shí)驗(yàn)結(jié)果可以看出本文提出的WLMF算法在對比實(shí)驗(yàn)中取得了最好的實(shí)驗(yàn)結(jié)果,并且與未進(jìn)行矩陣分解的算法相比,WLMF算法的運(yùn)行時(shí)間要短許多.

3.2 彩色圖像修復(fù)

為了更好的對比5種算法的修復(fù)性能,本文在多張彩色圖片上進(jìn)行圖像實(shí)驗(yàn).自然圖像通?？梢员灰暈榻频牡椭染仃嘯1],由于其具有三個(gè)顏色通道,因此實(shí)驗(yàn)通過矩陣填充算法分別修復(fù)每個(gè)通道.以圖2(見下頁)中像素大小為300×300的6張?jiān)紙D像作為實(shí)驗(yàn)對象,隨機(jī)抽取其像素的15%作為實(shí)驗(yàn)的觀測矩陣.在實(shí)驗(yàn)中,使用n=2和c=0.8的WLMF進(jìn)行實(shí)驗(yàn),并設(shè)置秩參數(shù)r=20.

各算法的定量實(shí)驗(yàn)結(jié)果如表2所示,所有結(jié)果均為10次實(shí)驗(yàn)的平均值.除了每張圖片的修復(fù)結(jié)果,表中還記錄了6幅圖像修復(fù)結(jié)果的平均值和運(yùn)行時(shí)間的平均值.從表2可以看出,本文提出的WLMF算法在所有模型中得分最高.平均而言,它比其他算法有明顯的優(yōu)勢.同時(shí),對比各算法的運(yùn)行時(shí)間,可以發(fā)現(xiàn)本文提出的算法運(yùn)行時(shí)間較短.另外,圖3展示了Image-3在各算法模型上實(shí)驗(yàn)的視覺比較.可以更直觀的看出,WLMF算法可以更好的修復(fù)圖像的細(xì)節(jié),更接近原始圖像.

圖2 原始彩色圖像

圖3 Image3在不同模型下的實(shí)驗(yàn)結(jié)果

表2 不同模型的彩色圖片修復(fù)結(jié)果

3.3 參數(shù)靈敏度分析

圖4 PSNR隨秩參數(shù)的變化圖

為了研究秩參數(shù)r對圖像修復(fù)的影響,進(jìn)一步測試了具有不同秩參數(shù)r的WLMF算法性能.每個(gè)場景下PSNR隨r的變化如圖4所示.可以發(fā)現(xiàn),六張彩色圖片實(shí)驗(yàn)結(jié)果數(shù)值總體趨勢隨著r的增大而增大,并在r=20之后趨于穩(wěn)定,即使在增大r實(shí)驗(yàn)結(jié)果也沒有明顯變化.該結(jié)果表明,所提出的WLMF模型對于秩參數(shù)的選擇具有一定的魯棒性.

3.4 算法收斂性

圖5是當(dāng)Image-3的采樣率為15%時(shí)算法WLMF的RelCha隨迭代次數(shù)的變化曲線,三條曲線表示三條顏色通道.從變化曲線可以看出,隨著迭代次數(shù)的增加,RelCha值迅速減小并趨于0,說明WLMF算法具有較好的收斂性.

4 總結(jié)

在本文中,提出了一種加權(quán)對數(shù)范數(shù)矩陣分解算法WLMF來求解矩陣填充問題.該算法結(jié)合了秩函數(shù)的非凸替代和低秩矩陣分解,使得該算法具有更好的恢復(fù)性能,并提高了計(jì)算效率.數(shù)值實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性,在整體視覺效果和局部細(xì)節(jié)保留方面優(yōu)于對比的經(jīng)典算法.