  We improve existing results in the field of compressed sensing and matrix
completion when sampled data may be grossly corrupted. We introduce three new
theorems. 1) In compressed sensing, we show that if the m \times n sensing
matrix has independent Gaussian entries, then one can recover a sparse signal x
exactly by tractable \ell1 minimimization even if a positive fraction of the
measurements are arbitrarily corrupted, provided the number of nonzero entries
in x is O(m/(log(n/m) + 1)). 2) In the very general sensing model introduced in
"A probabilistic and RIPless theory of compressed sensing" by Candes and Plan,
and assuming a positive fraction of corrupted measurements, exact recovery
still holds if the signal now has O(m/(log^2 n)) nonzero entries. 3) Finally,
we prove that one can recover an n \times n low-rank matrix from m corrupted
sampled entries by tractable optimization provided the rank is on the order of
O(m/(n log^2 n)); again, this holds when there is a positive fraction of
corrupted samples.
