Robust PCA via Outlier Pursuit

By Huan Xu, Constantine Caramanis, Sujay Sanghavi. IEEE Transactions on Information Theory, 2010

788 citations recorded by the source corpus.

Singular-value decomposition (SVD) [and principal component analysis (PCA)] is one of the most widely used techniques for dimensionality reduction: successful and efficiently computable, it is nevertheless plagued by a well-known, well-documented sensitivity to outliers. Recent work has considered the setting where each point has a few arbitrarily corrupted components. Yet, in applications of SVD or PCA, such as robust collaborative filtering or bioinformatics, malicious agents, defective genes, or simply corrupted or contaminated experiments may effectively yield entire points that are completely corrupted. We present an efficient convex optimization-based algorithm that we call outlier pursuit, which under some mild assumptions on the uncorrupted points (satisfied, e.g., by the standard generative assumption in PCA problems) recovers the exact optimal low-dimensional subspace and identifies the corrupted points. Such identification of corrupted points that do not conform to the low-dimensional approximation is of paramount interest in bioinformatics, financial applications, and beyond. Our techniques involve matrix decomposition using nuclear norm minimization; however, our results, setup, and approach necessarily differ considerably from the existing line of work in matrix completion and matrix decomposition, since we develop an approach to recover the correct column space of the uncorrupted matrix, rather than the exact matrix itself. In any problem where one seeks to recover a structure rather than the exact initial matrices, techniques developed thus far relying on certificates of optimality will fail. We present an important extension of these methods, which allows the treatment of such problems.

Subfields: Artificial Intelligence, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/01625cba9f8a783994377d4f35aa765242faab4f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Signal Processing

Citations in the corpus

Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery (2017, background): “This was called “outlier pursuit” in [58] and solves min ˜ L , ˜ S ˜ L ∗ + λ (cid:107) ˜ S C 2 , 1 subject to M = ˜ L + ˜ S C Here (cid:107) ˜ S 2 , 1 is the l 1 norm of the vector of column-wise l 2 norms.”
Dual Principal Component Pursuit (2015, methodology): “Keywords: Outliers, Robust Principal Component Analysis, High Relative Dimension, `1 Minimization, Non-Convex Optimization, Linear Programming, Trifocal Tensor”
Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions (2011, methodology): “Different forms of robust PCA can be formulated in terms of matrix decomposition using the matrix to model the gross errors [7, 9, 21].”
Exact Recoverability From Dense Corrupted Observations via $\ell _{1}$-Minimization (2011, methodology): “Recently, Cand`es et al. [13], [34], Chandrasekaran et al. [35], Xu et al. [36] and Agarwal et al. [37] have shown that one can exactly recover a low-rank matrix L ∈ R n 1 × n 2 from its grossly corrupted entries M = L + S by solving the following convex program: More speciﬁcally, the authors of…”
Fast global convergence rates of gradient methods for high-dimensional statistical recovery (2010, background): “[40, 13, 44, 26, 7]), second-order cone programs (SOCP) for the group Lasso (e.”
Adversarially Learned One-Class Classifier for Novelty Detection (2018, methodology): “periment, similar setup as in [ 50] is used, and we compare our method with [ ] and 6 other methods designed speciﬁcally for detecting outliers, including Coherence Pursuit (CoP) [32], OutlierPursuit [48], REAPER [22], Dual Principal Component Pursuit (DPCP) [43], Low-Rank Representation (LRR) [24],”
Robust Computation of Linear Models by Convex Relaxation (2012, methodology): “Indeed, our limited numerical experiments indicate that reaper tends to be significantly faster than the ADMM implementation of [77,78] and [56].”
Robust matrix completion (2014, background): “For example, Xu et al [26] showed that a very popular matrix completion procedure using nuclear norm minimization can fail dramatically even if S0 contains only a single nonzero column.”
Being Robust (in High Dimensions) Can Be Practical (2017, methodology): “There have also been semidefinite programming methods proposed for robust principal component analysis with outliers (Xu et al., 2010).”
On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation (2015, neutral): “es some additional conditions (e.g., the non-zero entries of the sparse noise are not too numerous and appear randomly among the entries of M), solving (1.5) guarantees to recover the sought solution [8, 7, 40]. This model has attracted a lot attention lately, both for its theoretical, algorithmic a”
Online Robust PCA via Stochastic Optimization (2013, methodology): “Different from the setting of samples being corrupted by sparse noise, [25, 24] and [7] solve robust PCA in the case that a few samples are completely corrupted.”
Robust Matrix Completion and Corrupted Columns (2011, background): “If ρ = 1, we partially recovers the result in (Xu et al., 2010c).”
Robust Anomaly Detection and Backdoor Attack Detection Via Differential Privacy (2019, methodology): “Traditional methods such as clustering ([30]) and principal component analysis (PCA) ([31, 32]) have been frequently used.”
Anomaly Detection using One-Class Neural Networks (2018, methodology): “– Robust-PCA OC-SVM as per formulation in [30, 39], hybrid model wherein robust PCA features are used to train OC-SVM.”
Robust High Dimensional Sparse Regression and Matching Pursuit (2013, background): “More generally, even beyond regression, in, e.g., robust PCA and robust matrix completion [7], [5], [34], [11], [21], recent robust recovery in high dimensions results have for the most part depended on convex optimization formulations.”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, methodology): “…al. (2011) [22] Block based PCP Tang and Nehorai (2011) [365] Local PCP Wohlberg et al. (2012) [399] Outlier Pursuit OP Xu et al. (2010) [410] SOP Xu et al. (2010) [410] Sparsity Control SpaCtrl Mateos et al. (2010) [258] SpaCorr Hsu et al. (2011) [155] Non Convex Heuristic Recovery lp HR (pHR)…”
HRN: A Holistic Approach to One Class Learning (2020, background): “Early work in statistics [4] was mainly based on probabilistic modeling of the distribution of the normal data and regard data points with low probabilities in the distribution as anomalies [4, 87, 22, 86].”