PCA与RPCA

PCA与RPCA

PCA和RPCA从名字看是有一些相似性的,两者的区别在于对于误差的假设不同,PCA假设数据误差是服从高斯分布的,即数据噪声较小;RPCA假设数据噪声是稀疏的,并且可能是强的噪声;

一般推导主成分分析可以有两种方法:

  • 最近可重构性:样本点到超平面要尽可能近;
  • 最大可分性:样本点在这个超平面上的投影尽可能分开,即最大化投影方差;

下面基于最大化投影方差来回归该算法,首先,先回顾一下PCA操作的步骤:

  • 对样本数据进行中心化处理(这步操作比较重要,特别是对推导公式)
  • 求样本的协方差矩阵;
  • 对样本的协方差矩阵进行特征值分解,并通过前k个特征值对应的特征向量进行映射:

\[ \boldsymbol{x}_{i}^{\prime}=\left[\begin{array}{c}{\boldsymbol{\omega}_{1}^{\mathrm{T}} \boldsymbol{x}_{i}} \\ {\boldsymbol{\omega}_{2}^{\mathrm{T}} \boldsymbol{x}_{i}} \\ {\vdots} \\ {\boldsymbol{\omega}_{d}^{\mathrm{T}} \boldsymbol{x}_{i}}\end{array}\right] \]

最大方差推导:

假设原始的坐标为\(\left\{\boldsymbol{v}_{1}, \boldsymbol{v}_{2}, \ldots, \boldsymbol{v}_{n}\right\}\),中心化之后表示为 \(\left\{\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \ldots, \boldsymbol{x}_{n}\right\}=\left\{\boldsymbol{v}_{1}-\boldsymbol{\mu}, \boldsymbol{v}_{2}-\boldsymbol{\mu}, \ldots, \boldsymbol{v}_{n}-\boldsymbol{\mu}\right\}\) ,向量内积可以理解为第一个向量在第二个向量上的投影长度,因此 \(x_i\) 在 \(\omega\)上的投影可以表示为 \(\left(\boldsymbol{x}_{i}, \omega\right)=\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{\omega}_{\mathrm{o}}\) ,根据上述内容,我们需要优化的函数是最大化投影方差,即:

\[ \begin{aligned} D(\boldsymbol{x})=& \frac{1}{n} \sum_{i=1}^{n}\left(\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{\omega}\right)^{2}=\frac{1}{n} \sum_{i=1}^{n}\left(\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{\omega}\right)^{\mathrm{T}}\left(\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{\omega}\right) \\=& \frac{1}{n} \sum_{i=1}^{n} \boldsymbol{\omega}^{\mathrm{T}} \boldsymbol{x}_{i} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{\omega} \\=&\boldsymbol{\omega}^{\mathrm{T}} \left(\frac{1}{n} \sum_{i=1}^{n} \boldsymbol{x}_{i} \boldsymbol{x}_{i}^{\mathrm{T}}\right) \boldsymbol{\omega} \end{aligned} \]

进一步,我们可以得到需要求解的最大投影方向就是协方差矩阵最大特征值对应的特征矩阵

\[ \left\{\begin{array}{l}{\max \left\{\omega^{\mathrm{T}} \Sigma \omega\right\}} \\ {\text { s.t. } \omega^{\mathrm{T}} \omega=1}\end{array}\right. \]

RPCA

RPCA用以解决含有高幅度尖锐噪声的数据,其基本假设是数据矩阵包含结构信息(该矩阵是低秩的),和噪声矩阵(该矩阵是稀疏的),所以RPCA希望将原始矩阵分解为 \(D=A+E\) 的形式:

\[ \min _{A, E} \operatorname{rank}(A)+\lambda\|E\|_{0} \quad \text { s.t. } A+E=D \]

这里的\(rank(\cdot)\) 和 \(L_0\) 范数非凸、非光滑,因此需要进行放缩,即使用核范数替代 \(rank(\cdot)\) 使用 \(L_1\) 代替 \(L_0\) :
\[ \min _{A, E}\|A\|_{*}+\lambda\|E\|_{1} \quad \text { s.t. } \quad A+E=D \]

区别

PCA的优化目标是:

\(D = L + N\),即低秩矩阵L和独立同分布的Gaussian噪声;

RPCA的优化目标是:

\(D = L + S\),即低秩矩阵L和稀疏尖锐噪声矩阵\(S\)

参考:https://blog.csdn.net/u010545732/article/details/19066725

上一篇:Luogu3379 【模板】最近公共祖先(LCA)


下一篇:CF1153F Serval and Bonus Problem FFT