Efficient Sparse Subspace Clustering by Nearest Neighbour Filtering
arXiv:1704.03958
Abstract
Sparse Subspace Clustering (SSC) has been used extensively for subspace identification tasks due to its theoretical guarantees and relative ease of implementation. However SSC has quadratic computation and memory requirements with respect to the number of input data points. This burden has prohibited SSCs use for all but the smallest datasets. To overcome this we propose a new method, k-SSC, that screens out a large number of data points to both reduce SSC to linear memory and computational requirements. We provide theoretical analysis for the bounds of success for k-SSC. Our experiments show that k-SSC exceeds theoretical expectations and outperforms existing SSC approximations by maintaining the classification performance of SSC. Furthermore in the spirit of reproducible research we have publicly released the source code for k-SSC
References in corpus (5)
- Robust Recovery of Subspace Structures by Low-Rank Representation
- A geometric analysis of subspace clustering with outliers
- Constructing the L2-Graph for Robust Subspace Learning and Subspace Clustering
- Fixed-Rank Representation for Unsupervised Visual Learning
- Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering