Scalable and Robust Sparse Subspace Clustering Using Randomized Clustering and Multilayer Graphs

Abstract

Sparse subspace clustering (SSC) is one of the current state-of-the-art methods for partitioning data points into the union of subspaces, with strong theoretical guarantees. However, it is not practical for large data sets as it requires solving a LASSO problem for each data point, where the number of variables in each LASSO problem is the number of data points. To improve the scalability of SSC, we propose to select a few sets of anchor points using a randomized hierarchical clustering method, and, for each set of anchor points, solve the LASSO problems for each data point allowing only anchor points to have a non-zero weight (this reduces drastically the number of variables). This generates a multilayer graph where each layer corresponds to a different set of anchor points. Using the Grassmann manifold of orthogonal matrices, the shared connectivity among the layers is summarized within a single subspace. Finally, we use $k$-means clustering within that subspace to cluster the data points, similarly as done by spectral clustering in SSC. We show on both synthetic and real-world data sets that the proposed method not only allows SSC to scale to large-scale data sets, but that it is also much more robust as it performs significantly better on noisy data and on data with close susbspaces and outliers, while it is not prone to oversegmentation.

arXiv comment25 pages, v2: typos corrected

References in corpus (12)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• A geometric analysis of subspace clustering with outliers
• Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
• Robust subspace clustering
• Median K-flats for hybrid linear modeling with many outliers
• Lasso Screening Rules via Dual Polytope Projection
• Hierarchical Clustering of Hyperspectral Images using Rank-Two Nonnegative Matrix Factorization
• Sketched Subspace Clustering
• Linearized Alternating Direction Method with Parallel Splitting and Adaptive Penalty for Separable Convex Programs in Machine Learning
• Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering
• Active Orthogonal Matching Pursuit for Sparse Subspace Clustering
• Efficient Sparse Subspace Clustering by Nearest Neighbour Filtering

Cited by in corpus (8)

• Exactly Robust Kernel Principal Component Analysis
• Efficient Solvers for Sparse Subspace Clustering
• A fast and Accurate Similarity-constrained Subspace Clustering Framework for Unsupervised Hyperspectral Image Classification
• Structured Graph Learning for Scalable Subspace Clustering: From Single-view to Multi-view
• Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms
• Stochastic Sparse Subspace Clustering
• Revisiting data augmentation for subspace clustering
• Learning a Self-Expressive Network for Subspace Clustering