  This paper considers the problem of recovery of a low-rank matrix in the
situation when most of its entries are not observed and a fraction of observed
entries are corrupted. The observations are noisy realizations of the sum of a
low rank matrix, which we wish to recover, with a second matrix having a
complementary sparse structure such as element-wise or column-wise sparsity. We
analyze a class of estimators obtained by solving a constrained convex
optimization problem that combines the nuclear norm and a convex relaxation for
a sparse constraint. Our results are obtained for the simultaneous presence of
random and deterministic patterns in the sampling scheme. We provide guarantees
for recovery of low-rank and sparse components from partial and corrupted
observations in the presence of noise and show that the obtained rates of
convergence are minimax optimal.
