一種自適應的魯棒性矩陣補全方法

萬 星, 周水生

(西安電子科技大學 數學與統計學院, 西安 710126)

1 引言與預備知識

當矩陣元素存在未知或缺失時, 可采用矩陣補全方法[1-2]根據已知元素估計未知元素, 找到與原始矩陣盡可能相似的矩陣. 目前, 矩陣補全已在圖像恢復[3-4]與去噪[5]、 人體運動捕捉[6-7]和推薦系統[8-9]等領域廣泛應用. 矩陣補全可通過求解秩最小化問題實現對未知元素的補全, 但由于秩函數的非凸性和不連續性, 因此求解秩最小化問題是NP難問題. Fazel[10]提出了使用核范數對秩函數做凸松弛, 但基于核范數最小化方法的一個主要缺陷是所有奇異值同時被最小化, 因此在實際應用中不能很好地逼近秩. 為更精確刻畫低秩部分, Zhang等[11]提出了截斷核范數正則化(truncated nuclear norm regularization, TNNR)方法, 不同于基于核范數方法最小化所有奇異值的求和, 而是由核范數減去最大的幾個奇異值之和得到截斷核范數, 該方法可更好近似原始矩陣的精確解. Hu等[12]將原始矩陣補全問題進行松弛, 采用平方F(Frobenius)范數將約束項以懲罰函數的方式轉換為無約束優化問題, 該模型可較好地處理高斯噪聲, 但由于模型中的平方損失是光滑的, 當預測值與真實值差異較大時, 平方項的懲罰力度較大, 因此對異常值較敏感, 所以該算法無法精確處理奇異噪聲損壞的數據. Hu等[13]對具有固定秩的矩陣補全模型進行了改進, 由于L1損失對異常值更魯棒, 提出了將目標函數中的平方F范數替換為L1范數, 得到一個具有魯棒性的低秩矩陣補全模型, 但L1損失的導數是不連續的, 所以對其求解較困難. Gao等[14]對二維主成分分析(2-dimensional principal component analysis, 2DPCA)模型進行了改進, 由于2DPCA在目標函數中采用平方F范數作為距離度量, 這種距離度量會增加重構誤差, 尤其在存在異常值的情形下, 為解決平方F范數對異常值敏感的問題, 提出了采用F范數作為距離度量的角度-二維主成分分析(angle-2-dimensional principal component analysis, Angle-2DPCA)方法, 因為與平方F范數相比, F范數能減弱大距離的影響. 本文基于F范數對異常值魯棒的優勢, 結合上述分析, 提出一種自適應的魯棒性矩陣補全方法.

在矩陣補全問題中, 為增加矩陣補全算法的魯棒性, 本文對文獻[12]的模型進行改進, 主要針對被奇異噪聲損壞的缺失矩陣, 在目標函數中采用對奇異噪聲魯棒的F范數作為損失項恢復矩陣中的缺失值, 以降低異常值對算法的影響, 提高恢復精確度. 在求解該模型過程中, 先采用凸優化技巧引入一個動態權重參數, 使其在更新恢復值時可根據當前恢復誤差大小自適應地調節下一次的迭代更新, 以便快速精確地進行補全, 再進一步建立求解優化問題的有效迭代方法. 實驗結果表明, 本文算法相比于傳統算法恢復性能得到較大提升, 不僅提高了缺失矩陣的重建精確性, 對截斷秩的隨機選取恢復效果也較穩定.

低秩矩陣補全可通過求解秩最小化問題實現對未知元素的補全. 給定一個只有部分觀測元的矩陣M∈m×n, 設X為想要恢復的矩陣,Ω是矩陣M中已觀測到元素的下標集合,PΩ是正交投影算子, rank(·)為秩函數, 則求解秩最小化問題可表示為

(1)

由于秩函數的非凸性和不連續性, 因此求解問題(1)是NP難問題. Fazel[10]首先使用了核范數對秩函數做凸松弛, 核范數與矩陣秩的關系類似于向量的L1范數與L0范數之間的關系[15]. 目前, 基于核范數的求解方法有奇異值閾值法(singular value threshold, SVT)[16]、 核范數正則最小二乘法(nuclear norm regularized least squares, NNLS)[17]和魯棒主成分分析法(robust principal component analysis, Robust PCA)[18]等. 矩陣核范數最小化模型可表示為

