Sparse Subspace Clustering: Algorithm, Theory, and Applications

By Ehsan Elhamifar, René Vidal. 2012

2,496 citations recorded by the source corpus.

We propose and study an algorithm, called Sparse Subspace Clustering, to cluster high-dimensional data points that lie in a union of low-dimensional subspaces. The key idea is that, among infinitely many possible representations of a data point in terms of other points, a sparse representation corresponds to selecting a few points that come from the same subspace. This motivates solving a sparse optimization program whose solution is used in a spectral clustering framework to infer the clustering of the data. As solving the sparse optimization program is NP-hard, we consider its convex relaxation and show that, under appropriate conditions on the arrangement of the subspaces and the distribution of the data, the proposed minimization program succeeds in recovering the desired sparse representations. The proposed algorithm does not require initialization, can be solved efficiently, and can handle data points near the intersections of subspaces. In addition, our algorithm can deal with data nuisances, such as noise, sparse outlying entries, and missing entries, directly by modifying the optimization program to incorporate the model of the data. We verify the effectiveness of the proposed algorithm through experiments on synthetic data as well as two real-world problems of motion segmentation and face clustering.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

iCaRL: Incremental Classifier and Representation Learning (2016, neutral): “In contrast, other potential methods for exemplar selection, such as [7, 26], were designed with other objectives and are not guaranteed to provide a good approximation quality for any number of prototypes.”
Consistent and Specific Multi-View Subspace Clustering (2018, methodology): “For instance, sparse subspace clustering (Elhamifar and Vidal 2013) finds a sparse representation from the subspaces of the data.”
Hidden Talents of the Variational Autoencoder. (2017, methodology): “Note that RPCA is commonly used for unsupervised cleaning of this type of data [14], and MNIST is known to have significant low-rank structure [29] as shown in Figure 5(a).”
Essential Tensor Learning for Multi-View Spectral Clustering (2018, methodology): “Due to the popularity of SSC [2] and LRR [3], many self-representation based subspace learning methods [4]–[7] are proposed for multi-view clustering.”
Zero-Shot Learning via Semantic Similarity Embedding (2015, methodology): “or large-scale cases, we adopt efﬁcient proximal gradient descent methods. Note that there are many alternate ways of embedding such as similarity rescaling, subspace clustering [27], sparse learning [7], and low rank representation [17], as long as the embedding is on the simplex. We tried these di”
Hierarchical Clustering Multi-Task Learning for Joint Human Action Grouping and Recognition (2017, background): “…the related actions (e.g., handwaving/handclapping/boxing can be regarded as related actions considering salient limb and hand motions) while identifying those non-relevant actions (e.g., jogging/walking/running can be considered as nonrelevant actions to the aforementioned limb-wise actions).”
COMIC: Multi-view Clustering Without Parameter Selection (2019, background): “Copyright 2019 by the author(s). source (Hocking et al., 2011; Elhamifar & Vidal, 2013; Liu et al., 2016; Flammarion et al., 2017; Shah & Koltun, 2017; Liu et al., 2019; Peng et al., 2017a; 2018; Liu et al., 2017), which may be less attractive to some scenarios due to the heterogeneous properties…”
Multi-Task Learning for Subspace Segmentation (2015, methodology): “Motion Segmentation Data: We next present evaluations using the Hopkins 155 Motion Database (Elhamifar & Vidal, 2013).”
A Nonlinear Orthogonal Non-Negative Matrix Factorization Approach to Subspace Clustering (2017, methodology): “11 State-of-the-art methods in single view subspace clustering learn affinity graph matrix by imposing 12 sparseness [11], low-rank [12] or jointly sparseness and low-rank constraints [13] on representation matrix.”
Stratified Transfer Learning for Cross-domain Activity Recognition (2017, methodology): “To circumvent the global domain shift, [12] clustered the data points in a low-dimensional space using sparse subspace clustering.”
Low-Rank Tensor Constrained Multiview Subspace Clustering (2015, methodology): “Similar to the prevalent subspace clustering methods (e.g., [15] [28] [21]), LT-MSC also adopts a two-stage framework for clustering: It firstly learns an affinity matrix from the given data points, and then uses spectral clustering to produce the final clustering results.”
Large-scale Multi-view Subspace Clustering in Linear Time (2019, methodology): “Among the various subspace clustering approaches, spectral clustering based methods such as low-rank representation (LRR) (Liu et al. 2013; Kang, Peng, and Cheng 2015) and sparse subspace clustering (SSC) (Elhamifar and Vidal 2013) have achieved great success.”
Deep Subspace Clustering Networks (2017, methodology): “, image segmentation [50, 27], motion segmentation [17, 9], and image clustering [14, 10].”
Structured AutoEncoders for Subspace Clustering (2018, methodology): “After obtaining deep features, we conduct SSC and LRR to achieve data clustering.”
Domain adaptive sparse representation-based classification (2015, methodology): “Similar ideas have been explored for subspace clustering using sparse representation in [20].”
Visual SLAM and Structure from Motion in Dynamic Environments (2018, background): “Another point of view is given by Elhamifar and Vidal [34, 35] that leverages a sparse representation to cluster motion.”
Structured Graph Learning for Scalable Subspace Clustering: From Single View to Multiview (2021, neutral): “For instance, SSCOMP [28] is built on orthogonal matching pursuit; ESSC [29] is a proximal gradient framework to solve sparse subspace clustering; ALRR [30] is a faster solver for low-rank representation.”