Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

TLDR

Principal component analysis is widely used in data analysis but lacks robustness to outliers. This work addresses robust PCA by aiming to recover a low‑rank matrix from grossly corrupted, sparse observations. The authors formulate the problem as a convex optimization that jointly estimates the low‑rank matrix and sparse errors, and provide a fast, provably convergent algorithm. They prove that most low‑rank matrices can be exactly recovered under proportional growth of rank and error sparsity, and validate the theory with simulations and real data, indicating usefulness in computer vision.

Abstract

Principal component is a fundamental operation in computational data analysis, with myriad applications ranging from web search to bioinformatics to computer vision and image analysis. However, its performance and applicability in real scenarios are limited by a lack of robustness to outlying or corrupted observations. This paper considers the idealized robust principal component analysis problem of recovering a low rank matrix A from corrupted observations D = A + E. Here, the corrupted entries E are unknown and the errors can be arbitrarily large (modeling grossly corrupted observations common in visual and bioinformatic data), but are assumed to be sparse. We prove that most matrices A can be efficiently and exactly recovered from most error sign-and-support patterns by solving a simple convex program, for which we give a fast and provably convergent algorithm. Our result holds even when the rank of A grows nearly proportionally (up to a logarithmic factor) to the dimensionality of the observation space and the number of errors E grows in proportion to the total number of entries in the matrix. A by-product of our is the first proportional growth results for the related problem of completing a low-rank matrix from a small fraction of its entries. Simulations and real-data examples corroborate the theoretical results, and suggest potential applications in computer vision.