Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis

Abstract

This paper presents a remarkably simple, yet powerful, algorithm termed Coherence Pursuit (CoP) to robust Principal Component Analysis (PCA). As inliers lie in a low dimensional subspace and are mostly correlated, an inlier is likely to have strong mutual coherence with a large number of data points. By contrast, outliers either do not admit low dimensional structures or form small clusters. In either case, an outlier is unlikely to bear strong resemblance to a large number of data points. Given that, CoP sets an outlier apart from an inlier by comparing their coherence with the rest of the data points. The mutual coherences are computed by forming the Gram matrix of the normalized data points. Subsequently, the sought subspace is recovered from the span of the subset of the data points that exhibit strong coherence with the rest of the data. As CoP only involves one simple matrix multiplication, it is significantly faster than the state-of-the-art robust PCA algorithms. We derive analytical performance guarantees for CoP under different models for the distributions of inliers and outliers in both noise-free and noisy settings. CoP is the first robust PCA algorithm that is simultaneously non-iterative, provably robust to both unstructured and structured outliers, and can tolerate a large number of unstructured outliers.

References in corpus (22)

• A Simpler Approach to Matrix Completion
• Rank-Sparsity Incoherence for Matrix Decomposition
• A geometric analysis of subspace clustering with outliers
• Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset
• Robust PCA via Outlier Pursuit
• Fast Algorithms for Robust PCA via Gradient Descent
• Non-convex Robust PCA
• A Novel M-Estimator for Robust PCA
• Two Proposals for Robust PCA using Semidefinite Programming
• Statistical Compressed Sensing of Gaussian Mixture Models
• Robust computation of linear models by convex relaxation
• High Dimensional Low Rank plus Sparse Matrix Decomposition
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Greedy Subspace Clustering
• Innovation Pursuit: A New Approach to Subspace Clustering
• Robust recovery of multiple subspaces by geometric l_p minimization
• Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
• Fast, Robust and Non-convex Subspace Recovery
• Principal Component Analysis with Contaminated Data: The High Dimensional Case
• Algorithms and Hardness for Robust Subspace Recovery
• lp-Recovery of the Most Significant Subspace among Multiple Subspaces with Outliers
• Robust Subspace Clustering via Thresholding

Cited by in corpus (31)

• Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset
• Generative Probabilistic Novelty Detection with Adversarial Autoencoders
• An Overview of Robust Subspace Recovery
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Innovation Pursuit: A New Approach to Subspace Clustering
• Inspect, Understand, Overcome: A Survey of Practical Methods for AI Safety
• Subspace-Orbit Randomized Decomposition for Low-rank Matrix Approximation
• Attribute Restoration Framework for Anomaly Detection
• Anomaly Detection based on Zero-Shot Outlier Synthesis and Hierarchical Feature Distillation
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Structured and Unstructured Outlier Identification for Robust PCA: A Non iterative, Parameter free Algorithm
• Subspace clustering without knowing the number of clusters: A parameter free approach
• Robust Tensor Decomposition for Image Representation Based on Generalized Correntropy
• Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search
• Low Rank Matrix Recovery with Simultaneous Presence of Outliers and Sparse Corruption
• Subspace Clustering using Ensembles of $K$-Subspaces
• ESAD: End-to-end Deep Semi-supervised Anomaly Detection
• A robust principal component analysis for outlier identification in messy microcalorimeter data
• Dual Principal Component Pursuit
• Person Re-identification Using Visual Attention
• To Trust or to Stockpile: Modeling Human-Simulation Interaction in Supply Chain Shortages
• Robust and Scalable Column/Row Sampling from Corrupted Big Data
• Dual Principal Component Pursuit: Probability Analysis and Efficient Algorithms
• Outlier Detection and Data Clustering via Innovation Search
• Learning Competitive and Discriminative Reconstructions for Anomaly Detection
• Fast, Parameter free Outlier Identification for Robust PCA
• A Bias Trick for Centered Robust Principal Component Analysis
• Study of Compressed Randomized UTV Decompositions for Low-Rank Matrix Approximations in Data Science
• Compressed Randomized UTV Decompositions for Low-Rank Approximations and Big Data Applications
• Deep Unsupervised Image Anomaly Detection: An Information Theoretic Framework
• Provable Data Clustering via Innovation Search