  Singular Value Decomposition (and Principal Component Analysis) is one of the
most widely used techniques for dimensionality reduction: successful and
efficiently computable, it is nevertheless plagued by a well-known,
well-documented sensitivity to outliers. Recent work has considered the setting
where each point has a few arbitrarily corrupted components. Yet, in
applications of SVD or PCA such as robust collaborative filtering or
bioinformatics, malicious agents, defective genes, or simply corrupted or
contaminated experiments may effectively yield entire points that are
completely corrupted.
  We present an efficient convex optimization-based algorithm we call Outlier
Pursuit, that under some mild assumptions on the uncorrupted points (satisfied,
e.g., by the standard generative assumption in PCA problems) recovers the exact
optimal low-dimensional subspace, and identifies the corrupted points. Such
identification of corrupted points that do not conform to the low-dimensional
approximation, is of paramount interest in bioinformatics and financial
applications, and beyond. Our techniques involve matrix decomposition using
nuclear norm minimization, however, our results, setup, and approach,
necessarily differ considerably from the existing line of work in matrix
completion and matrix decomposition, since we develop an approach to recover
the correct column space of the uncorrupted matrix, rather than the exact
matrix itself. In any problem where one seeks to recover a structure rather
than the exact initial matrices, techniques developed thus far relying on
certificates of optimality, will fail. We present an important extension of
these methods, that allows the treatment of such problems.
