Efficient Solvers for Sparse Subspace Clustering

Abstract

Sparse subspace clustering (SSC) clusters $n$ points that lie near a union of low-dimensional subspaces. The SSC model expresses each point as a linear or affine combination of the other points, using either ${\ell }_1$ or ${\ell }_0$ regularization. Using ${\ell }_1$ regularization results in a convex problem but requires $O(n^2)$ storage, and is typically solved by the alternating direction method of multipliers which takes $O(n^3)$ flops. The ${\ell }_0$ model is non-convex but only needs memory linear in $n$, and is solved via orthogonal matching pursuit and cannot handle the case of affine subspaces. This paper shows that a proximal gradient framework can solve SSC, covering both ${\ell }_1$ and ${\ell }_0$ models, and both linear and affine constraints. For both ${\ell }_1$ and ${\ell }_0$, algorithms to compute the proximity operator in the presence of affine constraints have not been presented in the SSC literature, so we derive an exact and efficient algorithm that solves the ${\ell }_1$ case with just $O(n^2)$ flops. In the ${\ell }_0$ case, our algorithm retains the low-memory overhead, and is the first algorithm to solve the SSC-${\ell }_0$ model with affine constraints. Experiments show our algorithms do not rely on sensitive regularization parameters, and they are less sensitive to sparsity misspecification and high noise.

This paper is accepted for publication in Signal Processing

References in corpus (6)

• Sparse projections onto the simplex
• Sketched Subspace Clustering
• The geometry of kernelized spectral clustering
• Scalable and Robust Sparse Subspace Clustering Using Randomized Clustering and Multilayer Graphs
• On Geometric Analysis of Affine Sparse Subspace Clustering
• Active Orthogonal Matching Pursuit for Sparse Subspace Clustering

Cited by in corpus (2)

• Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms
• Online Sparse Subspace Clustering