  This paper considers the recovery of a low-rank matrix from an observed
version that simultaneously contains both (a) erasures: most entries are not
observed, and (b) errors: values at a constant fraction of (unknown) locations
are arbitrarily corrupted. We provide a new unified performance guarantee on
when the natural convex relaxation of minimizing rank plus support succeeds in
exact recovery. Our result allows for the simultaneous presence of random and
deterministic components in both the error and erasure patterns. On the one
hand, corollaries obtained by specializing this one single result in different
ways recover (up to poly-log factors) all the existing works in matrix
completion, and sparse and low-rank matrix recovery. On the other hand, our
results also provide the first guarantees for (a) recovery when we observe a
vanishing fraction of entries of a corrupted matrix, and (b) deterministic
matrix completion.
