Stable Principal Component Pursuit

Abstract

In this paper, we study the problem of recovering a low-rank matrix (the principal components) from a high-dimensional data matrix despite both small entry-wise noise and gross sparse errors. Recently, it has been shown that a convex program, named Principal Component Pursuit (PCP), can recover the low-rank matrix when the data matrix is corrupted by gross sparse errors. We further prove that the solution to a related convex program (a relaxed PCP) gives an estimate of the low-rank matrix that is simultaneously stable to small entrywise noise and robust to gross sparse errors. More precisely, our result shows that the proposed convex program recovers the low-rank matrix even though a positive fraction of its entries are arbitrarily corrupted, with an error bound proportional to the noise level. We present simulation results to support our result and demonstrate that the new convex program accurately recovers the principal components (the low-rank matrix) under quite broad conditions. To our knowledge, this is the first result that shows the classical Principal Component Analysis (PCA), optimal for small i.i.d. noise, can be made robust to gross sparse errors; or the first that shows the newly proposed PCP can be made stable to small entry-wise perturbations.

5-page paper submitted to ISIT 2010

References in corpus (2)

• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Matrix Completion With Noise

Cited by in corpus (30)

• Low-Rank Structure Learning via Log-Sum Heuristic Recovery
• Principal Component Analysis with Contaminated Data: The High Dimensional Case
• Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications
• Matrix Completion with Noisy Entries and Outliers
• Structured and Unstructured Outlier Identification for Robust PCA: A Non iterative, Parameter free Algorithm
• Convergence of multi-block Bregman ADMM for nonconvex composite problems
• Principal Components and Regularized Estimation of Factor Models
• Exact recoverability from dense corrupted observations via $L_1$ minimization
• Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems
• Learning Robust Low-Rank Representations
• Online (and Offline) Robust PCA: Novel Algorithms and Performance Guarantees
• Robust Cost-Sensitive Learning for Recommendation with Implicit Feedback
• Low-Rank Modeling and Its Applications in Image Analysis
• Robust Reduced Rank Regression
• Moving Object Detection by Detecting Contiguous Outliers in the Low-Rank Representation
• An Improved Traffic Matrix Decomposition Method with Frequency-Domain Regularization
• An LS-Decomposition Approach for Robust Data Recovery in Wireless Sensor Networks
• Side Information for Face Completion: a Robust PCA Approach
• A Tensor Completion Approach for Efficient and Robust Fingerprint-based Indoor Localization
• Fast, Parameter free Outlier Identification for Robust PCA
• Structural Analysis of Network Traffic Matrix via Relaxed Principal Component Pursuit
• Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants
• Target And Background Separation in Hyperspectral Imagery for Automatic Target Detection
• A Scalable Frank-Wolfe based Augmented Lagrangian Method for Linearly Constrained Composite Convex Programming
• Fast and Robust Fixed-Rank Matrix Recovery
• Atomic Norm Denoising-Based Joint Channel Estimation and Faulty Antenna Detection for Massive MIMO
• Robust Orthogonal Complement Principal Component Analysis
• Online Optimization for Large-Scale Max-Norm Regularization
• A Robust Compressive Quantum State Tomography Algorithm Using ADMM
• Baselining Network-Wide Traffic by Time-Frequency Constrained Stable Principal Component Pursuit