劉 園，王 迪

(溫州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，浙江溫州 325035)

基于RPCA模型的P范數(shù)優(yōu)化算法

劉 園，王 迪

(溫州大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，浙江溫州 325035)

在圖像修復(fù)和視頻處理中，低秩矩陣恢復(fù)有著非常廣泛的應(yīng)用．RPCA模型是低秩矩陣恢復(fù)的經(jīng)典模型，其基本思想是將一個(gè)數(shù)值矩陣分解為一個(gè)低秩矩陣與一個(gè)稀疏矩陣和的形式再進(jìn)行求解．然而，RPCA問題是NP難的，一個(gè)通用的處理方式就是將RPCA模型中矩陣的秩函數(shù)和L0范數(shù)分別松弛為矩陣的核范數(shù)和L1范數(shù)，從而將其近似轉(zhuǎn)化為凸優(yōu)化問題來求解，但這種由凸優(yōu)化近似方法得到的解在相對(duì)較弱的非相干性條件下會(huì)使原始問題的解退化．針對(duì)這個(gè)問題，本文首先提出一種更接近于原始問題的非凸近似模型，即用矩陣的Schatten-p范數(shù)和Lp范數(shù)（0＜p＜1）分別代替矩陣的秩函數(shù)和L0范數(shù)，然后針對(duì)提出的非凸近似模型，進(jìn)一步給出有效的優(yōu)化算法，最后，在人工數(shù)據(jù)集和真實(shí)圖像數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明，所提出的模型是有效的．

低秩矩陣恢復(fù)；RPCA模型；Schatten-p范數(shù)；Lp范數(shù)

近些年來，隨著互聯(lián)網(wǎng)和信息科學(xué)的快速發(fā)展，人們可以獲得大量的可視化數(shù)據(jù)，從這些可視化數(shù)據(jù)中，研究者們可以提取出與圖像和視頻處理等領(lǐng)域相關(guān)的有用信息．然而，在一些圖像和視頻的處理過程中，很多時(shí)候所給的圖像與視頻數(shù)據(jù)都伴隨著光照強(qiáng)度變化、部分遮擋以及損壞等一系列噪音，能夠從這些帶有噪音污染的數(shù)據(jù)中準(zhǔn)確恢復(fù)出原有的圖像數(shù)據(jù)，是一個(gè)非常值得研究的問題．最近幾年的研究表明，一些可視化數(shù)據(jù)可以表示為低秩部分與稀疏部分的和的形式，例如，對(duì)于一張帶有光照陰影的人臉圖片來說，低秩部分和稀疏部分分別捕獲了人臉和光照陰影；在監(jiān)控視頻剪輯中，低秩部分和稀疏部分分別對(duì)應(yīng)著背景和移動(dòng)目標(biāo)．最近幾年，這些研究在圖像和視頻處理等領(lǐng)域中得到了高度的關(guān)注．

1 背景知識(shí)

其中rank(A)表示矩陣A的秩，||E||0表示矩陣E的L0范數(shù)，即矩陣E中非零元素的個(gè)數(shù)，λ是一個(gè)正的權(quán)衡參數(shù)．由于（1）中的目標(biāo)函數(shù)是非連續(xù)且非凸函數(shù)，且優(yōu)化問題（1）是NP-難問題，因此不易求解．一個(gè)常用的方法就是將秩函數(shù)松弛為凸的核范數(shù)，將L0范數(shù)松弛為L(zhǎng)1范數(shù)，從而將問題（1）松弛為以下凸優(yōu)化問題：

