  Suppose a given observation matrix can be decomposed as the sum of a low-rank
matrix and a sparse matrix (outliers), and the goal is to recover these
individual components from the observed sum. Such additive decompositions have
applications in a variety of numerical problems including system
identification, latent variable graphical modeling, and principal components
analysis. We study conditions under which recovering such a decomposition is
possible via a combination of $\ell_1$ norm and trace norm minimization. We are
specifically interested in the question of how many outliers are allowed so
that convex programming can still achieve accurate recovery, and we obtain
stronger recovery guarantees than previous studies. Moreover, we do not assume
that the spatial pattern of outliers is random, which stands in contrast to
related analyses under such assumptions via matrix completion.
