Exact Matrix Completion via Convex Optimization
Exact Matrix Completion via Convex Optimization
复制标题
DOI：
10.1007/s10208-009-9045-5
复制
发表时间：
2009-12-01
影响因子：
3
通讯作者：
Recht, Benjamin
中科院分区：
文献类型：
--
作者：
Candes, Emmanuel J.;Recht, Benjamin
我们考虑了一个很大的实际兴趣问题：从其条目的采样中恢复数据矩阵。假设我们从矩阵M中随机选择了M条目。我们可以完成矩阵并恢复我们未曾看到的条目吗？我们证明一个人可以从看起来不完整的集合中完美地恢复大多数低级矩阵条目。我们证明，如果采样条件的数字m的数量m obeymm> = = = cn（1.2）r log n对于某些正数常数c，则可以通过求解简单的凸优化程序来完美地恢复等级r的大多数n x n矩阵。该程序找到了适合数据的最低核标准的矩阵。上面的条件假定等级不太大。但是，如果一个人用1.25替换1.2指数，则结果对等级的所有值都保留。任意矩形矩阵也有类似的结果。我们的结果与最近有关压缩感测的文献有关，并表明信号和图像以外的对象可以从非常有限的信息中完美地重建。
We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen?We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeysm >= Cn(1.2)r log nfor some positive numerical constant C, then with very high probability, most n x n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.