即主成分追蹤（Principle Component Pursuit，PCP）問題[1]，其中||A||*表示矩陣A的核范數(shù)，即矩陣A的奇異值之和，||E||1表示矩陣E的L1范數(shù)，即矩陣E所有元素的絕對(duì)值之和．文獻(xiàn)[2]證明了在滿足較強(qiáng)的非相干性條件下，通過求解凸優(yōu)化問題（2）能獲得非凸優(yōu)化問題（1）的最優(yōu)解．進(jìn)一步，文獻(xiàn)[3]給出了求解問題（2）的交替方向算法（Alternating Direction Method，ADM）．然而，當(dāng)這些假設(shè)條件不滿足時(shí)，凸優(yōu)化問題（2）的解就會(huì)偏離原始問題（1）的最優(yōu)解．相比較而言，Lp范數(shù)（0＜p＜1）比L1范數(shù)更接近于L0范數(shù)，并且已有的相關(guān)文獻(xiàn)[4]也通過理論分析和大量實(shí)驗(yàn)證明了p范數(shù)在相對(duì)較弱的非干性條件下就能保證得到原始問題（1）的最優(yōu)解．更重要的是，它們指出雖然通過求解Lp范數(shù)非凸優(yōu)化問題得到的解是局部最優(yōu)解，但此局部最優(yōu)解要比L1范數(shù)凸優(yōu)化問題的全局最優(yōu)解的效果更好，即運(yùn)用Lp范數(shù)可成功恢復(fù)出具有更低信噪比的信號(hào)來[5]．因此，在這篇文章中我們運(yùn)用非凸的替代函數(shù)，即將L0范數(shù)松弛為L(zhǎng)p范數(shù)，將秩函數(shù)松弛為Schatten-p范數(shù)，提出了一個(gè)新的矩陣恢復(fù)模型．大量實(shí)驗(yàn)表明本文算法要好于PCP優(yōu)化算法．本文的貢獻(xiàn)可總結(jié)為以下幾點(diǎn)：

1）為低秩矩陣恢復(fù)問題提出了一個(gè)Schatten-p范數(shù)與Lp范數(shù)聯(lián)合正則化的主成分追蹤模型，此模型為非凸模型，它比凸的PCP模型更接近于原RPCA模型；

2）針對(duì)新的非凸模型，基于ADM方法，提出了一個(gè)快速求解的算法；

3）大量的人工數(shù)據(jù)和真實(shí)可視化數(shù)據(jù)上的實(shí)驗(yàn)驗(yàn)證了本文算法的有效性．

2 Lp優(yōu)化算法

容易看出，Lp范數(shù)（0＜p＜1）比L1范數(shù)更接近于L0范數(shù)，特別地，當(dāng)p→0時(shí)，Lp范數(shù)就退化成了L0范數(shù)．同理，Schatten-p范數(shù)比核范數(shù)更接近于秩函數(shù)．因此，我們考慮以下基于Schatten-p范數(shù)與Lp范數(shù)聯(lián)合正則化的主成分追蹤模型：

其中D?Rm×n（不妨假設(shè)）是一個(gè)觀測(cè)數(shù)據(jù)矩陣，||A||p表示矩陣A的Schatten-p范數(shù)，即為矩陣A的第i個(gè)奇異值，||E||p,p表示矩陣E的Lp范數(shù)，即有很多非凸懲罰函數(shù)可以用到非凸主成分追蹤模型中，這里用Lp范數(shù)和Schatten-p 范數(shù)是因?yàn)樗鼈兣cL1范數(shù)和Schatten-p范數(shù)具有類似的性質(zhì)．

下面運(yùn)用ADM算法解決上述非凸優(yōu)化問題（3）．首先引入拉格朗日乘子矩陣Y，并給出問題（3）的拉格朗日函數(shù)：

其中μ＞0表示給定的參數(shù)，||A||F表示矩陣A的Frobenius范數(shù)，即

為了優(yōu)化上述拉格朗日函數(shù)，下面給出基于交替方向的迭代求解算法：

具體地，對(duì)于子優(yōu)化問題（5），根據(jù)文獻(xiàn)[6]有：

類似，對(duì)于子優(yōu)化問題（6）有：

本文方法的具體步驟如算法1所述．在算法1中，μ首先被初始化為一個(gè)較小的數(shù)μ0，然后每一次迭代都幾何式增大，直到它達(dá)到一個(gè)事先設(shè)定的較大閾值這種連續(xù)性處理技術(shù)能夠很大程度上加快算法的收斂速度[7]．

