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

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

0 引 言

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

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

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

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

1 低秩矩陣恢復簡介

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

(1)

(2)

(3)

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

圖1 Schatten-p范數(shù)曲線

2 基于準范數(shù)與零范數(shù)的矩陣恢復

2.1 目標函數(shù)的提出

(4)

2.2 基于交替近似的目標函數(shù)優(yōu)化

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

(5)

其中，矩陣準范數(shù)被分解為兩個因子矩陣，分別求解因子矩陣的F范數(shù)與核范數(shù)即可得到準范數(shù)的優(yōu)化結(jié)果。利用這種性質(zhì)，本文的目標函數(shù)變?yōu)槿缦滦问?/p>

(6)

(7)

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

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

2.2.1 變量Z的更新

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

(8)

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

(9)

gl∶=AT(AXl-Bl)

(10)

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

(11)

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

(12)

根據(jù)奇異值閾值(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)的函數(shù)可以使用硬閾值函數(shù)(Hard thresholding)[14]進行求解，首先引入硬閾值算子

(17)

則式(16)可用下式求解

(18)

求解本文目標函數(shù)的詳細過程如下：輸入原始矩陣D，參數(shù)λ,α；初始化A=I，使用RPCA方法的結(jié)果初始化Z和S，ρ=1.1； 根據(jù)式(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)為目標函數(shù)在第k步迭代時的函數(shù)值。

3 實驗結(jié)果與分析

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

3.1 隨機生成矩陣

圖2 隨機生成矩陣的恢復結(jié)果對比

3.2 文本去除

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

圖3 文本去除結(jié)果對比

3.3 Essex人臉數(shù)據(jù)集

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

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

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

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

圖4 Essex人臉數(shù)據(jù)集

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

表2 10類人臉識別正確率

表3 30類人臉識別正確率

表4 50類人臉識別正確率

3.4 參數(shù)選擇

圖5 參數(shù)α對算法影響

4 結(jié)束語

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