Matrix Completion with Noise via Leveraged Sampling
  Many matrix completion methods assume that the data follows the uniform
distribution. To address the limitation of this assumption, Chen et al.
\cite{Chen20152999} propose to recover the matrix where the data follows the
specific biased distribution. Unfortunately, in most real-world applications,
the recovery of a data matrix appears to be incomplete, and perhaps even
corrupted information. This paper considers the recovery of a low-rank matrix,
where some observed entries are sampled in a \emph{biased distribution}
suitably dependent on \emph{leverage scores} of a matrix, and some observed
entries are uniformly corrupted. Our theoretical findings show that we can
provably recover an unknown $n\times n$ matrix of rank $r$ from just about
$O(nr\log^2 n)$ entries even when the few observed entries are corrupted with a
small amount of noisy information. Empirical studies verify our theoretical
results.