(2)

基于核范數最小化方法的主要缺點是所有奇異值同時被最小化, 在實際應用中可能不能很好地逼近秩函數. Zhang等[11]提出了截斷核范數正則化方法, 與基于核范數方法最小化所有奇異值的求和不同, 其不改變前r個最大奇異值大小, 通過最小化奇異值序列中剩余的(min{m,n}-r)個奇異值之和, 得到一個更精確的函數, 即截斷核范數逼近秩函數：

(3)

與傳統核范數極小化問題不同, 截斷核范數極小問題不是凸問題, 所以凸優化的標準方法不能直接用于解決該問題.文獻[12]將非凸優化問題(3)改寫為如下凸問題求解：

(4)

其中X∈m×n,A∈r×m,B∈r×n,AAT=BBT=Ir×r,I是單位矩陣.

(5)

ADMM方法可較好地處理各種噪聲, 但對于截斷秩參數r的隨機選取易得到不穩定的恢復效果, 且ADMM方法解決問題(5)是一個硬約束問題, 算法復雜度較高. 文獻[12]提出了APGL優化方法, 將原始的矩陣補全問題進行松弛, 采用平方F范數將約束項以懲罰函數的方式轉換為下列無約束優化問題, 降低了求解的復雜度:

(6)

APGL方法可較好地處理高斯噪聲, 但由于模型(6)中平方損失是光滑的, 當預測值與真實值差異較大時, 平方項的懲罰力度較大, 因此對異常值較敏感, 所以該算法無法精確處理奇異噪聲損壞的數據. 為更好地補全被奇異噪聲損壞的缺失矩陣, 本文提出一種改進的模型, 并給出其求解算法.

2 模型與求解

2.1 建立模型

文獻[14]中, 2DPCA在目標函數中采用平方F范數作為距離度量, 這種距離度量不僅會增加重構誤差, 而且在有異常值的情形下, 會使實際投影方向與理想解的偏離明顯, 從而影響算法的魯棒性. 為解決平方F范數對異常值敏感的問題, Gao等[14]提出了采用F范數作為距離度量的Angle-2DPCA方法. 該方法通過最小化重建誤差與方差的比值獲得最優投影矩陣, 其不僅對異常值具有魯棒性, 還具有旋轉不變性. 在矩陣補全問題中, 式(6)采用了平方F范數作為損失項恢復矩陣中的缺失值, 但由于平方F范數對異常值較敏感, 因此在恢復被奇異噪聲損壞的缺失矩陣時, 其魯棒性并不理想. 根據文獻[14], 將平方F范數替換為F范數, 可增強算法的魯棒性. 基于此, 本文提出下列魯棒性矩陣：

(7)

2.2 求解模型

對于模型(7), 由于F范數項不易求導, 因此一般的求解方法較困難.為精確和快速地求解模型(7), 本文基于凸優化技巧[19], 給出其等價式：

(8)

其中τ是一個動態權重參數, 該權重參數可在更新恢復值時根據當次恢復誤差大小自適應地調整恢復值的下次迭代更新, 使恢復值與真實值的差異越來越小, 從而提高算法的恢復性能.參數τ根據式(8)一階導數為0解得：

(9)

此外, 對于λ>0, 式(8)是一個無約束非光滑凸優化問題, 這類問題近年已在機器學習和計算機視覺中得到廣泛關注.考慮到經典梯度算法不能解決非光滑問題, 文獻[20]提出了許多加速梯度方法, 這些方法都具有處理大規模、 非光滑問題的能力.

Beck等[20]提出了加速近鄰梯度線搜索APGL方法, 該方法是一種特殊的梯度下降方法, 主要用于求解目標函數不可微的最優化問題. 如果目標函數在某些點是不可微的, 則該點的梯度無法求解, 也無法使用傳統梯度下降法. APGL方法的思想是使用鄰近算子作為近似梯度進行梯度下降. 因此, 本文利用加速近鄰梯度線搜索APGL方法求解式(8), 即解決下列形式的問題:

(10)

其中g(X)是一個非可微的凸函數,f(X)是一個光滑且Lipschitz連續的函數.

對于?t>0, 用加速近鄰梯度APGL算法首先在已知的點Y對f(X)進行下列逼近：

(11)

然后, 用改進后的方法通過交替迭代更新X,Y,t和τ解決優化問題.在第k次迭代中, 更新作為Q(X,Yk)的唯一極小值Xk+1：

(12)

本文引入加速近鄰梯度線搜索APGL方法.對于無約束非光滑凸優化問題(8), 選擇

根據式(9)得到參數τk+1更新公式為

τk+1=‖PΩ(Xk+1)-PΩ(M)‖F.

(13)

當預測值與真實值差異較大時, 作為動態加權參數的τk+1值變大可以自適應地調整恢復值的下次迭代更新, 使預測值與真實值的差異越來越小, 從而提高算法的恢復性能.由式(12)可得Xk+1的更新公式為

最后, 用與文獻[21]相同的方式進行τk+1和Yk+1的更新：

(15)

本文通過凸優化理論, 將式(7)巧妙地轉換為式(8), 即將不易求解的式(7)轉化為非光滑凸優化問題.同時引入一個權重參數, 該參數可根據當前恢復誤差大小自適應地調節下一次的迭代更新, 再基于加速近鄰梯度線搜索APGL方法, 給出求解模型對應的迭代公式.

2.3 算法框架

本文主要針對被奇異噪聲損壞的缺失矩陣, 給出一個魯棒性矩陣補全模型, 并引入動態權重參數τ和加速近鄰梯度線搜索APGL方法, 給出一種精確和快速的求解方法. 算法描述如下.

算法1

迭代更新:

直到‖Xk+1-Xk‖F≤ε.

3 實驗結果及分析

人類所能感知的外界信息中, 大部分都來自于視覺信息, 如圖像、 視頻等.因此, 數字圖像處理技術受到廣泛關注.但在許多情形下, 數字圖像可能由于編碼和傳輸問題而部分損壞, 也可能被一些文字或徽標覆蓋而部分損壞, 矩陣補全算法可用于補全這些圖像的缺失信息.因此在本文實驗中, 首先分別處理彩色圖像3個通道(紅、 綠和藍)的每個分量, 然后將每個通道的處理結果合成為最后的恢復結果.為證明本文方法恢復性能的優越性, 在圖像上添加了不同種類的奇異噪聲, 其中包含文本噪聲和各種奇異塊噪聲, 分別用不同的矩陣補全方法對缺失圖像進行恢復, 并將實驗結果的主觀視覺效果和客觀數據結果(峰值信噪比及恢復誤差)與其他的矩陣補全算法進行對比.

3.1 評價方法與參數設置

峰值信噪比(peak signal-to-noise ratio, PSNR)是評價圖像質量的一種常用標準, 本文使用恢復圖像的PSNR值評估不同方法的性能, 其值越高表示圖像的恢復效果越好. 假設圖像缺失像素的總數為T, 則總平方誤差

總均方誤差

峰值信噪比

恢復誤差

Erec=‖X-Xrec‖2.

在實驗中對參數進行調整以獲得最佳的性能.對于ADMM方法, 經驗性地設β=0.05; 對于APGL方法, 經驗性地設參數λ=0.01; 對于本文方法, 設參數λ=16; 對于停止條件, 本文將外部迭代的精度設為10-4, 內部迭代的精度設為3e-4.

3.2 奇異塊噪聲

在某些情形下, 由于被較大且分散的奇異塊污染, 只能得到損壞的缺失圖像, 并且恢復這些缺失數據可能有一定難度. 本文主要對被兩種奇異塊噪聲損壞的圖像進行恢復, 分別為墨水塊噪聲和菱形塊噪聲.

3.2.1 墨水塊噪聲

