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

劉 園，王 迪

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

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

劉 園，王 迪

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

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

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

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

1 背景知識

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

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

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

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

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

2 Lp優(yōu)化算法

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

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

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

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

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

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

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

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

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

當不收斂時作以下迭代步驟：

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

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

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

輸出：(Ak,Ek)．

3 實驗結(jié)果

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

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

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

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

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

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

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

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

表1 PCP模型與本文模型的相對誤差比較

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

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

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

3.3 人臉識別

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

1）對于每個人，隨機選取30張人臉照片作為訓練集樣本，剩余的作為測試樣本；

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

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

4）用PCP模型和本文模型分別對D進行矩陣恢復；

5）用K近鄰（KNN）方法對恢復后的測試樣本進行分類．

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

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

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

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

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

圖5 PCP模型與本文模型對人臉識別的正確率對比

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

4 結(jié) 論

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

[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ōu)化理論