第37卷第4期 温 州 大 学 学 报（自 然 科 学 版） 2016年11月 Vol 37, No 4 Journal of Wenzhou University (Natural Sciences) Nov, 2016 基于RPCA模型的P范数优化算法 刘 园，王 迪 (温州大学数学与信息科学学院，浙江温州 325035) 摘 要：在图像修复和视频处理中，低秩矩阵恢复有着非常广泛的应用．RPCA模型是低秩矩阵恢复的经典模型，其基本思想是将一个数值矩阵分解为一个低秩矩阵与一个稀疏矩阵和的形式再进行求解．然而，RPCA问题是NP难的，一个通用的处理方式就是将RPCA模型中矩阵的秩函数和L0范数分别松弛为矩阵的核范数和L1范数，从而将其近似转化为凸优化问题来求解，但这种由凸优化近似方法得到的解在相对较弱的非相干性条件下会使原始问题的解退化．针对这个问题，本文首先提出一种更接近于原始问题的非凸近似模型，即用矩阵的Schatten-p范数和Lp范数（0p1）分别代替矩阵的秩函数和L0范数，然后针对提出的非凸近似模型，进一步给出有效的优化算法，最后，在人工数据集和真实图像数据集上进行实验，结果表明，所提出的模型是有效的． 关键词：低秩矩阵恢复；RPCA模型；Schatten-p范数；Lp范数 中图分类号：TP391 文献标志码：A 文章编号：1674-3563(2016)04-0025-08 DOI：10.3875/j.issn.1674-3563.2016.04.005 本文的PDF文件可以从xuebao.wzu.edu.cn获得 近些年来，随着互联网和信息科学的快速发展，人们可以获得大量的可视化数据，从这些可视化数据中，研究者们可以提取出与图像和视频处理等领域相关的有用信息．然而，在一些图像和视频的处理过程中，很多时候所给的图像与视频数据都伴随着光照强度变化、部分遮挡以及损坏等一系列噪音，能够从这些带有噪音污染的数据中准确恢复出原有的图像数据，是一个非常值得研究的问题．最近几年的研究表明，一些可视化数据可以表示为低秩部分与稀疏部分的和的形式，例如，对于一张带有光照阴影的人脸图片来说，低秩部分和稀疏部分分别捕获了人脸和光照阴影；在监控视频剪辑中，低秩部分和稀疏部分分别对应着背景和移动目标．最近几年，这些研究在图像和视频处理等领域中得到了高度的关注． 1 背景知识 假定一个观测数据矩阵DRmn，目标是恢复出它的低秩部分ARmn和稀疏部分E Rmn，使得DAE，也即下列鲁棒主成分分析（Robust Principle Component Analysis, RPCA）优化问题： minrank(A)||E||0，s..tDAE， （1） A,E其中rank(A)表示矩阵A的秩，||E||0表示矩阵E的L0范数，即矩阵E中非零元素的个数，是收稿日期：2015-09-18 作者简介：刘园(19- )，男，安徽六安人，硕士研究生，研究方向：应用分析与最优化理论 26 温州大学学报（自然科学版）(2016)第37卷第4期 一个正的权衡参数．由于（1）中的目标函数是非连续且非凸函数，且优化问题（1）是NP-难问题，因此不易求解．一个常用的方法就是将秩函数松弛为凸的核范数，将L0范数松弛为L1范数，从而将问题（1）松弛为以下凸优化问题： min||A||||E||1，s..tDAE， （2） A,E即主成分追踪（Principle Component Pursuit，PCP）问题[1]，其中||A||表示矩阵A的核范数，即矩阵A的奇异值之和，||E||1表示矩阵E的L1范数，即矩阵E所有元素的绝对值之和．文献[2]证明了在满足较强的非相干性条件下，通过求解凸优化问题（2）能获得非凸优化问题（1）的最优解．进一步，文献[3]给出了求解问题（2）的交替方向算法（Alternating Direction Method，ADM）．然而，当这些假设条件不满足时，凸优化问题（2）的解就会偏离原始问题（1）的最优解．相比较而言，Lp范数（0p1）比L1范数更接近于L0范数，并且已有的相关文献[4]也通过理论分析和大量实验证明了p范数在相对较弱的非干性条件下就能保证得到原始问题（1）的最优解．更重要的是，它们指出虽然通过求解Lp范数非凸优化问题得到的解是局部最优解，但此局部最优解要比L1范数凸优化问题的全局最优解的效果更好，即运用Lp范数可成功恢复出具有更低信噪比的信号来[5]．因此，在这篇文章中我们运用非凸的替代函数，即将L0范数松弛为Lp范数，将秩函数松弛为Schatten-p范数，提出了一个新的矩阵恢复模型．大量实验表明本文算法要好于PCP优化算法．本文的贡献可总结为以下几点： 1）为低秩矩阵恢复问题提出了一个Schatten-p范数与Lp范数联合正则化的主成分追踪模型，此模型为非凸模型，它比凸的PCP模型更接近于原RPCA模型； 2）针对新的非凸模型，基于ADM方法，提出了一个快速求解的算法； 3）大量的人工数据和真实可视化数据上的实验验证了本文算法的有效性． 2 Lp优化算法 容易看出，Lp范数（0p1）比L1范数更接近于L0范数，特别地，当p0时，Lp范数就退化成了L0范数．同理，Schatten-p范数比核范数更接近于秩函数．因此，我们考虑以下基于Schatten-p范数与Lp范数联合正则化的主成分追踪模型： pmin||A||ps..tDAE， （3） p||E||p,p，A,E其中DRmnm（不妨假设）是一个观测数据矩阵，||A||p表示矩阵A的Schatten-p范数，即||A||p(i1ip(A))1/p，i(A)为矩阵A的第i个奇异值，||E||p,p表示矩阵E的Lp范数，即有很多非凸惩罚函数可以用到非凸主成分追踪模型中，这里用Lp||E||p,p(i1j1|eij|p)1/p．范数和Schattenp范数是因为它们与L1范数和Schatten-p范数具有类似的性质． 下面运用ADM算法解决上述非凸优化问题（3）．首先引入拉格朗日乘子矩阵Y，并给出问题（3）的拉格朗日函数： pL(A,E,Y)||A||p||E||pp,pY,DAEmn||DAE||2 （4） F，2 刘园等：基于RPCA模型的P范数优化算法 其中0表示给定的参数，||A||F表示矩阵A的Frobenius范数，即||A||F为了优化上述拉格朗日函数，下面给出基于交替方向的迭代求解算法： 27 A,A． A(k1)argminL(A,E(k),Y(k)) （5） A(k1) （6） argminL(A(k1),E,Y(k))．EE(k1)(k)(k1)(k1)YYDAE具体地，对于子优化问题（5），根据文献[6]有： A(k1)argminL(A,E(k),Y(k),) A(k)argmin||A||p,DAE(k)pY||DAE(k)||2F 21p(diag())VT， argmin||G(k)A||2||A||UTFp2Y(k)1~~(k)(k)其中，GDE，U和V分别是G(k)的左奇异特征向量矩阵和右奇异特征向量矩阵，diag(1,2,,r,0,,0)为G(k)的奇异值矩阵，其中i(i1,2,,r)为GTG的特征值，G(k)~~UVT，T为软阈值算子，即 if|z|haif|z|ha， if|z|hap10T(z){0,sgn(z)a}sgn(z)其中a[2(1p)]12p，haapa，*(a,|z|)是以下非线性方程 qq1z0 的较大的根，可以通过迭代算子(k1)((k))，()zq类似，对于子优化问题（6）有： q1求解． E(k1)argminL(A(k1),E,Y(k),) E2||DA(k1)E||FE2 211p(k)argmin(||Z(k)E||2||E||)argmin(ze)|eij|p Fp,pijijEE22i,ji,j(k)(k1)argmin||E||pY,DAEp,p1(k)(k)argmin[(zijeij)2|eij|p]Tzij， E2i,jY(k)(k)(k1)其中，ZDA． 本文方法的具体步骤如算法1所述．在算法1中，首先被初始化为一个较小的数0，然 28 温州大学学报（自然科学版）(2016)第37卷第4期 后每一次迭代都几何式增大，直到它达到一个事先设定的较大阈值．这种连续性处理技术能够很大程度上加快算法的收敛速度[7]． 算法1：求解问题（3）的基于交替方向法的迭代算法 输入：观测数据矩阵DRmn，正则参数． 初始化：A0；E0；00；1；k0． 当不收敛时作以下迭代步骤： 1）固定其它变量为最新值，由（5）式更新变量A． 2）固定其它变量为最新值，由（6）式更新变量E． 3）固定其它变量为最新值，更新拉格朗日乘子Y输出：(Ak,Ek)． (k)；令k1k． 3 实验结果 实验分三个部分对本文模型与PCP模型进行对比．首先，由于人工数据能够提供真实无噪音的数据（Ground truth），因此可以对矩阵恢复模型的精度在量上进行对比；其次，给出它们在单张图片恢复上的对比；最后在人脸识别数据集YaleB上恢复带有椒盐噪声的人脸图像，并用恢复后的数据进行分类，比较分类效果． 3.1 人工数据 首先生成一个秩为r的mn数据矩阵作为Ground truth，记为A0，然后生成一个稀疏矩阵，记为E0，其中E0中的非零元素的位置是随机的，非零元素均匀分布在区间[-500,500]，最后令ˆ和Eˆ分别为算法计算出来的数据恢复矩阵和稀疏噪音矩阵．DA0E0，并记A在以下实验中，ˆA||/||A||作为算法精度的度量标准．取m100，n100，r10，取相对误差Err||A为0202了消除生成数据的随机性因素对算法误差的影响，对每一组参数都做20次实验，取误差的均值来度量模型的精度． 首先，通过实验来观察参数p的变化对实验效果的影响情况．固定噪音数据所占的比例为ratio0.3，即稀疏噪音矩阵非零元素的个数为ratiomn，取参数p(0.1p0.9)．实验结果如图1所示，红色线表示本文所提出的模型在不同参数p下的相对误差，蓝色线表示PCP模型的相对误差（由于PCP模型中没有参数p，因此它的相对误差不变）．从图1可以看出，p值在（0,1）范围内变化时，PCP模型的相对误差在0.15左右，而本文所给出模型的相对误差在0.005之下．更重要的是，本文模型的相对误差基本不受参数p的变化影响．鉴于所提出的模型对于参数p的鲁棒性，在以下的实验中固定p0.5． 进一步，通过实验给出两种方法在噪音数据比例ratio(0.05ratio0.5)下的相对误差．结果如图2所示，两模型的相对误差都随着噪音比例的增大而逐渐增大．噪音比例在0.05 – 0.2之间时，两种方法的相对误差差别不大，但当噪音比例在0.3 – 0.5之间时，PCP模型的相对误差急剧增加，而本文模型随着噪音比例的增加，其相对误差却一直趋于平稳状态，并且误差一直保持在0.001以下． 表1给出了两种模型相对误差的数值结果，从表中可以明显看出，在整个噪音比例范围内，本文Lp模型的相对误差都远远小于PCP模型的相对误差． 刘园等：基于RPCA模型的P范数优化算法 29 图1 不同p值下本文算法与PCP 相对误差的比较 图2 不同噪音比例中本文算法与PCP 相对误差的比较 表1 PCP模型与本文模型的相对误差比较 噪音比例 0.05 0.10 0.15 0.20 0.25 相对误差 PCP模型 0.000 3 0.001 2 0.006 6 0.022 0 0.063 0 本文模型 / 10-5 1.32 1.92 2.78 4.16 5.01 噪音比例 0.30 0.35 0.40 0.45 0.50 相对误差 PCP模型 0.180 0 0.422 0 0.729 0 1.204 7 2.2 1 本文模型 / 10-5 5.68 8.87 9.72 13.70 16.09 3.2 单张图片数据 下面将给出两种模型在单张图片恢复上的效果比较．首先选取无明显噪声污染的图片作为原始观测图像，然后在这些图像上加入噪音比例ratio =0.3的“椒盐噪声”作为待恢复的图片，最后通过不同的模型将噪音滤除掉，恢复原有的图像．在这里，选取不同风格的四幅图像作为原始观测图像，其中包括灰度图片和RGB彩色图片，如图3（a）所示．对RGB彩色图片，我们用模型分别恢复出R通道、G通道、B通道的图像，然后再将它们合并起来，即为恢复出的彩色图片． 从图3可以看出，通过PCP模型恢复出来的图像中还含有很多噪音点，看起来比较模糊，与原始数据有一定的差距，而用本文模型恢复的图像更接近于原始观测图像，看起来较为清晰．因此，本文所提出的模型在单张图片恢复方面要优于PCP模型． 3.3 人脸识别 在YaleB数据集[8]上进行实验．数据集包含38个人的2 414幅人脸照片，其中每个人又包含了60多幅不同光照、不同表情下的照片，每张照片是32 × 32像素的灰度图像．实验设计如下： 1）对于每个人，随机选取30张人脸照片作为训练集样本，剩余的作为测试样本； 2）在每幅测试样本图片上加入噪音比例为ratio(0.05ratio0.5)的椒盐噪声，并将其排列为1 024维的列向量； 3）将训练样本和加噪声后的测试样本按列排成一个数据矩阵，记为D； 4）用PCP模型和本文模型分别对D进行矩阵恢复； 5）用K近邻（KNN）方法对恢复后的测试样本进行分类． 30 温州大学学报（自然科学版）(2016)第37卷第4期 (a) 原始观测 图像 (b) 加了椒盐噪音后的图像 (c) 用本文模型恢复出来的图像 (d) 用PCP模型恢复出来的图像 图3 单张图片数据集上的实验结果 图4给出了5个人的部分人脸图像，每一行是一个人脸不同表情的图像，（a）列为原始人脸数据图像，伴随有严重的光照阴影，（b）列为增加噪音比例ratio = 0.3的“椒盐噪音”后的人脸图像，（c）列是用本文模型恢复出来的人脸图像，（d）列是用PCP模型恢复出来的人脸图像． (a) 原始数据 图像 (b) 加了椒盐噪音后的图像 (c) 用本文模型恢复出来的图像 (d) 用PCP模型恢复出来的图像 图4 人脸数据集上的实验结果 刘园等：基于RPCA模型的P范数优化算法 31 从图4中可以看出，PCP模型仅仅能够去除部分光照阴影，本文的模型能够去除几乎所有的光照阴影，更为重要的是，PCP模型恢复出来的图像仍然伴随着许多的噪音点，使得恢复的图像显得模糊不清，而本文模型能够较好地去除原始图像中的椒盐噪音，效果更接近于真实人脸图像． 图5给出了PCP模型与本文模型在人脸识别正确率方面的实验结果．可以看到，随着噪音比例的增加，直接用“椒盐噪声”遮挡的图像进行分类所得到的正确率急剧下降，用通过PCP模型处理后的图像进行分类所得的正确率从0.55逐渐下滑到0.42左右，而用本文模型处理后的图像进行分类的识别正确率从0.6平缓下滑到0.55左右，远远高于实用PCP模型的正确率．表2给出了20次实验的识别正确率的均值以及方差，可以看出，在噪音比例范围内，采用本文模型得出的图像识别正确率远远高于采用PCP模型的． 图5 PCP模型与本文模型对人脸 识别的正确率对比 表2 PCP模型与本文模型对于人脸识别的正确率均值及方差比较 噪音比例 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 噪音图像 识别正确率 0.532 5 0.457 0 0.358 9 0.296 4 0.233 8 0.175 4 0.135 5 0.100 2 方 差 0.005 7 0.012 1 0.011 6 0.013 7 0.005 9 0.009 7 0.005 4 0.005 9 RPCA算法 识别正确率 0.542 9 0.532 7 0.523 4 0.504 4 0.493 4 0.478 0 0.459 7 0.423 9 方 差 0.002 7 0.001 5 0.002 0 0.002 7 0.004 4 0.002 4 0.005 0 0.004 8 本文算法 识别正确率 0.600 0 0.595 8 0.592 3 0.588 7 0.579 9 0.569 7 0.557 3 0.544 7 方 差 0.003 3 0.002 0 0.003 1 0.002 5 0.003 1 0.003 3 0.005 0 0.004 2 4 结 论 本文通过对RPCA问题的研究，将其中的秩范数与L0范数替换成非凸的Schatten-p范数和Lp范数（0p1），为低秩矩阵恢复提出一种更接近于RPCA问题的非凸近似模型，并针对此模型，给出了一种有效的求解算法．在人工数据集和真实数据集上的实验结果验证了本文所给模型的有效性． 参考文献 [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): 4-509. [3] Lin Z, Chen M, Ma Y. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices 32 [J]. arXiv preprint arXiv, 2010, 23(5): 109-115. 温州大学学报（自然科学版）(2016)第37卷第4期 [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 l1 minimization [J]. Journal of Fourier Analysis and Applications, 2008, 14(5-6): 877-905. [6] Marjanovic G, Solo V. On lq optimization 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-0. [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): 3-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) Abstract: 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 (0p1) 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. Key words: Low-rank Matrix Recovery; RPCA Model; Schatten-p-norm; Lp-norm (编辑：王一芳)
