Robust PCA via Outlier Pursuit

Abstract

Singular Value Decomposition (and Principal Component Analysis) 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 we call Outlier Pursuit, that 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 and 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, that allows the treatment of such problems.

26 pages, appeared in NIPS 2010. v2 has typos corrected, some re-writing. results essentially unchanged

References in corpus (1)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

Cited by in corpus (52)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Anomaly Detection using One-Class Neural Networks
• Generative Probabilistic Novelty Detection with Adversarial Autoencoders
• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• Robust PCA as Bilinear Decomposition with Outlier-Sparsity Regularization
• Recovery of Low-Rank Plus Compressed Sparse Matrices with Application to Unveiling Traffic Anomalies
• A Novel M-Estimator for Robust PCA
• Near-Optimal Joint Object Matching via Convex Relaxation
• Exact Subspace Segmentation and Outlier Detection by Low-Rank Representation
• Joint Tensor Factorization and Outlying Slab Suppression with Applications
• Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• A Simple and Fast Algorithm for L1-norm Kernel PCA
• Beyond Low Rank + Sparse: Multi-scale Low Rank Matrix Decomposition
• Inspect, Understand, Overcome: A Survey of Practical Methods for AI Safety
• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• Anomaly Detection based on Zero-Shot Outlier Synthesis and Hierarchical Feature Distillation
• Robust PCA in High-dimension: A Deterministic Approach
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Recovery of Coherent Data via Low-Rank Dictionary Pursuit
• lp-Recovery of the Most Significant Subspace among Multiple Subspaces with Outliers
• Community Recovery in Graphs with Locality
• Evolutionary Self-Expressive Models for Subspace Clustering
• Puzzle-AE: Novelty Detection in Images through Solving Puzzles
• A Dictionary-Based Generalization of Robust PCA Part II: Applications to Hyperspectral Demixing
• A Dictionary-Based Generalization of Robust PCA with Applications to Target Localization in Hyperspectral Imaging
• Denoising-based Turbo Message Passing for Compressed Video Background Subtraction
• Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search
• Low Rank Matrix Recovery with Simultaneous Presence of Outliers and Sparse Corruption
• A Dictionary Based Generalization of Robust PCA
• Target-based Hyperspectral Demixing via Generalized Robust PCA
• Robust Tensor Recovery with Fiber Outliers for Traffic Events
• Matrix Normal PCA for Interpretable Dimension Reduction and Graphical Noise Modeling
• Correlation-aware Deep Generative Model for Unsupervised Anomaly Detection
• Structured Low-Rank Matrix Factorization with Missing and Grossly Corrupted Observations
• Deep Dual Support Vector Data Description for Anomaly Detection on Attributed Networks
• Robust and Scalable Column/Row Sampling from Corrupted Big Data
• Outlier Detection and Data Clustering via Innovation Search
• Learning Competitive and Discriminative Reconstructions for Anomaly Detection
• Extracting Entities and Topics from News and Connecting Criminal Records
• A Bias Trick for Centered Robust Principal Component Analysis
• Outlier-robust sparse/low-rank least-squares regression and robust matrix completion
• Robust Multi-subspace Analysis Using Novel Column L0-norm Constrained Matrix Factorization
• Robust subspace recovery by Tyler's M-estimator
• Hierarchical Probabilistic Model for Blind Source Separation via Legendre Transformation
• Solving the Robust Matrix Completion Problem via a System of Nonlinear Equations
• Generalized One-Class Learning Using Pairs of Complementary Classifiers
• Online Variational Bayesian Subspace Filtering with Applications
• Detecting Anomalies Through Contrast in Heterogeneous Data
• Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants
• Plug-and-Play Anomaly Detection with Expectation Maximization Filtering
• Modal Principal Component Analysis