利用加權對數范數分解的矩陣填充算法*

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

(贛南師范大學 數學與計算機科學學院,江西 贛州 341000)

0 引言

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

(1)

其中X∈m1×m2是待恢復的準確數據,Ω表示與觀測數據元素對應的位置集合.

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

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

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

1 相關工作

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

(2)

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

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

(3)

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

(4)

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

(5)

(6)

2 利用加權對數范數因子分解的矩陣填充

首先介紹加權對數范數因子分解的相關定義與理論性質,然后給出基于加權對數范數因子分解的矩陣填充模型和求解算法.

2.1 加權對數范數因子分解

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

(7)

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

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

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

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

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

(8)

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

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

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

(9)

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

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

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

(10)

(11)

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

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

引理3設有函數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+.

證明

接下來,提出加權對數范數的多因子分解等價定理.

定理2給定矩陣X∈m1×m2,設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)

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

(14)

(15)

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

2.2 矩陣填充模型

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

(16)

根據定理2,上式可以等價地轉化為多因子分解形式,模型如下:

(17)

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

2.3 模型求解

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

(18)

(19)

(20)

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

(21)

根據范數的酉不變性,可得

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

(22)

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

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

(23)

(24)

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

問題(24)通過GSVT計算最大的局部最小值點為xi,然后比較0和xi處的函數值大小,得到最優解

?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常數;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.根據式(23)更新Xk+1i=UAdiag(Proxg(A))VAT;6.i=i+1;7.若i>n,則k=k+1,i=1;8.若k=kmax或收斂,輸出結果,否則轉至2;

3 實驗

(25)

同時為了驗證本文算法的收斂性,提出算法的終止準則是連續兩個重構矩陣的相對變化(RelCha)足夠小.RelCha表示為:

(26)

其中η>0是一個給定的容許值.

表1 不同模型的合成數據修復結果

3.1 合成數據修復

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

從表1的實驗結果可以看出本文提出的WLMF算法在對比實驗中取得了最好的實驗結果,并且與未進行矩陣分解的算法相比,WLMF算法的運行時間要短許多.

3.2 彩色圖像修復

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

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

圖2 原始彩色圖像

圖3 Image3在不同模型下的實驗結果

表2 不同模型的彩色圖片修復結果

3.3 參數靈敏度分析

圖4 PSNR隨秩參數的變化圖

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

3.4 算法收斂性

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

4 總結

在本文中,提出了一種加權對數范數矩陣分解算法WLMF來求解矩陣填充問題.該算法結合了秩函數的非凸替代和低秩矩陣分解,使得該算法具有更好的恢復性能,并提高了計算效率.數值實驗結果驗證了算法的有效性,在整體視覺效果和局部細節保留方面優于對比的經典算法.