Robust principal component analysis?
By E.J. Candes, Xiaodong Li, Yi Ma, John Wright. 2009
7,452 citations recorded by the source corpus.
This article 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 ℓ1 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.
Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Applied Mathematics
- Martin J. Wainwright
- Stanislav Minsker
- Yudong Chen
- Prateek Jain
- Constantine Caramanis
- E.J. Candes
- Thierry Bouwmans
- Sujay Sanghavi
In Computational Mechanics
- Wotao Yin
- Martin J. Wainwright
- Lei Zhang
- E.J. Candes
- Zhouchen Lin
- René Vidal
- Prateek Jain
- Francis R. Bach
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Ming-Hsuan Yang
- Xiaogang Wang
- Trevor Darrell
- Yi Yang
- Jitendra Malik
- Chunhua Shen
Citations in the corpus
- Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning (2017, methodology): “Such statistical robust learning algorithms have been proposed for several traditional machine learning models such as linear and logistic regressions [14], [18], [27], [16], [39], [61].”
- Robust Estimators in High Dimensions without the Computational Intractability (2016, neutral): “But when the covariance is also unknown, their algorithm estimates the mean and covariance to within error O( √ ε‖Σ‖2 log d) and O( √ ε log d‖Σ‖2), measured in 2 norm and Frobenius norm respectively.”
- Agnostic Estimation of Mean and Covariance (2016, methodology): “Assumptions about rank and sparsity are made in a technique that is now called Robust PCA [CSPW11, CLMW11].”
- Learning from untrusted data (2016, methodology): “The analogue to the optimization (3) is regularized empirical risk minimization: ŵ = arg min w ∈H n∑ i=1 fi (w ) + λh(w ), (7) where h(w ) is a non-negative regularizer.”
- Distributed Robust Learning (2014, background): “Examples include time series data, Markov chain data [1], and images/videos data where spatial correlation is common [3].”
- Geometric median and robust estimation in Banach spaces (2013, background): “For instance, if part of the observations is contained in a low-dimensional subspace while the rest are corrupted by noise, the low-dimensional subspace can often be recovered exactly, see [9,48] and references therein.”
- Being Robust (in High Dimensions) Can Be Practical (2017, background): “Some of these works can tolerate a constant fraction of corruptions (Candès et al., 2011), however require that the locations of the corruptions are evenly spread throughout the dataset so that no individual sample is entirely corrupted.”
- Robust Lasso With Missing and Grossly Corrupted Observations (2011, background): “Another recent line of research on recovering the data from grossly corrupted measurements has been also studied in the context of robust principal component analysis (RPCA) [3] [20] [1].”
- Bayesian group factor analysis with structured sparsity (2016, methodology): “The BASS model moreover allows sparse and dense factor loadings, which proved essential for real data scenarios that have this structure and has been pursued in classical statistics (Chandrasekaran et al., 2009; Candès et al., 2011; Zhou et al., 2011).”
- Interventional Few-Shot Learning (2020, background): “2) X → C: features can be represented using (or projected onto) the manifold base linearly [60, 9] or nonlinearly [6].”
- Adaptive Spatiotemporal SVD Clutter Filtering for Ultrafast Doppler Imaging Using Similarity of Spatial Singular Vectors (2018, methodology): “replacing the whole subset of the biggest singular values by zeros) was chosen under the assumption that tissue and blood signals are described by orthogonal singular vectors subspaces, but Candès et al [16] and [17], and Otazo et al.”
- Robust High-Dimensional Linear Regression (2016, background): “Our goal is to make regression which uses dimensionality reduction, such as PCA, robust to adversarial manipulation.”
- Proximal Markov chain Monte Carlo algorithms (2013, methodology): “…we present our analysis in the context of matrix denoising, however the approach can be easily applied to other low-rank matrix estimation problems such as matrix completion and decomposition (Candès and Plan 2009; Candès and Tao 2009; Chandrasekaran et al. 2011, 2012; Candès et al. 2011).”
- On the Compressive Spectral Method (2014, background): “L(1) optimization and its related models are at the center of many problems in the fields of imaging science and data analysis; see, for example, [2, 17, 18, 16].”
- Singing-voice separation from monaural recordings using robust principal component analysis (2012, methodology): “We also examined the parameter λk in RPCA and the gain factor with a binary mask in detail.”
- Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements (2011, methodology): “(We include face recognition in our discussion to illustrate the different uses of the low-rank matrix model.) However, there is another nuclear-norm based minimization approach, specialized to deal with sparse errors, with strong guarantees for this model [ 10 ].”