Robust Principal Component Analysis?

• Activity Number: 106
• Type: Invited
• Date/Time: Monday, August 2, 2010 : 8:30 AM to 10:20 AM
• Sponsor: International Association for Statistical Computing
• Author(s): Emmanuel Candes*+ and Xiaodong Li and Yi Ma and John Wright
• Companies: Stanford University and Stanford University and Microsoft Research Asia and Microsoft Research Asia
• Keywords: Sparsity ; Higher criticism ; Random matrices ; Likelihood ratios

Abstract

This talk is about a curious phenomenon. Suppose we have a data matrix, which is the sum of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are corrupted. This extends to the situation where a fraction of the entries are missing as well. We present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition.