matrix Completion with Noise: Difference between revisions
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
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. | 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, 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. | 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. | 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== | ||
Revision as of 16:38, 18 November 2010
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]\displaystyle{ nr\log^{2}{n} }[/math], in which [math]\displaystyle{ n }[/math] and [math]\displaystyle{ r }[/math] are the matrix dimension and rank, respectively.
Notation
Exact Matrix Completion
Stable Matrix Completion
Experiments
References
<references />