Robust principal component analysis?

The paper studies a decomposition problem: given a data matrix that is the superposition of a low-rank component and a sparse component, can each component be recovered individually? The authors prove that under suitable assumptions the answer is yes, and that both components can be recovered exactly by solving a convenient convex program they call Principal Component Pursuit, which among all feasible decompositions simply minimizes a weighted combination of the nuclear norm and the l1 norm.

This result establishes a principled approach to robust principal component analysis, showing that the principal components of a data matrix can be recovered even when a positive fraction of its entries are arbitrarily corrupted, and the guarantee extends to the case where some entries are missing. The authors discuss an algorithm for solving the optimization and demonstrate applications in video surveillance, where the method detects objects against a cluttered background, and in face recognition, where it removes shadows and specularities from face images.