Low-rank Matrix Recovery from Errors and Erasures

Abstract

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.

27 pages, 3 figures. Appeared in ISIT 2011

References in corpus (3)

• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
• Robust Matrix Decomposition with Outliers
• Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions

Cited by in corpus (7)

• Learning the Dependence Graph of Time Series with Latent Factors
• Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions
• Haplotype Assembly: An Information Theoretic View
• Identifying Influential Entries in a Matrix
• Greedy Approach for Low-Rank Matrix Recovery
• A Correctness Result for Online Robust PCA
• Fast greedy algorithm for subspace clustering from corrupted and incomplete data