算法1：求解問題（3）的基于交替方向法的迭代算法

當(dāng)不收斂時(shí)作以下迭代步驟：

1）固定其它變量為最新值，由（5）式更新變量A．

2）固定其它變量為最新值，由（6）式更新變量E．

3）固定其它變量為最新值，更新拉格朗日乘子Y(k)；令

輸出：(Ak,Ek)．

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)分三個(gè)部分對(duì)本文模型與PCP模型進(jìn)行對(duì)比．首先，由于人工數(shù)據(jù)能夠提供真實(shí)無噪音的數(shù)據(jù)（Ground truth），因此可以對(duì)矩陣恢復(fù)模型的精度在量上進(jìn)行對(duì)比；其次，給出它們?cè)趩螐垐D片恢復(fù)上的對(duì)比；最后在人臉識(shí)別數(shù)據(jù)集YaleB上恢復(fù)帶有椒鹽噪聲的人臉圖像，并用恢復(fù)后的數(shù)據(jù)進(jìn)行分類，比較分類效果．

3.1 人工數(shù)據(jù)

首先生成一個(gè)秩為r的m×n數(shù)據(jù)矩陣作為Ground truth，記為A0，然后生成一個(gè)稀疏矩陣，記為E0，其中E0中的非零元素的位置是隨機(jī)的，非零元素均勻分布在區(qū)間[-500,500]，最后令并記和分別為算法計(jì)算出來的數(shù)據(jù)恢復(fù)矩陣和稀疏噪音矩陣．在以下實(shí)驗(yàn)中，取m=100，n=100，r=10，取相對(duì)誤差作為算法精度的度量標(biāo)準(zhǔn)．為了消除生成數(shù)據(jù)的隨機(jī)性因素對(duì)算法誤差的影響，對(duì)每一組參數(shù)都做20次實(shí)驗(yàn)，取誤差的均值來度量模型的精度．

首先，通過實(shí)驗(yàn)來觀察參數(shù)p的變化對(duì)實(shí)驗(yàn)效果的影響情況．固定噪音數(shù)據(jù)所占的比例為ratio=0.3，即稀疏噪音矩陣非零元素的個(gè)數(shù)為ratio×m×n，取參數(shù)p(0.1≤p≤0.9)．實(shí)驗(yàn)結(jié)果如圖1所示，紅色線表示本文所提出的模型在不同參數(shù)p下的相對(duì)誤差，藍(lán)色線表示PCP模型的相對(duì)誤差（由于PCP模型中沒有參數(shù)p，因此它的相對(duì)誤差不變）．從圖1可以看出，p值在（0,1）范圍內(nèi)變化時(shí)，PCP模型的相對(duì)誤差在0.15左右，而本文所給出模型的相對(duì)誤差在0.005之下．更重要的是，本文模型的相對(duì)誤差基本不受參數(shù)p的變化影響．鑒于所提出的模型對(duì)于參數(shù)p的魯棒性，在以下的實(shí)驗(yàn)中固定p=0.5．

進(jìn)一步，通過實(shí)驗(yàn)給出兩種方法在噪音數(shù)據(jù)比例ratio(0.05≤ratio≤0.5)下的相對(duì)誤差．結(jié)果如圖2所示，兩模型的相對(duì)誤差都隨著噪音比例的增大而逐漸增大．噪音比例在0.05–0.2之間時(shí)，兩種方法的相對(duì)誤差差別不大，但當(dāng)噪音比例在0.3–0.5之間時(shí)，PCP模型的相對(duì)誤差急劇增加，而本文模型隨著噪音比例的增加，其相對(duì)誤差卻一直趨于平穩(wěn)狀態(tài)，并且誤差一直保持在0.001以下．

表1給出了兩種模型相對(duì)誤差的數(shù)值結(jié)果，從表中可以明顯看出，在整個(gè)噪音比例范圍內(nèi)，本文Lp模型的相對(duì)誤差都遠(yuǎn)遠(yuǎn)小于PCP模型的相對(duì)誤差．