任取6張大小為300×300的圖像作為原始圖像, 對其添加墨水塊噪聲, 可以看到原始圖像中有部分像素被損壞, 將該被部分損壞的圖像作為缺失圖像, 用本文算法恢復缺失圖像, 實驗結果如圖1所示, 其中第一行為原始圖像, 第二行為缺失圖像, 第三行為本文算法恢復后圖像的最優可視化效果. 由于一般情形下無法得知缺失矩陣的真實秩, 也無法獲得先驗信息應該如何選擇截斷奇異值的數目r, 所以對r值(截斷奇異值的數目)選取[1,10], 任選圖1中的3張圖像(A)、 (D)和(E)利用不同的補全算法進行實驗, 圖2為ADMM算法、 APGL算法及本文算法在取不同秩r時的峰值信噪比PSNR值和恢復誤差值對比結果.

圖1 自適應的魯棒性矩陣補全恢復效果Fig.1 Effect of adaptive robust matrix completion restoration

圖像的秩可以簡單理解為圖像所含信息的豐富程度, 圖像由于局部分塊之間的相似性和重復性, 通常具有低秩的屬性. 圖像的秩較高可能是因為圖像噪聲的影響, 隨著秩的增大, 矩陣的結構變得復雜, 不完全矩陣的恢復也變得困難.

由圖1可見, 恢復圖與原始圖像的相似性較高, 主觀視覺上幾乎看不出原來噪聲污染過的痕跡. 此外, 本文算法恢復的數值結果也較好, 其中圖1(A)～(F)恢復的PSNR值分別為26.29,21.10,23.25,28.30,21.58,38.55 dB.

圖2為不同算法處理圖1(C)～(E)的數值結果. 由圖2可見, 對于該奇異噪聲, 在取不同秩r的情形下, 相比于APGL算法, 本文算法恢復的峰值信噪比值PSNR存在一定程度上的增大, 恢復誤差存在一定程度上的變小, 表明了對于處理該奇異噪聲本文方法恢復性能的優越性. 此外, 相比于ADMM算法, 當秩r=1～4時, 兩種算法的峰值信噪比值PSNR相差較小, 即當矩陣具有很好的低秩性時, 兩種算法都取得了較理想的補全效果. 但自然圖像多數為低秩或者近似低秩的, 當秩r>4時, ADMM算法恢復效果驟然變差, 即峰值信噪比值PSNR突然下降， 恢復誤差突然增大, 表明若將ADMM算法應用到結構較復雜并且近似低秩的自然圖像恢復時, 恢復效果并不理想. 實驗結果表明, ADMM算法對于隨機選取的秩r值較敏感, 所以易得到不穩定的恢復效果. 因此, 對于該奇異噪聲, 本文提出的自適應的魯棒性矩陣補全方法不僅具有更精確的恢復效果, 而且對于截斷秩r的選取也具有魯棒性.

圖2 不同算法處理圖1(C)～(E)的數值結果對比Fig.2 Comparison of numerical results of Fig.1(C)—(E) processed by different algorithms

3.2.2 菱形塊噪聲

先任取大小為300×300的兩張圖像圖1(D)和圖1(F)作為原始圖像, 對其添加菱形塊噪聲得到一張缺失圖像, 然后用ADMM算法、 APGL算法及本文算法進行恢復實驗. 圖3和圖4分別為圖1(D)和圖1(F)恢復后圖像的可視化效果和數值實驗結果.

圖3從左到右分別為圖1(D)和圖1(F)的原始圖像、 菱形塊奇異噪聲損壞的缺失圖像以及3種矩陣補全算法恢復的圖像. 由圖3可見： 在ADMM算法和APGL算法的恢復圖像上可以不同程度地看到未處理干凈的噪聲, 恢復效果較差； 與這兩種算法相比, 本文算法恢復的圖像在視覺效果上更近似于原始圖像, 并且幾乎看不出噪聲污染過的痕跡, 表明本文提出的自適應的魯棒性矩陣補全方法可以有效恢復該奇異噪聲污染的缺失圖像.

