穩(wěn)定廣義低秩矩陣逼近算法

史加榮 米合拉衣·阿地勒

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

0 引 言

在模式識別、機器學(xué)習(xí)和計算機視覺等領(lǐng)域中，通常假設(shè)數(shù)據(jù)集存在于單個或多個低維線性子空間中。矩陣分解正是利用數(shù)據(jù)集的近似低秩結(jié)構(gòu)來恢復(fù)低秩成分、移除噪聲和補全缺失值[1]。對于灰度圖像集等二維數(shù)據(jù)集，在使用傳統(tǒng)的主成分分析(Principal Component Analysis,PCA)、奇異值分解(Singular Value Decomposition,SVD)和線性判別分析(Linear Discriminant Analysis,LDA)等子空間學(xué)習(xí)方法時，需要先將矩陣?yán)鞛橄蛄浚@種向量化破壞了數(shù)據(jù)本身的空時結(jié)構(gòu)，也可能會導(dǎo)致小樣本問題和維數(shù)災(zāi)難[2]。為此，許多一維子空間方法相繼被推廣到二維情形，例如：二維PCA[3]、二維SVD[4]、二維LDA[5]、雙向二維PCA[6]和廣義低秩矩陣逼近[7]等。

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

1 相關(guān)工作

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)

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

(2)

s.t.LTL=Ir1RTR=Ir2

(3)

s.t.LTL=Ir1RTR=Ir2

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

1.2 魯棒廣義低秩矩陣逼近

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

(4)

s.t.LTL=Ir1RTR=Ir2

(5)

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

LTL=Ir1RTR=Ir2

2 穩(wěn)定廣義低秩矩陣逼近

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

2.1 SGLRAM模型建立

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

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

(6)

式中：Ei是稀疏噪聲矩陣；Gi是高斯噪聲矩陣。進(jìn)一步考慮矩陣Di均存在數(shù)據(jù)缺失，缺失元素對應(yīng)的二維指標(biāo)集記為Ωi，即當(dāng)且僅當(dāng)(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和正交約束情形下，構(gòu)造式(9)的拉格朗日函數(shù)：

(10)

2.2 SGLRAM模型求解

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

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

(11)

(12)

(13)

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

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

(14)

R:=QR(T)

(15)

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

(16)

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

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

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

(17)

因此，fμ關(guān)于Gi偏導(dǎo)數(shù)為:

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

(18)

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

(19)

(20)

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

(21)

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

(22)

(23)

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

μ:=min{ρμ,μmax}

(24)

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

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

算法1求解SGLRAM的ADMM算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(25)

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

3 數(shù)值實驗與結(jié)果分析

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

3.1 合成數(shù)據(jù)集實驗

根據(jù)以下公式人工合成N個數(shù)據(jù)矩陣：

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

(26)

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

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

(27)

(28)

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

(29)

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

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

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

(a)σ=0.05

3.2 ORL人臉數(shù)據(jù)集實驗

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

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

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

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

4 結(jié) 語

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