圖1 不同p值下本文算法與PCP相對(duì)誤差的比較

圖2 不同噪音比例中本文算法與PCP相對(duì)誤差的比較

表1 PCP模型與本文模型的相對(duì)誤差比較

3.2 單張圖片數(shù)據(jù)

下面將給出兩種模型在單張圖片恢復(fù)上的效果比較．首先選取無明顯噪聲污染的圖片作為原始觀測(cè)圖像，然后在這些圖像上加入噪音比例ratio=0.3的“椒鹽噪聲”作為待恢復(fù)的圖片，最后通過不同的模型將噪音濾除掉，恢復(fù)原有的圖像．在這里，選取不同風(fēng)格的四幅圖像作為原始觀測(cè)圖像，其中包括灰度圖片和RGB彩色圖片，如圖3（a）所示．對(duì)RGB彩色圖片，我們用模型分別恢復(fù)出R通道、G通道、B通道的圖像，然后再將它們合并起來，即為恢復(fù)出的彩色圖片．

從圖3可以看出，通過PCP模型恢復(fù)出來的圖像中還含有很多噪音點(diǎn)，看起來比較模糊，與原始數(shù)據(jù)有一定的差距，而用本文模型恢復(fù)的圖像更接近于原始觀測(cè)圖像，看起來較為清晰．因此，本文所提出的模型在單張圖片恢復(fù)方面要優(yōu)于PCP模型．

3.3 人臉識(shí)別

在YaleB數(shù)據(jù)集[8]上進(jìn)行實(shí)驗(yàn)．?dāng)?shù)據(jù)集包含38個(gè)人的2 414幅人臉照片，其中每個(gè)人又包含了60多幅不同光照、不同表情下的照片，每張照片是32×32像素的灰度圖像．實(shí)驗(yàn)設(shè)計(jì)如下：

1）對(duì)于每個(gè)人，隨機(jī)選取30張人臉照片作為訓(xùn)練集樣本，剩余的作為測(cè)試樣本；

2）在每幅測(cè)試樣本圖片上加入噪音比例為ratio(0.05≤ratio≤0.5)的椒鹽噪聲，并將其排列為1 024維的列向量；

3）將訓(xùn)練樣本和加噪聲后的測(cè)試樣本按列排成一個(gè)數(shù)據(jù)矩陣，記為D；

4）用PCP模型和本文模型分別對(duì)D進(jìn)行矩陣恢復(fù)；

5）用K近鄰（KNN）方法對(duì)恢復(fù)后的測(cè)試樣本進(jìn)行分類．

圖3 單張圖片數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

圖4給出了5個(gè)人的部分人臉圖像，每一行是一個(gè)人臉不同表情的圖像，（a）列為原始人臉數(shù)據(jù)圖像，伴隨有嚴(yán)重的光照陰影，（b）列為增加噪音比例ratio=0.3的“椒鹽噪音”后的人臉圖像，（c）列是用本文模型恢復(fù)出來的人臉圖像，（d）列是用PCP模型恢復(fù)出來的人臉圖像．

圖4 人臉數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

從圖4中可以看出，PCP模型僅僅能夠去除部分光照陰影，本文的模型能夠去除幾乎所有的光照陰影，更為重要的是，PCP模型恢復(fù)出來的圖像仍然伴隨著許多的噪音點(diǎn)，使得恢復(fù)的圖像顯得模糊不清，而本文模型能夠較好地去除原始圖像中的椒鹽噪音，效果更接近于真實(shí)人臉圖像．

