# Sparse Subspace Clustering: Algorithm, Theory, and Applications

**Authors:** Ehsan Elhamifar, Rene Vidal  
**arXiv:** [1203.1005](https://arxiv.org/abs/1203.1005)  
**Date:** 2012-03-05  
**Summary page:** https://www.summarizepaper.com/en/paper/1203.1005v3/

## Key points

- The paper proposes an algorithm to cluster high-dimensional data points that lie in a union of low-dimensional subspaces.
- Real-world problems often involve collections of high-dimensional data with low-dimensional structures corresponding to several classes or categories the data belongs to.
- The proposed algorithm achieves a sparse representation of a data point by selecting only a few points from the same subspace among infinitely many possible representations in terms of other points.
- To achieve this sparse representation, the authors propose solving a sparse optimization program whose solution is used in a spectral clustering framework to infer the clustering of data into subspaces.
- The proposed algorithm can handle various types of nuisances commonly found in real world datasets, including noise, sparse outlying entries, and missing entries.
- Experiments on synthetic data as well as two real-world problems (motion segmentation and face clustering) showed that Sparse Subspace Clustering outperformed existing methods in terms of accuracy and efficiency.

## Summary

The paper "Sparse Subspace Clustering: Algorithm, Theory, and Applications" proposes an algorithm to cluster high-dimensional data points that lie in a union of low-dimensional subspaces. The authors note that many real-world problems involve collections of high-dimensional data, such as images, videos, text and web documents, DNA microarray data, and more. These types of data often have low-dimensional structures corresponding to several classes or categories the data belongs to. The key idea behind the proposed algorithm is that a sparse representation of a data point corresponds to selecting only a few points from the same subspace among infinitely many possible representations in terms of other points. To achieve this sparse representation, the authors propose solving a sparse optimization program whose solution is used in a spectral clustering framework to infer the clustering of data into subspaces. Since solving the sparse optimization program is generally NP-hard, the authors consider a convex relaxation and show that under appropriate conditions on the arrangement of subspaces and the distribution of data, their proposed minimization program succeeds in recovering the desired sparse representations. The proposed algorithm can be solved efficiently and can handle data points near intersections of subspaces. One key advantage of this algorithm over existing state-of-the-art methods is its ability to deal with various types of data nuisances directly by incorporating them into the model through the sparse optimization program. These nuisances include noise, sparse outlying entries, and missing entries. To demonstrate its effectiveness, experiments were conducted on synthetic data as well as two real-world problems: motion segmentation and face clustering. The results showed that Sparse Subspace Clustering outperformed existing methods in terms of accuracy and efficiency. Overall, this paper provides an important contribution to clustering high-dimensional datasets with low-dimensional structures by proposing an efficient algorithm which can handle various types of nuisances commonly found in real world datasets.