穩定廣義低秩矩陣逼近算法

史加榮 米合拉衣·阿地勒

1(西安建筑科技大學省部共建西部綠色建筑國家重點實驗室 陜西 西安 710055)2(西安建筑科技大學理學院 陜西 西安 710055)

0 引 言

在模式識別、機器學習和計算機視覺等領域中，通常假設數據集存在于單個或多個低維線性子空間中。矩陣分解正是利用數據集的近似低秩結構來恢復低秩成分、移除噪聲和補全缺失值[1]。對于灰度圖像集等二維數據集，在使用傳統的主成分分析(Principal Component Analysis,PCA)、奇異值分解(Singular Value Decomposition,SVD)和線性判別分析(Linear Discriminant Analysis,LDA)等子空間學習方法時，需要先將矩陣拉伸為向量，這種向量化破壞了數據本身的空時結構，也可能會導致小樣本問題和維數災難[2]。為此，許多一維子空間方法相繼被推廣到二維情形，例如：二維PCA[3]、二維SVD[4]、二維LDA[5]、雙向二維PCA[6]和廣義低秩矩陣逼近[7]等。

與SVD相比，GLRAM具有更好的壓縮性能和較低的計算量，已成為處理二維數據集的一種重要方法。Liu等[8]揭示了GLRAM與SVD的關系，討論了GLRAM目標函數的下界。趙揚揚等[9]提出了求解GLRAM的非迭代算法；Shi等[10]基于GLRAM提出了求解矩陣補全問題；Ren等[11]使用GLRAM構造了一個統一的網絡來學習高維映射；Luo等[12]將GLRAM和隨機低秩矩陣逼近應用到視頻處理中；張長倫等[13]建立了GLRAM的一個改進模型。當數據集受到大的噪聲腐蝕時，GLRAM可能不再奏效。為此，Shi等[14]提出了魯棒GLRAM(Robust GLRAM, RGLRAM)，隨后Wang等[15]把秩最小化引入到魯棒模型中。盡管RGLRAM在圖像恢復和視頻背景建模中取得了良好的效果[14-16]，但該模型沒有考慮高斯噪聲腐蝕和數據缺失情形。基于此，本文提出RGLRAM的一個新版本，即穩定廣義低秩矩陣逼近。

1 相關工作

1.1 廣義低秩矩陣逼近

Di=LMiRT+Eii=1,2,…,N

(1)

式中：L∈Rm×r1和R∈Rn×r2均為正交變換矩陣；Mi∈Rr1×r2；噪聲矩陣Ei∈Rm×n；r1和r2滿足max(r1,r2)

假設噪聲矩陣Ei的元素服從獨立同分布的均值為0的高斯分布，根據極大似然估計法可得GLRAM的最小化模型：

(2)

s.t.LTL=Ir1RTR=Ir2

(3)

s.t.LTL=Ir1RTR=Ir2

一般而言，上述優化問題沒有閉形式解，可通過奇異值分解來交替求解L和R[7]。

1.2 魯棒廣義低秩矩陣逼近

GLRAM模型適用于高斯噪聲情形，但不能很好地處理大的稀疏噪聲。文獻[14]提出了魯棒廣義低秩矩陣逼近(RGLRAM)模型。為了增強模型對稀疏噪聲的魯棒性，假設式(1)中Ei的元素服從獨立同分布的均值為0的拉普拉斯分布。基于極大似然估計法，可建立以下l1范數最小化問題:

(4)

s.t.LTL=Ir1RTR=Ir2

(5)

s.t.Di=LMiRT+Eii=1,2,…,N

LTL=Ir1RTR=Ir2

2 穩定廣義低秩矩陣逼近

基于稠密高斯噪聲與稀疏噪聲疊加這一假設，建立了穩定廣義低秩矩陣逼近算法(SGLRAM)。

2.1 SGLRAM模型建立

假設數據矩陣Di同時受到大的稀疏噪聲和高斯噪聲腐蝕，則可將它分解為如下三項之和：

Di=LMiRT+Ei+Gii=1,2,…,N

(6)

