Matrix Completion With Noise
Matrix Completion With Noise
复制标题
DOI：
10.1109/jproc.2009.2035722
复制
发表时间：
2010-06-01
影响因子：
20.6
通讯作者：
Plan, Yaniv
中科院分区：
文献类型：
--
作者：
Candes, Emmanuel J.;Plan, Yaniv
在压缩传感之后，最近出现了一个新的领域。这一领域解决了一系列具有重大实际意义的问题，即从似乎不完整甚至可能损坏的信息中恢复数据矩阵。在最简单的形式中，问题是从其条目的小样本中恢复矩阵。它出现在科学和工程的许多领域，包括协同过滤，机器学习，控制，遥感和计算机视觉，仅举几例。本文综述了矩阵完备化的新文献，指出在适当的条件下，可以通过求解一个简单的凸优化问题，即数据约束下的核范数极小化问题，从一个近似极小的元素集合中恢复出一个未知的低秩矩阵.此外，本文介绍了新的结果表明，矩阵完成是可证明准确的，即使当观察到的几个条目被破坏了少量的噪声。一个典型的结果是，人们可以恢复一个未知的n × n矩阵的低秩r从刚刚约nr log（2）n噪声样本与误差成比例的噪声水平。我们提出的数值结果，补充我们的定量分析，并表明，在实践中，核范数最小化准确地填补了许多缺失的条目，大型低秩矩阵，从几个嘈杂的样本。矩阵补全和压缩感知之间的一些类比在整个讨论。
On the heels of compressed sensing, a new field has very recently emerged. This field addresses a broad range of problems of significant practical interest, namely, the recovery of a data matrix from what appears to be incomplete, and perhaps even corrupted, information. In its simplest form, the problem is to recover a matrix from a small sample of its entries. It comes up in many areas of science and engineering, including collaborative filtering, machine learning, control, remote sensing, and computer vision, to name a few. This paper surveys the novel literature on matrix completion, which shows that under some suitable conditions, one can recover an unknown low-rank matrix from a nearly minimal set of entries by solving a simple convex optimization problem, namely, nuclear-norm minimization subject to data constraints. Further, this paper introduces novel results showing that matrix completion is provably accurate even when the few observed entries are corrupted with a small amount of noise. A typical result is that one can recover an unknown n x n matrix of low rank r from just about nr log(2)n noisy samples with an error that is proportional to the noise level. We present numerical results that complement our quantitative analysis and show that, in practice, nuclear-norm minimization accurately fills in the many missing entries of large low-rank matrices from just a few noisy samples. Some analogies between matrix completion and compressed sensing are discussed throughout.