稀疏性(sparse)与低秩性(low-rank)是矩阵最重要的两个性质，数学家在研究矩阵分解(Matrix Decomposition, Matrix Factorization, Matrix Completion)的过程中，从最开始的纯数学上的分解(如 SVD,NMF)，终于发展到从矩阵自身性质的角度考虑，产生了稀疏分解与低秩分解两个流派。一般情况下，矩阵不会同时具有稀疏性与低秩性，但注意到在矩阵分解中，分解出的矩阵不止一个，因此 X = L + E 可以分解出一个稀疏矩阵与一个低秩矩阵，称为稀疏低秩分解(Low-rank & Sparse Matrix Decomposition)，代表是robust PCA算法。目前，矩阵分解或者矩阵恢复在各种类型的工作中都被充分利用，产生了压缩感知的方法，图像领域的图像恢复，识别，使用矩阵分解做聚类等。与之相关的，我们先了解矩阵的这两种表征方式，然后再介绍有关的应用。
稀疏表征
稀疏表征，从字面上的意思，是希望矩阵很稀疏，也就是大部分元素为0。给定原始空间中的矩阵 X ，找到某个空间中的一组基 Y ， X 在 Y 上的表达为 Z ，因此有：
既然 Z 是矩阵在另外一个空间上的表达，希望 Z 更加稀疏，也就是稀疏表征的目的，本质上，也是一种降维的思路。换一种说法，给定的 m维空间中有一组 过完备的基(m*n的矩阵，m << n)，如何选择最少个数的 基向量，重构它自己。
问题来了，注意到 X 是两个变量的乘积，在没有先验知识的情况下是不可解的。我们寻求的是 X 的稀疏表征 Z ，在这里， Y 并不是主要因素。如果将 Y 用 X 替代，不也可以理解为通过 X 来寻找它自身空间里的一个更稀疏的表征：
现在只有一个待求解变量了，而且也有正则项，可以通过范数求解。但L0范数的求解是一个NP问题，所以选取了它的近似，L1范数。求解过程这里不作讨论，其对应算法，会在之后单独介绍。
低秩表征
随着对现实数据认识的加深，发现矩阵的表象(稀疏性)在很多场合已经不能起到更多的作用，所以数学家们开始考虑更多的情况。如在稀疏表征中考虑噪声E的影响，但由于原有的数据已经很稀疏，分离出一个稀疏矩阵与一个更稀疏的噪声矩阵E，这种思路的可行性值得怀疑，实验检验也表示这种方法的鲁棒性很差。稀疏性已经不足以满足需要，所以自然想到矩阵的另一个重要性质——低秩性。矩阵的秩表示矩阵非零奇异值的个数。矩阵的低秩性表示矩阵可以使用更少的向量去进行表征，在高维数据中的体现尤为明显。先给出一个朴素的优化函数：
核范数是矩阵秩的凸，比较好求解，因此，很多时候直接使用核范数表示。
考虑到现实数据中存在的各种噪声，可以确认我们的目标：给出 X ，X = L + E ，恢复出低秩矩阵 L 与稀疏矩阵 E 。这是低秩性在矩阵恢复中的应用，在低秩表征中，优化函数有细微不同。
同样，这个优化函数不能直接求解，需要使用到它们的凸近似。最终，LRR的优化函数可以写成：
对随机的噪声，选取L1范数效果较好；对列稀疏的噪声，选取2-1范数；对白噪声(噪声服从高斯分布)，选取F范数。
这里简单介绍一下LRR的推导。低秩表征可以写成：
考虑噪声后：
注意到这个优化函数是非凸的，很难求解，需要用到特殊的方法(Paolo, Rene, and Avinash, “A Closed Form Solution to Robust Subspace Estimation and Clustering”, CVPR’11)。这不太优雅，于是继续研究，发现E是一个稀疏的噪声矩阵， EZ≈0 ，于是约束条件变成了 X = XZ + E ，后来的证明表示，在一定条件下这两个函数等价。
总结
SR与LRR是矩阵表征最重要的两种方式，在数据挖掘中，SR常与聚类结合在一起，LRR不只可以做聚类，也常用在矩阵恢复。(如需要进一步了解，可以阅读笔者的组会报告：slider)
参考文献
- Elhamifar E, Vidal R. Sparse subspace clustering[C]. Computer Vision and Pattern Recognition, 2009. CVPR 2009.
- Elhamifar E, Vidal R. Sparse subspace clustering: Algorithm, theory, and applications[J]. IEEE transactions on pattern analysis and machine intelligence, 2013.
- Liu G, Lin Z, Yu Y. Robust subspace segmentation by low-rank representation[C]. Proceedings of the 27th international conference on machine learning, ICML-10.
Categories: DM
