Matrix Completion With Noise

Abstract

On the heels of compressed sensing, a new field
\nhas very recently emerged. This field addresses a broad range
\nof problems of significant practical interest, namely, the
\nrecovery of a data matrix from what appears to be incomplete,
\nand perhaps even corrupted, information. In its simplest form,
\nthe problem is to recover a matrix from a small sample of its
\nentries. It comes up in many areas of science and engineering,
\nincluding collaborative filtering, machine learning, control,
\nremote sensing, and computer vision, to name a few. This
\npaper surveys the novel literature on matrix completion, which
\nshows that under some suitable conditions, one can recover an
\nunknown low-rank matrix from a nearly minimal set of entries
\nby solving a simple convex optimization problem, namely,
\nnuclear-norm minimization subject to data constraints. Further,
\nthis paper introduces novel results showing that matrix
\ncompletion is provably accurate even when the few observed
\nentries are corrupted with a small amount of noise. A typical
\nresult is that one can recover an unknown n x n matrix of low
\nrank r from just about nr log^2 n noisy samples with an error that
\nis proportional to the noise level. We present numerical results
\nthat complement our quantitative analysis and show that, in
\npractice, nuclear-norm minimization accurately fills in the
\nmany missing entries of large low-rank matrices from just a few
\nnoisy samples. Some analogies between matrix completion and
\ncompressed sensing are discussed throughout.

Keywords

Affiliated Institutions

• California Institute of Technology US

Related Publications