鲁棒主成分分析模型综述

A Review of Robust Principal Component Analysis Models

摘要: 主成分分析求解的模型适用于去除密集的高斯小噪声，但是对于非高斯噪声或离群点严重的噪声时，主成分分析法去噪效果很不理想，缺乏鲁棒性。针对主成分分析模型的缺点提出了鲁棒主成分分析模型。本文在鲁棒主成分分析的相关理论基础下，研究了鲁棒主成分分析的几种经典模型的去噪效果。通过实验数据及图片的效果，分析对比这几个模型的优缺点。

Abstract: The model solved by principal component analysis is suitable for removing dense Gaussian small noise, but for non-gaussian noise or noise with serious outliers, the denoising effect of principal component analysis is not ideal and lacks robustness. A robust principal component analysis model was proposed to overcome the shortcomings of the PCA model. Based on the theory of robust principal component analysis, this paper studies the denoising effects of several classical models of RPCA. The advantages and disadvantages of these models are analyzed and compared through the results of experimental data and pictures.

1. 引言

2. 鲁棒模型

2.1. 鲁棒主成分分析模型(Robust Principal Component Analysis, RPCA)

2.1.1. 模型的建立

在实际应用中可以将图像看作矩阵X。 $X=A+E$ ，其中A是低秩矩阵，E为稀疏(噪声)矩阵 [2] 。则RPCA模型解决的问题是从带有稀疏大噪声的数据中精确的恢复出低秩矩阵。此模型可以表示为：

$\underset{A,E}{\min }{\Vert A\Vert }_{\ast }+\lambda {\Vert E\Vert }_1\text{s}\text{.t}\text{.}X=A+E$ (1)

其中 ${\Vert \cdot \Vert }_{\text{1}}$ 为矩阵的 ${\mathcal{l}}_1$ 范数， ${\Vert \cdot \Vert }_{\ast }$ 为矩阵的核范数。 $\lambda =1/\sqrt{\max \left(m,n\right)}$ 。A是需要恢复的原矩阵，通常为

低秩的；E是未知的噪声矩阵；X是含噪声的矩阵。

2.1.2. 模型的求解 [3]

对(1)构建增广拉格朗日函数得：

$L_{\mu }\left(A,E,Y\right)={\Vert A\Vert }_{\ast }+\lambda {\Vert E\Vert }_1+\langle X-A-E,Y\rangle +\frac{\mu }{2}{\Vert X-A-E\Vert }_F^2$

迭代低秩矩阵A为：

$\begin{array}{c}{A}^{*}=\arg \underset{A}{\min }{L}_{\mu }\left(A,E,Y\right)\\ =\arg \underset{A}{\min }{\Vert A\Vert }_{\ast }+\langle X-A-E,Y\rangle +\frac{\mu }{2}{\Vert X-A-E\Vert }_F^2\\ =D_{{\mu }^{-1}}\left\{X-E+{\mu }^{-1}Y\right\}\end{array}$

迭代稀疏矩阵E为：

$\begin{array}{c}{E}^{*}=\arg \underset{E}{\min }{L}_{\mu }\left(A,E,Y\right)\\ =\arg \underset{A}{\min }\lambda {\Vert E\Vert }_1+\langle X-A-E,Y\rangle +\frac{\mu }{2}{\Vert X-A-E\Vert }_F^2\\ =S_{\lambda {\mu }^{-1}}\left\{X-A+{\mu }^{-1}Y\right\}\end{array}$

2.2. 双线性鲁棒主成分分析模型(Bilinear Robust Principal Component Analysis, BRPCA)

2.2.1. 模型的建立

使用APG或ALM求解RPCA优化问题，每次迭代时要求对输入矩阵 $X\in R^{m\times n}$ 进行SVD。RPCA模型中含有核范数，虽然在很多情况下这是可以接受的，但是随着X的增大或性能需求的增加更高时，每次进行SVD在计算上过于耗时。为了缓解这个问题，Cabral等人 [4] 使用了双线性因子分解的思想避免使用核范数，减少奇异值阈值的使用。BRPCA模型如下：

$\underset{U,V,E}{\min }\frac{1}{2}\left({\Vert U\Vert }_F^2+{\Vert V\Vert }_F^2\right)+\lambda {\Vert E\Vert }_1\text{s}\text{.t}\text{.}X=UV+E$ (2)

2.2.2. 模型的求解

对(2)构建增广拉格朗日函数得：

$L_{\mu }\left(U,V,E,Y\right)=\frac{1}{2}\left({\Vert U\Vert }_F^2+{\Vert V\Vert }_F^2\right)+\lambda {\Vert E\Vert }_1+\langle X-UV-E,Y\rangle +\frac{\mu }{2}{\Vert X-UV-E\Vert }_F^2$

输出低秩矩阵A为：

$A^{*}=U^{*}{V}^{*}$

其中：

迭代矩阵U为：

$\begin{array}{c}{U}^{*}=\arg \underset{U}{\min }{L}_{\mu }\left(U,V,E,Y\right)\\ =\arg \underset{U}{\min }\frac{1}{2}{\Vert U\Vert }_F^2+\langle X-UV-E,Y\rangle +\frac{\mu }{2}{\Vert X-UV-E\Vert }_F^2\end{array}$ (3)

