Low-rank Matrix Recovery from Errors and Erasures

Low-rank matrices play a central role in large-scale data analysis and dimensionality reduction. They arise in a variety of application areas, among them Principal Component Analysis (PCA), Multidimensional scaling (MDS), Spectral Clustering and related methods, ranking and collaborative filtering, etc. In all these problems, low-rank structure is used to either approximate a general matrix, or to correct for corrupted or missing data. This paper considers the recovery of a low-rank matrix in the simultaneous presence of (a) erasures: most elements are not observed, and (b): errors: among the ones that are observed, a significant fraction at unknown locations are grossly/maliciously corrupted. It is now well recognized that the standard, popular approach to low-rank matrix recovery using SVD as a first step fails spectacularly in this setting [1]. Low-rank matrix completion, which considers only random erasures ([2], [3]) will also fail with even just a few maliciously corrupted entries. In light of this, several recent works have studied an alternate approach based on the natural convex relaxation of minimizing rank plus support. One approach [4], [5] provides deterministic/worst case guarantees for the fully observed setting (i.e.