不完全鲁棒主成分分析的正则化方法及其在背景建模中的应用
作者：史加荣　郑秀云　杨威
来源：《计算机应用》2015年第10期
        摘要：针对现有的鲁棒主成分分析（RPCA）方法忽略序列数据的连续性及不完整性的情况，提出了一种低秩矩阵恢复模型——正则化不完全鲁棒主成分分析（RIRPCA）。首先基于序列数据连续性的度量函数建立了RIRPCA模型，即最小化矩阵核范数、L1范数和正则项的加权组合；然后使用增广拉格朗日乘子法来求解所提出的凸优化模型， 此算法具有良好的可扩展性和较低的计算复杂度；最后，将RIRPCA应用到视频背景建模中。实验结果表明，RIRPCA比矩阵补全和不完全RPCA等方法在恢复丢失元素和分离前景上具有优越性。
        关键词：鲁棒主成分分析； 低秩矩阵恢复； 背景建模； 核范数最小化； 增广拉格朗日乘子法
        中图分类号： TP391.41
        文献标志码：A
        Abstract： Because the existing Robust Principal Component Analysis （RPCA） approaches do not consider the continuity and the incompletion of sequential data， one type of lowrank matrix recovery model，正则化网络 named Regularized Incomplete RPCA （RIRPCA）， was proposed. First， the model of RIRPCA was constructed based on a metric function for evaluating the continuity， where the model minimized a weighted combination of the matrix nuclear norm， L1 norm and regularized term. Then， the augmented Lagrange multipliers algorithm was employed to solve the proposed convex optimization problem. This algorithm has good scalability and low computation complexity. Finally， RIRPCA was applied to the background modeling of videos. The experimental results demonstrate that the proposed method has the superiority of recovering missing entries and separating foreground over matrix completion and incomplete RPCA.
        Key words： Robust Principal Component Analysis （RPCA）； lowrank matrix recovery； background modeling； nuclear norm minimization； augmented Lagrange multiplier
        0引言
        在计算机视觉、模式识别、信号处理和机器学习等领域中，人们所获取的数据集往往来自于多个模态。尽管有些数据集的维数比较高（如：视频序列和人脸数据集），但它们内在的维数通常远低于数据表示空间的维数。以主成分分析（Principal Component Analysis， PCA）[1]为代表的线性子空间模型假设相关数据集存在于一个低维线性子空间中，即数据集构成的矩阵是低秩的。当数据矩阵受到小的高斯噪声腐蚀时，PCA可有效地执行维数约减、噪声移除和特征提取。但当矩阵存在大量丢失元素、大的稀疏噪声或野点时，PCA却不再奏效。对PCA鲁棒性能的研究一直是人们关注的一个焦点。
        低秩矩阵恢复根据矩阵的低秩结构来恢复低秩成分、稀疏噪声或丢失元素，是压缩感知理论从一阶到二阶的进一步发展[2-3]。鲁棒PCA（Robust PCA， RPCA）[4-5]和矩阵补全（Matrix Completion， MC）[6-7]是低秩矩阵恢复的两类代表模型，它们分别对大的稀疏噪声腐蚀和丢失元素具有鲁棒性。RPCA将数据矩阵分解为一个低秩矩阵与一个稀疏噪声矩阵之和，Candès等[5]提出的主成分追踪已成为RPCA的一个标准范式。MC根据矩阵的低秩性质来补全丢失元素，它最初被描述为仿射秩最小化模型，Candès等[6-7]将此模型凸松弛到核范数最优化问题。
        在许多实际应用中，与时间或空间相关的数据集（如：视频序列和脑电图信号）往往是有序的，因此也具有一定的连续性。当这类低秩数据集受到稀疏噪声腐蚀且含有丢失元素时，稀疏噪声的大小和丢失元素的多少分别会对RPCA和MC的恢复能力产生重要的影响。为了增强对稀疏噪声和丢失元素的鲁棒性，文献[8]提出了不完全RPCA（Incomplete RPCA， IRPCA）模型，并使用增广拉格朗日乘子法来求解此模型，该方法能更好地恢复低秩成分与稀疏噪声；文献[9]将IRPCA推广到非凸情形，并从理论上证明了所提算法的收敛性。
        RPCA、MC和IRPCA这三类模型具有一个共同缺点，即丢失元素所对应的噪声无法恢复。然而，噪声有时也是非常重要的待恢复成分，如在视频背景建模中，噪声对应着前景。此外，这三种模型也没有考虑数据集的有序性或连续性。为克服现有模型在恢复稀疏噪声和利用数据集有序性等方面的不足，本文提出了IRPCA的一种正则化模型。此模型充分利用了数据集的有序性，能够有效地恢复丢失元素所对应的噪声，在一定程度上对MC和IRPCA进行了改善。
        2不完全鲁棒PCA的正则化方法
        在低秩矩阵恢复中，如果数据集的稀疏噪声没有任何结构或特征，则恢复噪声成分是不