对(3)式求导有：

$\begin{array}{l}\frac{\partial }{\partial U}\left(\frac{1}{2}{\Vert U\Vert }_F^2+\langle X-UV-E,Y\rangle +\frac{\mu }{2}{\Vert X-UV-E\Vert }_F^2\right)=0\\ U^{*}=\left(X-E+{\mu }^{-1}Y\right)V^{\text{T}}{\left(V{V}^{\text{T}}+{\mu }^{-1}I\right)}^{-1}\end{array}$

迭代矩阵V为：

$\begin{array}{c}{V}^{*}=\arg \underset{V}{\min }{L}_{\mu }\left(U,V,E,Y\right)\\ =\arg \underset{V}{\min }\frac{1}{2}{\Vert V\Vert }_F^2+\langle X-UV-E,Y\rangle +\frac{\mu }{2}{\Vert X-UV-E\Vert }_F^2\end{array}$ (4)

对(4)式求导有：

$\begin{array}{l}\frac{\partial }{\partial V}\left(\frac{1}{2}{\Vert V\Vert }_F^2+\langle X-UV-E,Y\rangle +\frac{\mu }{2}{\Vert X-UV-E\Vert }_F^2\right)=0\\ V^{*}={\left(U^{\text{T}}U+{\mu }^{-1}I\right)}^{-1}{U}^{\text{T}}\left(X-E+{\mu }^{-1}Y\right)\end{array}$

迭代稀疏矩阵E为：

$\begin{array}{c}{E}^{*}=\arg \underset{E}{\min }{L}_{\mu }\left(U,V,E,Y\right)\\ =\arg \underset{E}{\min }\lambda {\Vert E\Vert }_1+\langle X-UV-E,Y\rangle +\frac{\mu }{2}{\Vert X-UV-E\Vert }_F^2\\ =S_{\lambda {\mu }^{-1}}\left\{X-UV+{\mu }^{-1}Y\right\}\end{array}$

2.3. 归纳主成分分析模型(Inductive Robust Principal Component Analysis, IRPCA)

2.3.1. 模型的建立

由于RPCA和BPCA都适用于批量运算，因此每次观察到一个新的数据点时，都必须在所有数据上运行算法，对不是批量运算的应用程序来说并不是很适合。IRPCA模型 [5] 则克服了这一局限性。给定一个初始数据矩阵X，IRPCA不是学习它的低秩分量A，而是尝试学习一个投影矩阵P，它将X投影到低维子空间上。换句话说，存在矩阵P使得 $A=PX$ 。随后，如果观察到一个新的数据点 $x_{new}$ ，就可以很容易地将其投影到低维子空间上，以便重新恢复。IRPCA模型如下：

$\underset{P,E}{\min }{\Vert P\Vert }_{*}+\lambda {\Vert E\Vert }_1\text{s}\text{.t}\text{.}X=PX+E$ (5)

2.3.2. 模型的求解

对(5)构建增广拉格朗日函数得：

$L_{\mu }\left(P,E,Y\right)={\Vert P\Vert }_{*}+\lambda {\Vert E\Vert }_1+\langle X-PX-E,Y\rangle +\frac{\mu }{2}{\Vert X-PX-E\Vert }_F^2$

输出低秩矩阵A为：

$A^{*}=P^{*}X$

迭代低秩矩阵P为：

$\begin{array}{l}\arg \underset{p}{\min }{L}_{\mu }\left(P,E,Y\right)\\ =\arg \underset{p}{\min }{\Vert P\Vert }_{*}+\langle X-PX-E,Y\rangle +\frac{\mu }{2}{\Vert X-PX-E\Vert }_F^2\\ =\arg \underset{p}{\min }{\mu }^{-1}{\Vert P\Vert }_{*}+\frac{1}{2}{\Vert PX-\left(X-E+{\mu }^{-1}Y\right)\Vert }_F^2\end{array}$

迭代稀疏矩阵E为：

$P_{k+1}^{\ast }=D_{{\left(\mu n\right)}^{-1}}\left\{P_k-n^{-1}\left(P_{k}X-X+E-{\mu }^{-1}Y\right)X^{\text{T}}\right\}$ $\begin{array}{c}{E}^{*}=\arg \underset{E}{\min }{L}_{\mu }\left(P,E,Y\right)\\ =\arg \underset{E}{\min \lambda }{\Vert E\Vert }_1+\langle X-PX-E,Y\rangle +\frac{\mu }{2}{\Vert X-PX-E\Vert }_F^2\\ =S_{\lambda {\mu }^{-1}}\left\{X-PX+{\mu }^{-1}Y\right\}\end{array}$

2.4. 标准正交鲁棒主成分分析模型(Orthonormal Robust Principal Component Analysis, ORPCA)

2.4.1. 模型的建立

