Robust principal component analysis? Recovering low-rank matrices from sparse errors

Abstract

The problem of recovering a low-rank data matrix from corrupted observations arises in many application areas, including computer vision, system identification, and bioinformatics. Recently it was shown that low-rank matrices satisfying an appropriate incoherence condition can be exactly recovered from non-vanishing fractions of errors by solving a simple convex program, Principal Component Pursuit, which minimizes a weighted combination of the nuclear norm and the ℓ1 norm of the corruption [1]. Our methodology and results suggest a principled approach to robust principal component analysis, since they show that one can efficiently and exactly recover the principal components of a low-rank data matrix even when a positive fraction of the entries are corrupted. These results extend to the case where a fraction of entries are missing as well. © 2010 IEEE.