圖4從上到下依次為不同矩陣補全方法恢復圖1(D)和圖1(F)的數值結果. 由圖4可見, 在取不同秩r值時, 相比ADMM算法和APGL算法, 本文算法恢復的峰值信噪比值PSNR最大, 恢復誤差值最小. 當圖1(D)的秩r>4時, ADMM算法和APGL算法的峰值信噪比值PSNR突然下降到12 dB以下, 本文算法的PSNR值隨著秩r的增大并未驟然變小, 而是逐漸穩定地減小. 當圖1(F)的秩r>6時, ADMM算法和APGL算法的峰值信噪比值PSNR突然下降到14 dB以下, 本文算法的PSNR值隨著秩r的增大不但未驟然變小, 反而逐漸穩定地增大. 實驗結果表明, 對于該奇異噪聲, 本文提出的自適應的魯棒性矩陣補全方法恢復性能得到了較大提升, 不僅在視覺效果, 而且在數值結果上均取得了較好的恢復效果.

圖3 不同算法處理圖像的視覺效果對比Fig.3 Comparison of visual effects of images processed by different algorithms

圖4 不同算法處理圖1(D),(F)的數值結果對比Fig.4 Comparison of numerical results of Fig.1(D),(F) processed by different algorithms

3.3 文本噪聲

在某些情形下, 由于缺失的圖像上文本字符損壞的位置不是隨機分布的, 文本噪聲可能會破壞矩陣重要的低秩信息, 因此, 數字圖像上文本噪聲的去除有一定難度. 將文本覆蓋的位置視為矩陣補全問題中的缺失項, 對其利用不同的補全方法進行恢復. 對6張大小為300×300的原始圖像(圖1(A)～(F))添加文本噪聲, 由于一般情形下, 無法得知缺失矩陣的真實秩, 也無法獲得先驗信息應該如何選擇截斷奇異值的數目r, 本文分別選取r=10和r=15, 利用不同補全算法進行實驗, 數值實驗結果列于表1. 圖5為圖1(C)和圖1(F)的原始圖像、 缺失圖像以及不同矩陣補全方法恢復的結果(r=10). 由表1可見, 對于6張不同的圖像, 選取截斷秩r=10和r=15時, 相比于ADMM算法和APGL算法, 本文算法取得了最大的峰值信噪比值PSNR, 驗證了本文提出的自適應的魯棒性矩陣補全方法具有較好的恢復性能.

表1 不同算法處理圖像的PSNR值(dB)

圖5為不同矩陣補全算法恢復后的圖像可視化效果對比結果. 由圖5可見, 本文算法能很好地恢復由于文本噪聲而導致的缺失像素, 并且取得了比ADMM算法和APGL算法更好的主觀視覺效果. 此外, 在客觀數值結果上, 本文算法也獲得了較高的峰值信噪比值PSNR. 其中: 對于圖1(C), ADMM算法、 APGL算法以及本文算法得到的PSNR值分別為21.95,26.15,28.81 dB; 對于圖1(F), ADMM算法、 APGL算法以及本文算法得到的PSNR值分別為21.71,38.25,45.02 dB. 因此, 針對文本噪聲損壞的缺失矩陣, 本文提出的自適應的魯棒性矩陣補全方法不僅提高了缺失矩陣的重建精確性, 在秩的隨機選取下也具有較穩定的恢復效果.

圖5 不同算法作用于不同圖像的視覺效果對比Fig.5 Visual effect comparison of different algorithms act on different images

綜上所述, 本文基于截斷核范數進行低秩約束補全矩陣中的缺失值, 為增加矩陣補全算法的魯棒性, 提出了一種自適應的魯棒性矩陣補全方法. 主要針對被奇異噪聲損壞的缺失矩陣, 在目標函數中采用對奇異噪聲魯棒的F范數, 降低了異常值對算法的影響. 為快速求解模型, 本文基于凸優化理論, 通過引入一個動態權重參數, 將問題轉化為更易求解的無約束非光滑凸優化問題. 實驗結果表明, 本文方法較對比算法恢復性能得到較大提升, 不僅提高了缺失矩陣的重建精確性, 在秩的隨機選取方面也具有較穩定的恢復效果, 不僅彌補了ADMM算法對于截斷秩r選取魯棒性差的缺陷, 還解決了APGL算法對被奇異噪聲破壞的缺失矩陣無法穩定恢復的問題.