基于準范數與零范數的矩陣恢復

張令威，劉光宇，吳哲夫，劉光燦

(南京信息工程大學 江蘇省大數據分析技術重點實驗室，江蘇 南京 210044)

0 引 言

由于數據在采集、存儲、傳輸的過程中很容易受到噪聲的干擾，這為人們利用這些數據帶去了更大的挑戰。矩陣恢復的目的就是在矩陣的部分數據受到干擾的情況下恢復出原始的矩陣。

高維矩陣往往具有較高的相關性和冗余性[1]，因此矩陣一般具有低秩的結構，這種低秩性可以通過秩函數來衡量。而矩陣中存在的噪聲通常具有稀疏性。因此可以將高維數據分解為一個低秩矩陣與一個稀疏矩陣之和[2]。然而，矩陣的秩函數是非凸且不連續的[3]，秩最小化問題也是NP難的，這使得直接求解秩函數十分困難。為了求解秩最小化問題，目前普遍的做法是使用秩函數最優的凸近似-核范數[4]來代替秩函數，理論證明，當問題符合某些特定的條件時，核范數最小化與秩函數最小化的求解結果是等價的。核范數的應用使得秩最小化問題轉化成了凸問題，極大降低了求解的難度。

近年來矩陣恢復算法主獲得了快速的發展，常用的有下述一些方法。魯棒主成分分析(robust PCA，RPCA)[5]將矩陣分解為低秩矩陣與系數噪聲矩陣，低秩表示(low-rank representation，LRR)[6,7]在RPCA的基礎上做了延伸，認為數據集中的樣本可以表示為一個字典中的基的線性組合，組合的系數應該是低秩的，LRR更好地捕捉了數據的真實分布情況。非凸近似函數Schatten-p范數[8,9]使用準范數作為秩函數的代替，獲得了比核范數更精確的秩最小化結果。最近，基于Schatten-p范數的低秩矩陣分解[10]將待求解的矩陣分解為兩個子矩陣的乘積，加速了準范數的求解過程。

本文使用準范數的低秩矩陣分解形式代替經典的核范數約束，使用零范數約束矩陣中的稀疏噪聲部分，提出基于交替近似的線性最小化方法求解目標函數的優化問題。實驗結果表明，本文的方法可以獲得更加精確的低秩矩陣恢復結果，能夠有效地去除矩陣中的噪聲，同時也可以提高基于低秩表示的圖像分類方法的效果。

1 低秩矩陣恢復簡介

高維矩陣通常具有較高的相關性，而矩陣的秩相對于矩陣的行數或列數來說一般較小。低秩矩陣恢復就是將給定高維矩陣D(D∈m×n) 分解為一個低秩矩陣L(L∈m×n) 與一個稀疏噪聲矩陣S(S∈m×n)，優化問題如下所示

(1)

(2)

(3)

由于Schatten-p準范數的非凸性質，且求解問題是NP難的，因此基于直接求解準范數的方法通常無法進行大規模的應用。

圖1 Schatten-p范數曲線

2 基于準范數與零范數的矩陣恢復

2.1 目標函數的提出

(4)

2.2 基于交替近似的目標函數優化

由于矩陣Schatten-2/3準范數的非凸性質導致了求解的困難，Shang等[11]證明

(5)

其中，矩陣準范數被分解為兩個因子矩陣，分別求解因子矩陣的F范數與核范數即可得到準范數的優化結果。利用這種性質，本文的目標函數變為如下形式

(6)

(7)

其中，參數α用來平衡擾動的大小。

零范數的求解是NP難的，本文提出了交替近似最小化的方法求解含有零范數的目標函數，式(7)可以分解為3個子問題交替進行迭代優化。

2.2.1 變量Z的更新

首先固定變量A，S，更新Z

(8)

式(8)沒有閉式解，需要進行線性化得到具有閉式解的近似形式，研究證明

(9)

gl∶=AT(AXl-Bl)

(10)

由式(9)、式(10)兩式可將式(8)轉化為如下形式

(11)

對于形如式(11)的函數，首先引入收縮算子(shrinkage operator)[12]，定義為

(12)

