【组会】从稀疏表征到低秩表征


稀疏性(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 ,因此有:

min L0(Z) s.t. X = YZ

既然 Z 是矩阵在另外一个空间上的表达,希望 Z 更加稀疏,也就是稀疏表征的目的,本质上,也是一种降维的思路。换一种说法,给定的 m维空间中有一组 过完备的基(m*n的矩阵,m << n),如何选择最少个数的 基向量,重构它自己。

task

问题来了,注意到 X 是两个变量的乘积,在没有先验知识的情况下是不可解的。我们寻求的是 X 的稀疏表征 Z ,在这里, Y 并不是主要因素。如果将 Y X 替代,不也可以理解为通过 X 来寻找它自身空间里的一个更稀疏的表征:

min L0(Z) s.t. X = XZ

 

min L1(Z) s.t. X = XZ

现在只有一个待求解变量了,而且也有正则项,可以通过范数求解。但L0范数的求解是一个NP问题,所以选取了它的近似,L1范数。求解过程这里不作讨论,其对应算法,会在之后单独介绍。


低秩表征

随着对现实数据认识的加深,发现矩阵的表象(稀疏性)在很多场合已经不能起到更多的作用,所以数学家们开始考虑更多的情况。如在稀疏表征中考虑噪声E的影响,但由于原有的数据已经很稀疏,分离出一个稀疏矩阵与一个更稀疏的噪声矩阵E,这种思路的可行性值得怀疑,实验检验也表示这种方法的鲁棒性很差。稀疏性已经不足以满足需要,所以自然想到矩阵的另一个重要性质——低秩性。矩阵的秩表示矩阵非零奇异值的个数。矩阵的低秩性表示矩阵可以使用更少的向量去进行表征,在高维数据中的体现尤为明显。先给出一个朴素的优化函数:

min rank(Z) s.t. X = XZ

核范数是矩阵秩的凸,比较好求解,因此,很多时候直接使用核范数表示。

考虑到现实数据中存在的各种噪声,可以确认我们的目标:给出 X X = L + E ,恢复出低秩矩阵 L 与稀疏矩阵 E 。这是低秩性在矩阵恢复中的应用,在低秩表征中,优化函数有细微不同。

min rank(Z) + L0(E) s.t. X = XZ + E

同样,这个优化函数不能直接求解,需要使用到它们的凸近似。最终,LRR的优化函数可以写成:

min norm(Z) + L1(E) s.t. X = XZ + E

对随机的噪声,选取L1范数效果较好;对列稀疏的噪声,选取2-1范数;对白噪声(噪声服从高斯分布),选取F范数。

这里简单介绍一下LRR的推导。低秩表征可以写成:

min norm(Z) s.t. X = XZ

考虑噪声后:

min norm(Z) + L1(E) s.t. X – E = (X – E)Z

注意到这个优化函数是非凸的,很难求解,需要用到特殊的方法(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.