matrix Completion with Noise

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

In this section, the notations used for the whole paper are introduced. Three matrix norms of spectral, Frobenius, and nuclear norms of matrix [math]\displaystyle{ X \in \mathbb{R}^{n1\times n2} }[/math] with singular values of [math]\displaystyle{ \{ \sigma_k \} }[/math] are used frequently, and are denoted by [math]\displaystyle{ \parallel X \parallel }[/math], [math]\displaystyle{ \parallel X \parallel_F }[/math], and [math]\displaystyle{ \parallel X \parallel_* := \Sigma_k \sigma_k }[/math], respectively.

Also, the operators for linear transformation on [math]\displaystyle{ \mathbb{R}^{n1 \times n2} }[/math] are denoted by calligraphic letters, for instance, identity operator an this space is shown by [math]\displaystyle{ \mathcal{I}: \mathbb{R}^{n1 \times n2} \to \mathbb{R}^{n1 \times n2} }[/math]

References

<references />