根據奇異值閾值(singular value thresholding)[13]可得式(11)的閉式解為

(13)

2.2.2 變量A的更新

然后固定變量Z，S，更新A

(14)

上式對A求偏導可直接得到A的更新公式

Al+1=α(D-Sl)(Zl)T(I+αZl+1(Zl+1)T)-1

(15)

2.2.3 變量S的更新

最后固定變量A，Z，更新S

(16)

形如式(16)的函數可以使用硬閾值函數(Hard thresholding)[14]進行求解，首先引入硬閾值算子

(17)

則式(16)可用下式求解

(18)

求解本文目標函數的詳細過程如下：輸入原始矩陣D，參數λ,α；初始化A=I，使用RPCA方法的結果初始化Z和S，ρ=1.1； 根據式(13)、式(15)、式(18)更新變量Z,A,S直到滿足收斂條件；輸出兩個因子矩陣Z，A，噪聲矩陣S。 本文的收斂準則為|fk(A,Z,S)-fk+1(A,Z,S)|<10-6fk(A,Z,S)，其中fk(A,Z,S)為目標函數在第k步迭代時的函數值。

3 實驗結果與分析

本文提出的方法在人工生成數據集與真實數據集上與RPCA算法[5]、字典搜索[1](dictionary pursuit，DP)算法進行了矩陣恢復的對比實驗，還在LRR算法的基礎上探索了本文的方法對于人臉識別任務的影響。本文實驗環境為Intel酷睿i7-6700CPU，16G內存的戴爾臺式電腦，使用MATLAB R2017a平臺編程實現算法。

3.1 隨機生成矩陣

圖2 隨機生成矩陣的恢復結果對比

3.2 文本去除

本文將提出的方法進行了文本去除實驗的對比。真實圖像的維度為256×256，秩為10。圖3(a)展示了輸入圖像與原始圖像。本實驗中，文本部分可以看作矩陣恢復問題中的噪聲部分。本文算法與RPCA，Dictionary Pursuit[1]進行了對比。

圖3 文本去除結果對比

3.3 Essex人臉數據集

Essex人臉數據集由埃塞克斯大學所收集，被分為4個

表1 文本去除評價指標對比

目錄:face94，face95，face96，grimace，共計395個人的人臉，每人20張圖像，包含各種不同的種族血統的人。人群主要是一年級的本科學生，所以大多數圖像的年齡在18-20歲之間，但是也含有部分老年人的圖像。其中部分人臉圖像帶有眼鏡或者胡須，face96中還包含了極端的表情變化。

本文將原始數據圖像統一下采樣至40×40像素，將每張人臉圖像矢量化為1600維作為一個數據樣本。實驗中隨機選取10，30，50個類別，每類隨機選取6張圖像加入不同大小的白塊作為遮擋，以LRR算法為分類算法，通過搜索選取各算法的最優參數，以正確率為評價標準進行了對比實驗。圖4展示了所選數據集及加入遮擋后的部分圖片樣本。

圖4 Essex人臉數據集

表2～表4展示了本文方法與RPCA、LRR方法進行人臉識別任務的結果。表2表明，當待分類的人臉圖片較少時，本文方法能夠顯著提高分類結果的正確率。隨著待分類圖片逐漸增加，本文方法對分類結果的提升效果逐漸降低，但仍然獲得了最好的結果。

表2 10類人臉識別正確率

表3 30類人臉識別正確率

表4 50類人臉識別正確率

3.4 參數選擇

圖5 參數α對算法影響

4 結束語

使用矩陣Schatten-2/3準范數代替常規的核范數作為秩函數的近似，并將準范數的求解分解為求解其兩個因子矩陣的核范數與F范數，簡化了準范數的優化難度，使用零范數代替l1范數作為稀疏噪聲矩陣的約束，并提出了交替近似算法進行求解，最終獲得了比l1范數更加精確的矩陣恢復效果。在人工生成矩陣、文本去除任務、Essex人臉數據集識別任務上同流行的矩陣恢復算法進行對比實驗，驗證了本文方法可以更有效地恢復被噪聲干擾的矩陣，同時可以有效提高無監督人臉識別算法的準確性。