Reconstruction Theorem

• with more than critical number of observations nuclear-norm-minimization can recover correct matrix with high probability

Definition

Let $A\in {\mathbb{R}}^{n\times n}$ be a rank $k$ matrix that is incoherent with some $\mu \ge 1$ and for which $S$ samples have been observed at random. Then there is a universal constant $C$ such that if $S\ge C{\mu }^{2}nk(\log n{)}^6$, then with probability at least $1-n^{-3}$, $A$ fulfills: