Robust PCA via Outlier Pursuit

Xu H, Caramanis C, Sanghavi S, et al. Robust PCA via Outlier Pursuit[C]. neural information processing systems, 2010: 2496-2504.

引

这篇文章同样是关于矩阵恢复的。假设 $M = L_0 + C_0 \in \mathbb{R}^{p \times n}$ ，即 $M$ 实际上是由一个低秩矩阵 $L_0$ 和稀疏矩阵 $C_0$ 构成。需要注意的是，这里的稀疏不是指某些元素为0，而是某列为零。可以简单地认为， $L_0$ 中是一些有用的正确的样本，而 $C_0$ 中的是错误的样本（非零的部分）。所以，我们能够从中将 $L_0$ 的列空间恢复出来，并识别出那些样本属于 $C_0$ ，即是错误的呢？

上面的作者的说法，我再用自己的话讲一下。 $M$ 中的每一列都是一个 $p$ 维样本，有些时候我们会遇到这种情况，有些样本是错误的。这个错误是指很严重的错误，而不是被一些噪声污染了，就像是这些数据是人的身高体重，却混入了长颈鹿的身高体重。所以呢，我们有理由相信，俩者分布在俩个子空间里，我们要做的就是判断哪个子空间里是我们想要的，哪个是错误的样本。显然正确的样本不能太少，而且正确的样本必须靠的紧凑一些。所以，这么想来，其实要求还不少。

显然直接这么做是不可靠的，举一个极端的例子： $M$ 中仅有 $M_{11}$ 非零，那么显然是无法判断第一列是否是正确的样本的。所以，我们需要一个不连贯条件:

在这里插入图片描述

此外，作者也考虑了带噪声的问题，其中是噪声。

针对不带噪声的问题，作者求解的下列问题：

在这里插入图片描述

其中为列的范数的和,是的核范数。

针对带噪声问题，作者求解的是下列问题：

在这里插入图片描述

主要结果

定理1

在这里插入图片描述

定理2

在这里插入图片描述

理论证明

构造Oracle Problem

在这里插入图片描述

其中, 是中不为0的非稀疏列的指标集，下面的类似的符号也类似的定义。

这个神谕问题，假设 $U_0, V_0, \mathcal{I}_0$ 是已知的。

作者先证明，满足 $M=L'+C';\mathcal{P}_{U_0}(L')=L';\mathcal{P}_{\mathcal{I_0}}(C')=C'$ 的解有下列性质：
$U'U^T = U_0U_0^T, \quad \mathcal{I'}\subseteq \mathcal{I}_0$
这意味着， $\hat{L}$ 的列空间和 $L_0$ 的列空间一致， $\hat{C}$ 中的列（非0）也确实是错误的列。