A geometric analysis of subspace clustering with outliers

Abstract

This paper considers the problem of clustering a collection of unlabeled data points assumed to lie near a union of lower-dimensional planes. As is common in computer vision or unsupervised learning applications, we do not know in advance how many subspaces there are nor do we have any information about their dimensions. We develop a novel geometric analysis of an algorithm named sparse subspace clustering (SSC) [In IEEE Conference on Computer Vision and Pattern Recognition, 2009. CVPR 2009 (2009) 2790-2797. IEEE], which significantly broadens the range of problems where it is provably effective. For instance, we show that SSC can recover multiple subspaces, each of dimension comparable to the ambient dimension. We also prove that SSC can correctly cluster data points even when the subspaces of interest intersect. Further, we develop an extension of SSC that succeeds when the data set is corrupted with possibly overwhelmingly many outliers. Underlying our analysis are clear geometric insights, which may bear on other sparse recovery problems. A numerical study complements our theoretical analysis and demonstrates the effectiveness of these methods.

Published in at http://dx.doi.org/10.1214/12-AOS1034 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Multivariate analysis and Jacobi ensembles: largest eigenvalue, Tracy--Widom limits and rates of convergence
• Exact Subspace Segmentation and Outlier Detection by Low-Rank Representation

Cited by in corpus (104)

• Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
• Robust subspace clustering
• Generative Probabilistic Novelty Detection with Adversarial Autoencoders
• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• An Overview of Robust Subspace Recovery
• Factoring nonnegative matrices with linear programs
• A Novel M-Estimator for Robust PCA
• Spectral Clustering Based on Local PCA
• Fixed-Rank Representation for Unsupervised Visual Learning
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Robust Subspace Clustering with Compressed Data
• Greedy Subspace Clustering
• Innovation Pursuit: A New Approach to Subspace Clustering
• Learning Transformations for Clustering and Classification
• Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering
• Guess Who Rated This Movie: Identifying Users Through Subspace Clustering
• Noisy Sparse Subspace Clustering
• Algebraic Clustering of Affine Subspaces
• Anomaly Detection based on Zero-Shot Outlier Synthesis and Hierarchical Feature Distillation
• Robust Subspace Clustering via Smoothed Rank Approximation
• Restricted Isometry Property of Gaussian Random Projection for Finite Set of Subspaces
• Noisy Matrix Completion under Sparse Factor Models
• Scalable and Robust Sparse Subspace Clustering Using Randomized Clustering and Multilayer Graphs
• Efficient Solvers for Sparse Subspace Clustering
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• A New Approach To Two-View Motion Segmentation Using Global Dimension Minimization
• Algorithms and Hardness for Robust Subspace Recovery
• On Geometric Analysis of Affine Sparse Subspace Clustering
• Clustering multi-way data: a novel algebraic approach
• Active Orthogonal Matching Pursuit for Sparse Subspace Clustering
• Structured and Unstructured Outlier Identification for Robust PCA: A Non iterative, Parameter free Algorithm
• Robust Subspace Clustering via Tighter Rank Approximation
• Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit
• Learning the nonlinear geometry of high-dimensional data: Models and algorithms
• Sparse Subspace Clustering: Algorithm, Theory, and Applications
• A general model for plane-based clustering with loss function
• Noisy subspace clustering via matching pursuits
• Riemannian Multi-Manifold Modeling
• Subspace clustering without knowing the number of clusters: A parameter free approach
• Matrix Completion Under Monotonic Single Index Models
• Evolutionary Self-Expressive Models for Subspace Clustering
• Doubly Stochastic Subspace Clustering
• Guess Who Rated This Movie: Identifying Users Through Subspace Clustering
• Self-Expressive Decompositions for Matrix Approximation and Clustering
• All-In-One Robust Estimator of the Gaussian Mean
• A Theoretical Analysis of Noisy Sparse Subspace Clustering on Dimensionality-Reduced Data
• Neither Global Nor Local: A Hierarchical Robust Subspace Clustering For Image Data
• Subspace Clustering via Optimal Direction Search
• Unsupervised Anomaly Detection with Adversarial Mirrored AutoEncoders
• Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search
• A Critique of Self-Expressive Deep Subspace Clustering
• Low Rank Matrix Recovery with Simultaneous Presence of Outliers and Sparse Corruption
• Popularity Adjusted Block Models are Generalized Random Dot Product Graphs
• Understanding People Flow in Transportation Hubs
• Subspace Clustering using Ensembles of $K$-Subspaces
• Efficient Sparse Subspace Clustering by Nearest Neighbour Filtering
• Dual Principal Component Pursuit
• Filtrated Spectral Algebraic Subspace Clustering
• Rigorous Restricted Isometry Property of Low-Dimensional Subspaces
• Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms
• Accelerated Sparse Subspace Clustering
• Basis Pursuit and Orthogonal Matching Pursuit for Subspace-preserving Recovery: Theoretical Analysis
• Theoretical Analysis of Sparse Subspace Clustering with Missing Entries
• Restricted Connection Orthogonal Matching Pursuit For Sparse Subspace Clustering
• Learning Robust Subspace Clustering
• Subspace Clustering by Block Diagonal Representation
• Robust Group Subspace Recovery: A New Approach for Multi-Modality Data Fusion
• Unraveling the Veil of Subspace RIP Through Near-Isometry on Subspaces
• Making transport more robust and interpretable by moving data through a small number of anchor points
• Stochastic Sparse Subspace Clustering
• Inference and Mixture Modeling with the Elliptical Gamma Distribution
• A New Geometric Approach to Latent Topic Modeling and Discovery
• Subspace-Sparse Representation
• Accurate and Scalable Image Clustering Based On Sparse Representation of Camera Fingerprint
• VARCLUST: clustering variables using dimensionality reduction
• Compressed Subspace Learning Based on Canonical Angle Preserving Property
• Survey on Computational Applications of Tensor Network Simulations
• Revisiting data augmentation for subspace clustering
• Estimation and Clustering in Popularity Adjusted Stochastic Block Model
• Outlier Detection and Data Clustering via Innovation Search
• SSSC-AM: A Unified Framework for Video Co-Segmentation by Structured Sparse Subspace Clustering with Appearance and Motion Features
• On deterministic conditions for subspace clustering under missing data
• Minimal Sample Subspace Learning: Theory and Algorithms
• Synchrosqueezed Wave Packet Transforms and Diffeomorphism Based Spectral Analysis for 1D General Mode Decompositions
• Minimum Enclosing Parallelogram with Outliers
• Subspace clustering based on low rank representation and weighted nuclear norm minimization
• Riemannian-geometry-based modeling and clustering of network-wide non-stationary time series: The brain-network case
• Efficient Online Minimization for Low-Rank Subspace Clustering
• Fast, Parameter free Outlier Identification for Robust PCA
• Bringing in the outliers: A sparse subspace clustering approach to learn a dictionary of mouse ultrasonic vocalizations
• Robust Low-Complexity Randomized Methods for Locating Outliers in Large Matrices
• Unsupervised clustering under the Union of Polyhedral Cones (UOPC) model
• Leveraging Union of Subspace Structure to Improve Constrained Clustering
• Is an Affine Constraint Needed for Affine Subspace Clustering?
• Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graph
• Scalable Sparse Subspace Clustering via Ordered Weighted ${\ell }_1$ Regression
• Blocked Clusterwise Regression
• Learning for Multi-Type Subspace Clustering
• Sparse Subspace Clustering via Two-Step Reweighted L1-Minimization: Algorithm and Provable Neighbor Recovery Rates
• Approximate Subspace-Sparse Recovery with Corrupted Data via Constrained ${\ell }_1$-Minimization
• Probabilistic Sparse Subspace Clustering Using Delayed Association
• Provable Data Clustering via Innovation Search
• Learning a Self-Expressive Network for Subspace Clustering
• Persistent Reductions in Regularized Loss Minimization for Variable Selection