圖5給出了PCP模型與本文模型在人臉識(shí)別正確率方面的實(shí)驗(yàn)結(jié)果．可以看到，隨著噪音比例的增加，直接用“椒鹽噪聲”遮擋的圖像進(jìn)行分類所得到的正確率急劇下降，用通過PCP模型處理后的圖像進(jìn)行分類所得的正確率從0.55逐漸下滑到0.42左右，而用本文模型處理后的圖像進(jìn)行分類的識(shí)別正確率從0.6平緩下滑到0.55左右，遠(yuǎn)遠(yuǎn)高于實(shí)用PCP模型的正確率．表2給出了20次實(shí)驗(yàn)的識(shí)別正確率的均值以及方差，可以看出，在噪音比例范圍內(nèi)，采用本文模型得出的圖像識(shí)別正確率遠(yuǎn)遠(yuǎn)高于采用PCP模型的．

圖5 PCP模型與本文模型對(duì)人臉識(shí)別的正確率對(duì)比

表2 PCP模型與本文模型對(duì)于人臉識(shí)別的正確率均值及方差比較

4 結(jié) 論

本文通過對(duì)RPCA問題的研究，將其中的秩范數(shù)與L0范數(shù)替換成非凸的Schatten-p范數(shù)和Lp范數(shù)（0＜p＜1），為低秩矩陣恢復(fù)提出一種更接近于RPCA問題的非凸近似模型，并針對(duì)此模型，給出了一種有效的求解算法．在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所給模型的有效性．

[1] Ganesh A, Ma Y, Rao S, et al. Robust principal component analysis: exact recovery of corrupted low-rank matrices via convex optimization [J]. Advances in Neural Information Processing Systems, 2009, 87(4): 2080-2088.

[2] Candes E J, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information [J]. Ranaon on Nformaon Hory, 2006, 52(2): 489-509.

[3] Lin Z, Chen M, Ma Y. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[J]. arXiv preprint arXiv, 2010, 23(5): 109-115.

[4] Chen X, Xu F, Ye Y. Lower bound theory of nonzero entries in solutions of l2-lp minimization [J]. Siam Journal on Scientific Computing, 2010, 32(5): 2832-2852.

[5] Candès E J, Wakin M B, Boyd S P. Enhancing sparsity by reweighted l1minimization [J]. Journal of Fourier Analysis and Applications, 2008, 14(5-6): 877-905.

[6] Marjanovic G, Solo V. On lqoptimization and matrix completion [J]. IEEE Transactions on Signal Processing, 2012, 60(11): 5714-5724.

[7] Toh K C, Yun S. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems [J]. Pacific J Optimization, 2010, 6(3): 615-640.

[8] Georghiades A S, Belhumeur P N, Kriegman D J. From few to many: illumination cone models for face recognition under variable lighting and pose [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(6): 643-660.

The Study of P-norm Optimization Algorithm Based on RPCA Model

LIU Yuan, WANG Di
(College of Mathematics and Information Science, Wenzhou University, Wenzhou, China 325035)

The model of low-rank matrix recovery has been widely used in image in painting and video processing field. RPCA model is a classical model of low rank matrix recovery. Its basic idea is to decompose a numerical matrix into the form of a low-rank matrix and a sparse matrix sum before it is solved. However, RPCA problem is NP-hard. A commonly-used processing mode is to loose the matrix rank function and the L0norm from the RPCA model respectively into the matrix nuclear norm and the L1norm. Thus, the problem is solved through the way to transform its approximation into the convex optimization problem. However, the solution of the convex optimization approximation approach degrades the solution of original problem under the relatively weak incoherent condition. This paper firstly proposes a non-convex approximation model toward the problem, namely, applying the matrix Schatten-p norm andLpnorm (0＜p＜1)to replace the matrix rank function and L0norm. And then the further effective optimization algorithm is given based on the non-convex approximation model. Lastly, the experiment based on the synthetic datasets and the real image datasets is made. It turns out that the model proposed is valid and effective.

Low-rank Matrix Recovery; RPCA Model; Schatten-p-norm; Lp-norm

TP391

A

1674-3563(2016)04-0025-08

10.3875/j.issn.1674-3563.2016.04.005 本文的PDF文件可以從xuebao.wzu.edu.cn獲得

(編輯：王一芳)

2015-09-18

劉園(1989- )，男，安徽六安人，碩士研究生，研究方向：應(yīng)用分析與最優(yōu)化理論