Robust PCA，稀疏子空间聚类（SSC）与低秩表示（LRR）

低秩表示（Low-Rank Representation, LRR）方法由Liu等于2010年提出，是用于解决子空间分割等问题的一种有效方法，通过在Robust PCA的基础上引入子空间聚类的思想，加入字典项使Robust PCA中的单一低秩子空间变为多个子空间的集合，从而达到更好的效果。

PCA与Robust PCA

主成分分析（PCA）是我们熟知的降维方法，能有有效找出数据中的主要结构，去除噪音，在一组新的基下尽量表达原有数据间的关系。不过，PCA方法对于大的噪声或者严重的离群点（Outlier）比较敏感而难以正常工作，而Robust PCA正解决了这一问题。Robust PCA假设噪声$ E $是稀疏的（而不太关心噪声的强度），优化以下表达式：

\[\begin{equation*} \min_{Z, E} rank(Z) + \lambda \Vert E \Vert_0 \; s.t. X = Z + E \end{equation*}\]

其中，$ rank(\cdot) $表示矩阵的秩，$ \Vert\cdot\Vert_0 $表示矩阵的L0范数（矩阵非0元素的个数）。A是包含真实结构的低秩矩阵，E是稀疏噪声。考虑线性代数中，矩阵的秩度量的是矩阵行列之间的相关性。如果矩阵是低秩的，说明这个矩阵各行/列的相关性很强，从而可以投影到更低维的线性子空间，用更少的若干向量就可以表达。而人脸图像、用户-物品表格等矩阵正具有这种强的相关性，因此在理想状态下一般是低秩的。不过，如果低秩矩阵$ Z $受到随机稀疏噪声$ E $的影响，那么$ Z $的低秩性就被破坏了，变为了我们实际观察到的高秩矩阵$ X $。而Robust PCA想要做的，正是从这个$ X $中寻找尽可能低秩的$ Z $和尽可能稀疏的$ E $。

然而，矩阵的秩$ rank(\cdot) $和L0范数$ \Vert\cdot\Vert_0 $非凸且非光滑，难以进行优化，因此我们一般使用矩阵的核范数$ \Vert\cdot\Vert_* $（矩阵奇异值的和）和L1范数$ \Vert\cdot\Vert_1 $对其进行松弛，从而得到一个凸优化问题：

\[\begin{equation*} \min_{Z, E} \Vert Z \Vert_* + \lambda \Vert E \Vert_1 \; s.t. X = Z + E \end{equation*}\]

稀疏子空间聚类（Sparse Subspace Clustering, SSC）

稀疏子空间聚类（Sparse Subspace Clustering, SSC）由Elhamifar等于2009年提出，其优化如下表达式：

\[\begin{align*} min \Vert &z_i \Vert_0 \\ s.t. \; &x_i = X_{\hat{i}}z_i, \forall i \\ where \; &X_{\hat{i}} = [x_1, ..., x_{i - 1}, x_{i + 1}, ..., x_n] \end{align*}\]

也就是说，迫使每个数据$ x_i $只用其他数据（不包括自身）的线性组合来表示，且使用其他数据越少（即表达越稀疏）越好。上式用矩阵形式表示为：

\[\begin{align*} min \Vert &Z \Vert_0 \\ s.t. \; &X = XZ, Z_{ii} = 0 \end{align*}\]

使用L1范数对上式中的L0进行松弛，并加入正则项，得：

\[\begin{align*} min \Vert &Z \Vert_1 + \lambda \Vert E \Vert_1\\ s.t. \; &X = XZ + E, Z_{ii} = 0 \end{align*}\]

上式的解$ Z $具有块对角结构，这种结构解释了数据的子空间属性：块的个数代表子空间个数，每个块的大小代表对应子空间的维数，同一块的数据属于同一子空间。

低秩表示（Low-Rank Representation, LRR）

考虑前面的Robust PCA，我们可以注意到，Robust PCA隐性地假定数据中的主要结构是在一个单一的低秩子空间里的。然而如果数据是从多个子空间$ \mathcal{S}_1, \mathcal{S}_2, ..., \mathcal{S}_k $中取样得到的呢？Robust PCA会将它们当做是从$ \mathcal{S} = \sum_{i=1}^{k}\mathcal{S}_i $中取样得到的。然而，$ \mathcal{S} $很可能比实际上的$ \bigcup_{i=1}^{k}\mathcal{S}_i $要大得多，使得结果不够准确。LLR在Robust PCA的基础上通过引入一个字典矩阵$ A $，将这种多子空间的情况纳入考量，表述如下：

\[\begin{equation*} \min_{Z, E} \Vert Z \Vert_* + \lambda \Vert E \Vert_1 \; s.t. X = AZ + E \end{equation*}\]

在一些特定任务中，我们可以选择$ A = X $，则上式可以表述为：

\[\begin{equation*} \min_{Z, E} \Vert Z \Vert_* + \lambda \Vert E \Vert_1 \; s.t. X = XZ + E \end{equation*}\]

可见其形式与SSC类似（然而没有$ Z_{ii} = 0 $的约束）。事实上，其也确实能够很好地解决稀疏子空间聚类的问题。简单地说，我们大概可以将LRR理解为Robust PCA和SSC两种方法的融合。

参考

  • Guangcan Liu, Zhouchen Lin, Shuicheng Yan, Ju Sun, Yong Yu, and Yi Ma. Robust recovery of subspace structures by low-rank representation. IEEE Transactions on Pattern Analysis & Machine Intelligence, 35(1):171–184, 2010.
  • E. Elhamifar and R. Vidal. Sparse subspace clustering. In IEEE Conference on Computer Vision and Pattern Recognition, 2009. CVPR 2009., pages 2790–2797, 2009.
  • 机器学习中的范数规则化之（二）核范数与规则项参数选择http://blog.csdn.net/zouxy09/article/details/24972869
  • Matlab code: solving the low-rank representation (LRR) problems https://sites.google.com/site/guangcanliu/