式中：Ei是稀疏噪聲矩陣；Gi是高斯噪聲矩陣。進一步考慮矩陣Di均存在數據缺失，缺失元素對應的二維指標集記為Ωi，即當且僅當(k,l)∈Ωi時，Di的第k行第l列元素未缺失。為描述方便起見，將Di的缺失元素補充為0，新得到的矩陣記為Zi。對于Ωi，引入正交投影算子ΡΩi(·):Rm×n→Rm×n，其定義為PΩi(Di)=Zi。建立如下的SGLRAM模型：

(7)

s.t.Di=LMiRT+Ei+Gi

PΩi(Di)=Zii=1,2,…,N

LTL=Ir1RTR=Ir2

(8)

s.t.Xi=LMiRT+Ei+Gi

Di=XiPΩi(Di)=Zii=1,2,…,N

LTL=Ir1RTR=Ir2

上述最小化問題等價于：

(9)

s.t.Xi=LMiRT+Ei+Gi

Di=XiPΩi(Di)=Zii=1,2,…,N

LTL=Ir1RTR=Ir2

式中：μ>0。在不考慮ΡΩi(Di)=Zi和正交約束情形下，構造式(9)的拉格朗日函數：

(10)

2.2 SGLRAM模型求解

式(9)是非凸的，因此無法直接使用現有的壓縮感知方法求解。下面給出求解此優化問題的ADMM方法，即采用交替更新策略，每次只更新一個塊變量。

(1)更新L。當L未知且其他變量固定時，L的計算過程如下：

(11)

(12)

(13)

式中：QR(·)是矩陣的QR分解。容易證明：當更新完L和M后，fμ(L,R,M,D,E,G,X)值不會增加。

(2)更新M。當M未知且其他變量不變時，M的計算過程如下：

(14)

R:=QR(T)

(15)

(4)更新E。當E未知且其他變量不變時，E的計算過程如下：

(16)

式中：Sσ(·):Rm×n→Rm×n為絕對值閾值算子[18]。

(5)計算G。根據以下公式更新G：

〈Y1,Xi-LMiRT-Ei-Gi〉=

(17)

因此，fμ關于Gi偏導數為:

記Om×n為m×n維零矩陣，令▽Gifμ=Om×n，得到Gi的更新公式：

(18)

(6)計算X。當X未知且其他變量不變時，X的計算過程如下：

(19)

(20)

(7)計算D。當D未知且其他變量不變時，D的計算過程如下：

(21)

考慮到約束ΡΩi(Di)=Zi，進一步得到Di的迭代公式為:

(22)

(23)

(9)計算μ。根據以下公式更新μ：

μ:=min{ρμ,μmax}

(24)

式中：ρ>1為一個常數；μmax是μ的最大取值。

算法1列出求解SGLRAM的ADMM算法的整個過程。

算法1求解SGLRAM的ADMM算法

輸出：L、M、R、E、G、X和D。

初始化：L，R，Mi=LTZiR，Xi=Di=Zi，

迭代步驟如下，直至收斂。

1.根據式(13)更新L。

2.根據式(14)更新Mi,i=1,2,…,N。

3.根據式(15)更新R。

4.根據式(14)更新Mi,i=1,2,…,N。

5.根據式(16)更新Ei,i=1,2,…,N。

6.根據式(18)更新Gi,i=1,2,…,N。

7.根據式(20)更新Xi,i=1,2,…,N。

8.根據式(22)更新Di,i=1,2,…,N。

10.根據式(24)更新μ。

11.如果終止條件滿足，終止算法；否則，轉第1步。

在算法1中，可按如下方式隨機初始矩陣L和R：L=orth(randn(m,r1))，R=orth(randn(n,r2))，其中randn(m,r1)表示按標準正態分布隨機生成的m×r1維矩陣，orth(·)是按列標準正交化算子。算法1的收斂條件可以設置為：

(25)

或者達到最大迭代次數，其中ε是一個足夠小的正數。在后面的實驗中，取ρ=1.1，μmax=1010，ε=10-9。

3 數值實驗與結果分析

在人工合成數據集和ORL人臉數據集上進行實驗，并將SGLRAM的實驗結果與GLRAM、RGLRAM的結果進行比較。采用MATLAB R2012a進行編程，所有實驗在處理器為Intel(R)Core(TM)i5-7400 @3 GHz的個人計算機上運行。

