IRPCA

参考论文：Inductive Robust Principal Component Analysis
作者：Bing-Kun Bao, Guangcan Liu, Member, IEEE,
Changsheng Xu, Senior Member, IEEE,
and Shuicheng Yan, Senior Member, IEEE

PCA

PCA由于F范数，对噪声和异常值敏感。具体见本人的另外一篇文章PCA主成分分析

RPCA

目标函数如下：
$min_{Y,E}||Y||_*+\lambda ||E||_1,s.t.X = Y + E$ 假设RPCA的最优解为 $Y^*,E^*$ ，那么对于测试样本，通常是这样：

首先求 $Y^*$ 的SVD, $Y^*=U^**\Sigma^**V^*$
然后： $y^* =U^*(U^*)^Tx$

但是，这个方法并不好，不能很好的处理训练样本本身，更精确的说，由以上方法得到的解 $（U^*(U^*)^TX,X-U^*(U^*)^TX）$ 可能并不是目标函数的最优解。证据表明由 $X-U^*(U^*)^TX$ 得到的误差 $E$ 通常不是稀疏的。

IRPCA

针对PCA和RPCA的不足，本文提出了IRPCA，不仅可以处理严重的损坏（相比于 RPCA），并且有良好的泛化能力。
关键在于：IRPCA从训练数据中学习得到一个低秩投影矩阵P，它能有效地移除误差，并把数据投影到子空间中。
如果异常值没有施加任何限制，那么 IRPCA 是不可能实现的。但是如果，异常值是无序的，则一般情况下没有简单的模型可以拟合它。
幸运的是，IRPCA 是可行的。

首先，即使异常值是乱序的，也能存在一个线性投影 $P_0$ 把数据投影到子空间中，能正确地恢复出数据（即使不是完全精确的恢复）；
其次，两个高维的向量，通常是独立的，近似相互正交，也就是说，异常通常不在正确的子空间中。这样的情况下， $P_0$ 就可以从数据中去除异常。

所以，只要有数据 x，其主成分就可以通过 $y=P_0x$ 获得。

例如：X是1024 * 100，P就是1024 * 1024

IRPCA的目标函数如下：
$min_{P,Y}rank(P)+\lambda ||X-PX||_0,s.t.Y=PX$ 处理后如下： $min_{P,Y}||P||_*+\lambda ||E||_1,s.t.X=PX+E$

IRPCA求解

首先将上述问题转化为其转置的形式： $min_{P,Y}||P^T||_*+\lambda ||E^T||_1,s.t.X^T=X^TP^T+E^T$ 根据论文Robust subspace segmentation by low-rank representation可以得到其计算复杂度是 $O(d^3)$ ，对于高维数据，计算量很大。本文不直接计算上述问题，根据论文Robust Recovery of Subspace Structures by Low-Rank Representation的理论1，最优解 $P^*$ 的转置总是在 $X$ 的列张成的子空间里。所以 $P^*$ 可以表示为 $P^*=L^*(Q^*)^T$ ，其中 $Q^*$ 是通过对X的列进行正交得到的。所以上述问题可以等价为下述更简单的形式： $min_{L,E}||L||_*+\lambda ||E||_1,s.t.X=LA+E$ 然后构建 Lagrangian 函数 $min_{L,E}||J||_*+\lambda ||E||_1,s.t.X=LA+E,J=L$

【机器学习】Inductive Robust Principal Component Analysis(IRPCA)
其中 $Y_1,Y_2∈R^{m×n}$ 分别是 Lagrange 乘子矩阵，μ 是惩罚项参数。显然，优化目标函数可以给出

其中 ρ>1 是一个常数，用于不断增加 μ 的值。
然后通过ALM算法，可以对其进行求解，算法如下：
【机器学习】Inductive Robust Principal Component Analysis(IRPCA)
step1可以通过SVT得到： $J_{k+1}=US_{\frac{1}{\mu}}(\Sigma)V^T$
step2,这里有错，Z应该是L，同理step4
step3可以通过收缩算子得到： $E_{k+1}=S_{\frac{\lambda}{\mu}}(X-L_{k+1}A+\frac{Y_{1k}}{\mu})$

【机器学习】Inductive Robust Principal Component Analysis(IRPCA)

PCA

RPCA

IRPCA

IRPCA求解

相关推荐