Paper Info
Title
Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization.
Abstract
Principal component analysis 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 error entries E 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. 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 analysis 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.
Year
Venue
Field
2009
NIPS
Mathematical optimization,Matrix (mathematics),Computer science,Robustness (computer science),Robust principal component analysis,Curse of dimensionality,Low-rank approximation,Artificial intelligence,Logarithm,Convex optimization,Principal component analysis,Machine learning
DocType
Citations 
PageRank 
Conference
82
3.97
References 
Authors
7
5
Name
Order
Citations
PageRank
John Wright121719.34
Arvind Ganesh24904153.80
Rao, Shankar3823.97
YiGang Peng445114.87
Yi Ma514931536.21