Stable Principal Component Pursuit
By Zihan Zhou, Xiaodong Li, John Wright, E.J. Candes, Yi Ma. 2010
595 citations recorded by the source corpus.
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 entry-wise 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.
Subfields: Acoustics and Ultrasonics, Computational Mechanics, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Acoustics and Ultrasonics
- Trac Duy Tran
- Nam H. Nguyen
- Thierry Bouwmans
- Sahand N. Negahban
- Purushottam Kar
- Prateek Jain
- Kush Bhatia
In Computational Mechanics
- Martin J. Wainwright
- Thierry Bouwmans
- Sahand N. Negahban
- Michael I. Jordan
- Francis R. Bach
- Trac Duy Tran
- Pradeep Ravikumar
- Vassilis Kalofolias
In Signal Processing
- Thierry Bouwmans
- Vassilis Kalofolias
- Pradeep Ravikumar
- Bin Yu
- Xavier Bresson
- Michael M. Bronstein
- Sahand N. Negahban
- Trac Duy Tran
Citations in the corpus
- Principal Components and Regularized Estimation of Factor Models (2017, background): “ on the singular vectors of L prevents the low rank component from being too sparse. The cardinality condition requires the support of S to be selected uniformly at random so that S is not low rank.8 Zhou et al. (2010) allows for the presence of small noise W. With 7See Delvin et al. (1981), Li and ”
- Parallel Direction Method of Multipliers (2014, background): “Further, in the stable version of RPCA [29], an noisy matrix Z is taken into consideration, and the linear constraint has three blocks, i.”
- On the linear convergence of the alternating direction method of multipliers (2012, unknown): “In this case, the stable robust PCA problem is again in the form of (1.1).”
- Robust Principal Component Analysis on Graphs (2015, background): “Extensions of this model for inexact recovery [25] and outlier pursuit [22] have been proposed.”
- RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images (2010, background): “It has been shown in [22] that sparse and low-rank matrix decomposition (without transformations) by convex optimization is stable to additive Gaussian noise of small magnitude, in addition to sparse errors.”
- Sparse Bayesian Methods for Low-Rank Matrix Estimation (2011, background): “In both cases, most matrices can be recovered by solving the affine rank minimization problem1 [1]–[4]”
- Moving Object Detection by Detecting Contiguous Outliers in the Low-Rank Representation (2011, methodology): “In all our experiments, we let K = √ n , and γ = β and 5 β for simulation and real sequences, respectively.”
- Traditional and recent approaches in background modeling for foreground detection: An overview (2014, background): “[328] proposed a stable PCP (SPCP) that guarantees stable and accurate recovery in the presence of entrywise noise.”
- Exploring patterns enriched in a dataset with contrastive principal component analysis (2018, background): “For example, multi-dimensional scaling (MDS) 4 fi nds a low-dimensional embedding that preserves the distance in the high-dimensional space; principal component pursuit 17 fi nds a low-rank subspace that is robust to small entry-wise noise and gross sparse errors.”
- SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group (2016, methodology): “ nonlinear estimation, this class of problems enjoys a beautiful geometric structure [28] that has already been shown to enable remarkably robust recovery, even in the presence of gross contamination [24,87]. We intend to investigate this possibility in future research. Finally, while the specic rel”
- Infrared Patch-Image Model for Small Target Detection in a Single Image (2013, background): “It has been shown in [13] that under the same conditions as PCP (8), B and T can be stably estimated when (cid”
- Multidimensional simultaneous random plus erratic noise attenuation and interpolation for seismic data by joint low-rank and sparse inversion (2015, methodology): “Those works include strong theoretical results under various conditions on the matrix structure (for instance, one cannot expect to separate matrices that are low rank and sparse) and have been extended to cases in which available data are limited and/or contaminated with random noise (Zhou et al., ”
- Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, methodology): “5) l∞-norm [22] SPCP SPCP Temporal Coherence Frobenius norm [468] Equality (||A − L − S − E||F = 0) Weighting matrix W : Inequality (||A− L − S||F < δ) + Frobenius norm [282] on E 1) Dense Optical Flow (RMC) [419][434]”
- Hyperspectral Image Restoration Using Low-Rank Matrix Recovery (2014, methodology): “In Section IV, both the simulated experiment and real data experiments are described and analyzed, followed by the conclusions in Section V.”
- GoDec: Randomized Lowrank & Sparse Matrix Decomposition in Noisy Case (2011, background): “Stable principal component pursuit (Zhou et al., 2010) is an extension of RPCA to handle noise by minimizing the nuclear norm and l1 norm.”
- Divide-and-Conquer Matrix Factorization (2011, background): “The derived properties will aid us in deriving DFC estimation guarantees.”
- A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers (2009, background): “, [1, 17, 18, 26, 41, 76]) has studied matrix problems involving the sum of a low-rank matrix with a sparse matrix, along with the regularizer formed by a weighted sum of the nuclear norm and the elementwise 1-norm.”