对于给定的数据矩阵 $X\in R^{m\times n}$ ，RPCA试图恢复低秩矩阵 $A\in R^{m\times n}$ ，可以认为是X在低维子空间上的投影，我们称之为主子空间。IRPCA将这一思想更进一步，尝试学习投影矩阵 $P\in R^{m\times n}$ ，它将X投影到主子空间上，从而检索A (即 $A=PX$ )。假设主子空间为r维，其中 $r\le \min \left(m,n\right)$ ，则需要学习一组基

向量 $U=\left[u_1,u_2,\cdots ,u_r\right]\in R^{m\times r}$ 张成主子空间。为了限制U，这里要求这组基向量是正交的，即 $U^{\text{T}}U=I$ 。

经典的主成分分析通常将这些基向量称为主成分。学习了主成分后，投影的数据点将表示为主成分的线性组合。换句话说，如果 $V\in R^{m\times n}$ 是一个合适系数的矩阵，我们可以写成 $A=UV$ 。

下面，根据前面的讨论，修改RPCA问题。我们可以写出 $A=UV$ ， $U^{\text{T}}U=I$ 。由于核范数的不变性，我们得到：

${\Vert A\Vert }_{*}={\Vert UV\Vert }_{*}={\Vert V\Vert }_{*}$

建立标准正交鲁棒主成分分析模型 [6] (ORPCA)如下：

$\underset{V,E,U}{\min }{\Vert V\Vert }_{*}+\lambda {\Vert E\Vert }_1\text{s}\text{.t}\text{.}X=UV+E,U^{\text{T}}U=I$ (6)

2.4.2. 模型的求解

对(6)构建增广拉格朗日函数得:

$L_{\mu }\left(V,E,U,Y\right)={\Vert V\Vert }_{*}+\lambda {\Vert E\Vert }_1+\langle X-UV-E,Y\rangle +\frac{\mu }{2}{\Vert X-UV-E\Vert }_F^2$

输出低秩矩阵A为：

$A^{*}=U^{*}{V}^{*}$

迭代矩阵V为：

$\begin{array}{c}{V}^{*}=\arg \underset{V}{\min }{L}_{\mu }\left(V,E,U,Y\right)\\ =\arg \underset{V}{\min }{\Vert V\Vert }_{*}+\langle X-UV-E,Y\rangle +\frac{\mu }{2}{\Vert X-UV-E\Vert }_F^2\\ =D_{{\mu }^{-1}}\left\{U^{\text{T}}\left(X-E+{\mu }^{-1}Y\right)\right\}\end{array}$

迭代矩阵U：

$\begin{array}{c}{U}^{*}=\arg \underset{U}{\min }{L}_{\mu }\left(V,E,U,Y\right)\\ =\arg \underset{U}{\min }\langle X-UV-E,Y\rangle +\frac{\mu }{2}{\Vert X-UV-E\Vert }_F^2\\ =\arg \underset{U}{\min }\frac{1}{2}{\Vert \left(X-E+{\mu }^{-1}Y\right)-UV\Vert }_F^2\end{array}$

迭代稀疏矩阵E为：

$\begin{array}{c}{E}^{*}=\arg \underset{E}{\min }{L}_{\mu }\left(V,E,U,Y\right)\\ =\arg \underset{E}{\min }\lambda {\Vert E\Vert }_1+\langle X-UV-E,Y\rangle +\frac{\mu }{2}{\Vert X-UV-E\Vert }_F^2\\ =S_{\lambda {\mu }^{-1}}\left\{X-UV+{\mu }^{-1}Y\right\}\end{array}$

3. 实验

3.1. 图片实验

首先，选取大小规模为 $650\times 650$ 的原始图片见，对原始图片添加含噪率为10%的椒盐噪声，详情见图1。设定算法迭代终止条件为 $tol=1e-6$ ，迭代最大次数为1000次，其他参数为默认值。算出各个算法恢复矩阵后的相对错误率，算法运行时间和算法达到收敛时迭代次数。从而能更准确的对各类算法进行对比总结。

Figure 1. Original pictures and pictures with noise

图1. 原始图片与含有噪声的图片

3.2. 实验结果

由图2中的图像与图1对比和表1数据对比，我们可以看出传统的RPCA耗时时间最长，迭代次数最多，所得图像相对误差较大；BRPCA耗时与迭代次数均较少，但图像误差仅次于RPCA；IRPCA耗时时间与所需的迭代次数最短，所的图像较为清晰，误差较小；ORPCA所需时长与迭代次数略高于BRPCA，但所的图像最清晰，误差最小。

(a) RPCA (b) BRPCA (c) IRPCA (d) ORPCA

Figure 2. Image denoised by each algorithm

图2. 各算法去噪后的图片

Table 1. Data denoised by each algorithm

表1. 各算法去噪后的数据

3.3. 实验小结

在本文中，我们介绍了几种主成分分析模型，即RPCA模型，BRPCA模型，IRPCA模型和ORPCA模型，分析了他们的原理，模型的求解并进行了实验，通过实验我们可以发现，这几种模型对图片去噪是有效的，但是所需要的时间，迭代次数，以及误差大小各不相同，利用直观的图像和数据更加客观的反应各种算法的优缺点。