A geometric analysis of subspace clustering with outliers
arXiv:1112.4258 · doi:10.1214/12-AOS1034
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.
arXiv commentPublished 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 (6)
- Median K-flats for hybrid linear modeling with many outliers
- Hybrid Linear Modeling via Local Best-fit Flats
- Multivariate analysis and Jacobi ensembles: largest eigenvalue, Tracy--Widom limits and rates of convergence
- Exact Subspace Segmentation and Outlier Detection by Low-Rank Representation
- Robust recovery of multiple subspaces by geometric l_p minimization
- Randomized hybrid linear modeling by local best-fit flats
Cited by in corpus (108)
- Robust Recovery of Subspace Structures by Low-Rank Representation
- Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
- Robust subspace clustering
- Block-Sparse Recovery via Convex Optimization
- Hybrid Linear Modeling via Local Best-fit Flats
- 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
- Robust Subspace Clustering via Smoothed Rank Approximation
- Anomaly Detection based on Zero-Shot Outlier Synthesis and Hierarchical Feature Distillation
- 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
- A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
- Efficient Solvers for Sparse Subspace Clustering
- 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
- Active Orthogonal Matching Pursuit for Sparse Subspace Clustering
- Clustering multi-way data: a novel algebraic approach
- Structured and Unstructured Outlier Identification for Robust PCA: A Non iterative, Parameter free Algorithm
- Robust Subspace Clustering via Tighter Rank Approximation
- lp-Recovery of the Most Significant Subspace among Multiple Subspaces with Outliers
- 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
- All-In-One Robust Estimator of the Gaussian Mean
- Self-Expressive Decompositions for Matrix Approximation and Clustering
- 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 -Subspaces
- Dual Principal Component Pursuit
- Efficient Sparse Subspace Clustering by Nearest Neighbour Filtering
- Restricted Connection Orthogonal Matching Pursuit For Sparse Subspace Clustering
- Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms
- Rigorous Restricted Isometry Property of Low-Dimensional Subspaces
- Accelerated Sparse Subspace Clustering
- Subspace Clustering by Block Diagonal Representation
- Filtrated Spectral Algebraic Subspace Clustering
- Basis Pursuit and Orthogonal Matching Pursuit for Subspace-preserving Recovery: Theoretical Analysis
- Learning Robust Subspace Clustering
- Theoretical Analysis of Sparse Subspace Clustering with Missing Entries
- Robust Group Subspace Recovery: A New Approach for Multi-Modality Data Fusion
- Subspace-Sparse Representation
- A New Geometric Approach to Latent Topic Modeling and Discovery
- Making transport more robust and interpretable by moving data through a small number of anchor points
- Unraveling the Veil of Subspace RIP Through Near-Isometry on Subspaces
- Inference and Mixture Modeling with the Elliptical Gamma Distribution
- Stochastic Sparse Subspace Clustering
- Revisiting data augmentation for subspace clustering
- Accurate and Scalable Image Clustering Based On Sparse Representation of Camera Fingerprint
- Survey on Computational Applications of Tensor Network Simulations
- VARCLUST: clustering variables using dimensionality reduction
- Compressed Subspace Learning Based on Canonical Angle Preserving Property
- Minimal Sample Subspace Learning: Theory and Algorithms
- Synchrosqueezed Wave Packet Transforms and Diffeomorphism Based Spectral Analysis for 1D General Mode Decompositions
- On deterministic conditions for subspace clustering under missing data
- Outlier Detection and Data Clustering via Innovation Search
- Estimation and Clustering in Popularity Adjusted Stochastic Block Model
- Minimum Enclosing Parallelogram with Outliers
- SSSC-AM: A Unified Framework for Video Co-Segmentation by Structured Sparse Subspace Clustering with Appearance and Motion Features
- Efficient Online Minimization for Low-Rank Subspace Clustering
- 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
- Bringing in the outliers: A sparse subspace clustering approach to learn a dictionary of mouse ultrasonic vocalizations
- Fast, Parameter free Outlier Identification for Robust PCA
- Robust Low-Complexity Randomized Methods for Locating Outliers in Large Matrices
- Sparse Subspace Clustering via Two-Step Reweighted L1-Minimization: Algorithm and Provable Neighbor Recovery Rates
- Is an Affine Constraint Needed for Affine Subspace Clustering?
- Provable Data Clustering via Innovation Search
- Leveraging Union of Subspace Structure to Improve Constrained Clustering
- Approximate Subspace-Sparse Recovery with Corrupted Data via Constrained -Minimization
- Blocked Clusterwise Regression
- Unsupervised clustering under the Union of Polyhedral Cones (UOPC) model
- Learning for Multi-Type Subspace Clustering
- Learning a Self-Expressive Network for Subspace Clustering
- Scalable Sparse Subspace Clustering via Ordered Weighted Regression
- Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graph
- Probabilistic Sparse Subspace Clustering Using Delayed Association
- Persistent Reductions in Regularized Loss Minimization for Variable Selection