Robust Principal Component Analysis?

Abstract

This paper is about a curious phenomenon. Suppose we have a data matrix, which is the superposition 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 called Principal Component Pursuit; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the L1 norm. 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 arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and 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, where it offers a principled way of removing shadows and specularities in images of faces.

Cited by in corpus (24)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Tensor-based formulation and nuclear norm regularization for multi-energy computed tomography
• Nonlinear hyperspectral unmixing with robust nonnegative matrix factorization
• A convex model for non-negative matrix factorization and dimensionality reduction on physical space
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Estimation of Simultaneously Sparse and Low Rank Matrices
• Convex Tensor Decomposition via Structured Schatten Norm Regularization
• Note on sampling without replacing from a finite collection of matrices
• Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion
• The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
• Learning the Dependence Graph of Time Series with Latent Factors
• An Iterative Method for Unsupervised Robust Anomaly Detection Under Data Contamination
• Covariance Eigenvector Sparsity for Compression and Denoising
• Robust PCA in High-dimension: A Deterministic Approach
• Detecting Overlapping Temporal Community Structure in Time-Evolving Networks
• The model of an anomaly detector for HiLumi LHC magnets based on Recurrent Neural Networks and adaptive quantization
• Corruption Robust Phase Retrieval via Linear Programming
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Estimation with Low-Rank Time-Frequency Synthesis Models
• Matrix ALPS: Accelerated Low Rank and Sparse Matrix Reconstruction
• High-Dimensional Covariance Decomposition into Sparse Markov and Independence Models
• High-Dimensional Covariance Decomposition into Sparse Markov and Independence Domains
• Temporally Coherent Bayesian Models for Entity Discovery in Videos by Tracklet Clustering
• Principal Component Analysis: A Generalized Gini Approach