转载

研究领域总结（二）：稀疏——矩阵补全

I.定义

矩阵补全（Matrix Completion）是指如下一个问题: 有一个巨大的矩阵$X/in/mathbb{R}^{m/times n}$，然而人们只能观测到其中的部分元素。记观测到的矩阵为矩阵$M/in/mathbb{R}^{m/times n}$（没观测到的元素位置以$0$填充），则$P_/Omega(X)=P_/Omega(M)$,其中观测到的元素下标集合记为$/Omega$，$P_/Omega$表示投影到$/Omega$。

为了说明它的意义，这里举一个最常见的情形，即评分预测/推荐系统——协同过滤，如豆瓣之类的网站，会有很多用户（看作行）对很多电影（看作列）进行打分（矩阵元素的值），每个用户只会对很少的电影打分，这就导致我们的打分矩阵是一个部分观测到的矩阵，而往往我们想预测出来用户对没有打分的电影的评分，依次来推荐或挖掘等等。同时注意到行数和列数往往非常非常大（>百万级别），并且矩阵的稀疏度可能很高很高（<0.x%）。

显然这个问题是个不适定问题，想要补全整个矩阵，我们需要一些额外的约束，最常见的就是假设这个矩阵是低秩的，一方面这符合我们对自然界的观测，另一方面可以用“物以类聚，人以群分”的一致性来做直觉解释。考虑观测有噪声的情况，则整个问题可以形式化为：

/[ /min_{X}/|P_/Omega(X-M)/|_F^2 /quad s.t. rank(X)/leq k. /]

II.求解：化归到稀疏问题

rank是个很难搞的东西，而且把整个问题变成非凸的了。把$X$的奇异值表示成向量形式$/sigma$，那么根据SVD分解的性质，$rank(X)/leq k$等价于 $/|/sigma/|_0/leq k$。这样，就化归到了稀疏问题上来，可以用压缩感知、稀疏编码的思路来思考，只不过目标从向量拓展到了矩阵。

1.松弛到凸问题。

/[ /min_{X}/|P_/Omega(X-M)/|_F^2 +/lambda /|X/|_* /]

关于这个问题，有很多解法，大部分都是从稀疏里变换过来的，如收缩算子、ADMM等等。

Candes证明了矩阵补全和压缩感知一样，在满足矩阵size和采样率（观测稀疏度）要求下，有exact recovery的bound（事实上，矩阵补全的坑就是Candes挖的）。有兴趣的可以读一下他的paper： E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Found. of Comput. Math. , 9 717-772

2.非凸解法。

同样的，虽然松弛到凸问题有最优解，有bound guarantee，但是论起实际效果往往非凸的一些解法更准确更快速。这部分我做的比较多。主要两类：

- 类似OMP，可以用贪心方法选基，每次选一个rank one的矩阵，然后更新系数，选k个即能保证矩阵秩小于等于k。注意到一个重要的区别是稀疏里有个字典，也即从一组冗余基里选，而矩阵补全没有这样一个字典，可以从无限个数的基里选，可以用top SVD 或者其它子目标问题求解得到。
- 非凸惩罚项，比如MCP。

III.协同过滤、去噪

工业界的推荐系统最主要的两个思路就是基于内容和协同过滤两种。协同过滤更standard的是用矩阵分解来做（个人认为主要还是矩阵分解比补全出来的早，抢占了市场），矩阵分解根据一篇paper的定理（一时忘记出处了），其实是和Nuclear norm约束等价的。期待矩阵补全在实际中的更多应用。此外，矩阵补全也可以用来做图像去噪。

正文到此结束