Principal Component Analysis (PCA) is the problem of finding a low-rank approximation to a matrix. It is a central problem in statistics, but it is sensitive to sparse errors with large magnitudes. Robust PCA addresses this problem by decomposing a matrix into the sum of a low-rank matrix and a sparse matrix, thereby separating out the sparse errors. This paper provides a background in robust PCA and investigates the conditions under which an optimization problem, Principal Component Pursuit (PCP), solves the robust PCA problem. Before introducing robust PCA, we discuss a related problem, sparse signal recovery (SSR), the problem of finding the sparsest solution to an underdetermined system of linear equations. The concepts used to solve SSR are analogous to the concepts used to solve robust PCA, so presenting the SSR problem gives insight into robust PCA. After analyzing robust PCA, we present the results of numerical experiments that test whether PCP can solve the robust PCA problem even if previously proven sufficient conditions are violated.

Author Bio

Michael Hornstein recently received a B.S. in Mathematical and Computational Science from Stanford University, and is currently a master's student at the Stanford Institute for Computational and Mathematical Engineering. He wrote this paper for the Vertical Integration of Research and Education program (VIGRE) in the Stanford Statistics Department during the summer of 2010. His advisor was Prof. Deanna Needell, now at Claremont McKenna College. To obtain the code used in the numerical experiments, you can email him.