matrix Completion with Noise

From statwiki
Revision as of 16:38, 18 November 2010 by Laleh Ghoraie (talk | contribs)
Jump to: navigation, search

Introduction

Nowadays, in many well-studied applications, we may face a situation that a few entries of a data matrix are observed, and our task highly depends on the accurate recovery of the original matrix. We are curious to find out if this is possible, and if yes, how accurate it can be performed.

In the current paper <ref name=""> </ref>, Candes and Plan, discuss these questions. They review the novel literature about recovery of a low-rank matrix with an almost minimal set of entries by solving a simple nuclear-norm minimization problem.

They also present results indicating that matrix completion and the original unknown matrix recovery are provably accurate even when small amount of noise is present and corrupts the few observed entries. The error of the recovery task is proportional to the noise level when the number of noisy samples is about [math]nr\log^{2}{n}[/math], in which [math]n[/math] and [math]r[/math] are the matrix dimension and rank, respectively.

Notation

Exact Matrix Completion

Stable Matrix Completion

Experiments

References

<references />