可能的。在视频背景建模中，低秩成分对应背景，稀疏噪声对应前景，且数据矩阵D=（d1，d2，…，dn）为序列数据集。视频序列d1，d2，…，dn往往是连续变化的，这也等价于稀疏噪声是连续变化的。稀疏噪声的这种连续变化特征可以在一定程度上有助于恢复丢失元素所对应的噪声。众所周知，现有的MC、RPCA和IRPCA等模型均不能恢复丢失元素所对应的噪声。为此，本文提出了一种凸优化模型，它不但可以恢复低秩成分，而且还能有效地恢复有序数据集的丢失元素所对应的噪声。
        对于有序数据集，可以根据数据矩阵D的连续变化来恢复它的部分丢失元素。当x1，x2，…，xn是序列数据时，文献[12]使用∑n-1i=1‖xi+1-xi‖1来度量序列数据的连续性，而本文将采用具有更好光滑性的评价函数：J（X）=∑n-1i=1‖xi+1-xi‖2F，此处X=（x1，x2，…，xn）∈Rm×n。显然J（X）是X的凸函数，且它的取值越小，说明x1，x2，…，xn的变化越平缓。因此，为了恢复丢失元素，将正则项J（X）添加到最优化模型（4）的目标函数上，于是得到IRPCA的正则化模型（Regularized IRPCA， RIRPCA）：
        作为IRPCA模型的推广，最优化问题（5）的目标函数关于块变量A、E和X是可分离的，且约束条件关于这三个块变量也是线性的，因此可以使用ALM算法来求解问题（5）。A
LM也称为乘子交替方向法（Alternating Direction Method of Multiplier， ADMM），是20世纪70年代出现的一种简单且易于实施的最优化方法，它特别适合于求解大规模的分布式的凸优化问题。由于ALM具有良好的可扩展性和较低的计算复杂度，所以它已成为求解核范数最优化问题的主流算法。为此，先构造最优化模型（5）的增广拉格朗日函数：
        3实验分析
        3.1数据集描述与实验设置
        在Bootstrap和Hall视频数据集（http：//perception.i2r.astar.edu.sg/bk_model/bk_index.html）上进行实验。对于这两个视频序列，分别选取前200帧图像，每帧图像的大小分别为120×160和144×176，部分图像如图1所示。因此，得到维数分别为19200×200和25344×200的两个数据矩阵。根据伯努利分布对矩阵的元素进行随机采样，即（i， j）∈Ω的概率为p，（i， j）Ω的概率为1-p。
        根据文献[5]的建议，取λ=1/max（m，n）。本文取正则化参数τ=0.0005λ，最大迭代次数N=100。对于其他数据集，可以采用交叉验证法选取合适的τ。其余参数按照求解RPCA的
算法进行设置[10]： ρ=1.1，ε=10-8， μ=1.25/‖PΩ（D）‖和=107μ。在随后的实验中，将RIRPCA的实验结果与MC和IRPCA进行比较。
        3.2实验结果比较与分析
        对于给定的数据矩阵D和指标集Ω，利用某种矩阵恢复算法来补全PΩ（D）的所有丢失元素，所得到的恢复矩阵记为。本文使用相对误差来评价各种方法的恢复性能，其定义为：
        ‖D-‖F‖D‖F（17）
        相对误差越小，算法的恢复性能越好。下面考虑4种采样概率，即p=0.2， 0.4， 0.6， 0.8。当采样概率p固定时，将算法重复10次，最终报告相对误差的平均值及对应的标准差，实验结果如表1～2所示。
        从表1～2的相对误差比较中可以得出：
        1）与MC和IRPCA相比，RIRPCA取得了最佳的相对误差。对于Bootstrap数据集，RIRPCA比MC的平均相对误差低5.97%～18.06%，比IRPCA低2.55%～5.34%；对于Hall数据集，RIRPCA比MC的平均相对误差低3.34%～9.22%，比IRPCA低1.94%～2.86%。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。