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 (6)

• Robust PCA via Outlier Pursuit
• Fast Algorithms for Robust PCA via Gradient Descent
• Non-convex Robust PCA
• Greedy Subspace Clustering
• Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
• Principal Component Analysis with Contaminated Data: The High Dimensional Case

Cited by in corpus (27)

• Generative Probabilistic Novelty Detection with Adversarial Autoencoders
• An Overview of Robust Subspace Recovery
• 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
• ESAD: End-to-end Deep Semi-supervised Anomaly Detection
• Subspace Clustering using Ensembles of $K$-Subspaces
• A robust principal component analysis for outlier identification in messy microcalorimeter data
• 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
• Learning Competitive and Discriminative Reconstructions for Anomaly Detection
• Dual Principal Component Pursuit: Probability Analysis and Efficient Algorithms
• Outlier Detection and Data Clustering via Innovation Search
• Fast, Parameter free Outlier Identification for Robust PCA
• A Bias Trick for Centered Robust Principal Component Analysis
• Compressed Randomized UTV Decompositions for Low-Rank Approximations and Big Data Applications
• Provable Data Clustering via Innovation Search
• Deep Unsupervised Image Anomaly Detection: An Information Theoretic Framework
• Study of Compressed Randomized UTV Decompositions for Low-Rank Matrix Approximations in Data Science