3.1 合成數據集實驗

根據以下公式人工合成N個數據矩陣：

Di=Ai+Ei+Gii=1,2,…,N

(26)

式中：Di∈Rm×n；Ai是低秩矩陣；Ei是稀疏噪聲矩陣，Gi是高斯噪聲矩陣。具體地，Ai按如下方式產生：

Ai=orth(U)Si(orth(V))T

(27)

(28)

相對誤差越小，恢復性能越好。用兩個逆信噪比(Inverse Signal-to-Noise Ratio,ISNR)分別來度量稀疏噪聲和高斯噪聲的噪聲大小，其定義如下：

(29)

設計兩組實驗來比較算法的性能，部分參數設置如下：m=n=100，N=50，r1=r2=20，λ=0.2，q=0.1，最大迭代次數為300。將實驗重復10次，最終報告平均結果。

在第一組實驗中，不考慮數據缺失情形。取a∈{0.5,1,2}，σ∈{0.05,0.10}。a與σ不同組合取值下的實驗結果如表1所示。可以看出：當σ固定時，a的取值對SGLRAM和RGLRAM的影響較小，這說明這兩種方法對稀疏噪聲更加魯棒；SGLRAM具有最好的低秩恢復性能，其相對誤差比RGLRAM的結果小0.004 9～0.015 1；當a固定時，σ的取值越大，SGLRAM的恢復性能越差，這說明高斯噪聲水平對SGLRAM的恢復性能具有重要的影響；SGLRAM的運行時間最長，大約是GLRAM的5倍，是RGLRAM的1.8倍。總之，盡管SGLRAM的運行時間較長，但它在移除稀疏噪聲與高斯噪聲方面優于GLRAM和RGLRAM。

表1 (a,σ)不同取值的實驗結果

(a)σ=0.05

3.2 ORL人臉數據集實驗

選取英國劍橋大學Olivetti研究所的ORL人臉數據集作為實驗數據。該數據集包含40個不同年齡、不同性別的人，在不同時間共獲取400幅灰度圖像，其中每個人有10幅不同的圖像，且拍攝傾斜角度和旋轉角度最大可達20°。這些圖像展示了不同的表情和面部細節，每幅圖像均被標準化為64×64的分辨率。對于第i幅圖像，對其添加密度為0.1的椒鹽噪聲，記對應的含噪矩陣為Di，i=1,2,…,400。根據Di的近似低秩性來移除噪聲。

對于SGLRAM，其他參數設置如下：r1=r2=20，λ=1，最大迭代次數為300。圖2給出了GLRAM、RGLRAM、SGLRAM三種模型的部分圖像的恢復結果。可以看出：GLRAM對稀疏的椒鹽噪聲比較敏感，而RGLRAM和SGLRAM卻較好地移除了大的稀疏噪聲。

(a)原始圖像 (b)噪聲圖像 (c)GLRAM (d)RGLRAM (e)SGLRAM

對于受椒鹽噪聲腐蝕的人臉圖像，下面考慮三種模型在不同缺失概率p下的恢復結果。令p∈{0.1,0.3,0.5,0.7}，圖3比較了某幅圖像的恢復結果。觀察圖3，可以發現GLRAM具有最差的恢復性能，即使在p=0.1時，它都不能較好地恢復低秩圖像。當p=0.1時，RGLRAM和SGLRAM均得到了較好的恢復結果，此時RGLRAM將缺失元素當作稀疏噪聲，具有一定的魯棒性。當p≥0.3時，RGLRAM具有較差的恢復性能，而SGLRAM具有較好的恢復性能。綜上，SGLRAM不但對稀疏噪聲具有魯棒性，而且對缺失元素還具有一定的穩定性。

4 結 語

本文提出了GLRAM的一種穩定模型——SGLRAM。該模型假設低秩數據矩陣同時受到稀疏噪聲和高斯噪聲的腐蝕，并考慮數據存在缺失情形。建立了最小化矩陣l1范數與Frobenious范數的優化問題，并基于ADMM方法設計了迭代算法。實驗結果表明本文方法不但對稀疏噪聲魯棒，而且對缺失數據具有穩定性。SGLRAM的全變差等正則化模型將是今后值得研究的一個方向。