Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2010 | Published
Journal Article Open

Matrix Completion With Noise

Abstract

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.

Additional Information

© 2010 IEEE. Manuscript received March 18, 2009; accepted October 17, 2009. Date of publication April 26, 2010; date of current version May 19, 2010. The work of E. J. Candes was supported by the U.S. Office of Naval Research under grants N00014-09-1-0469 and N00014-08-1-0749 and by the National Science Foundation under a Waterman Award. E. J. Candes would like to thank T. Tao and S. Becker for some very helpful discussions.

Attached Files

Published - Candes2010p10178P_Ieee.pdf

Files

Candes2010p10178P_Ieee.pdf
Files (435.6 kB)
Name Size Download all
md5:d63e7e73b76566c970906e34c1fd82c7
435.6 kB Preview Download

Additional details

Created:
August 21, 2023
Modified:
October 20, 2023