Efficient Solvers for Sparse Subspace Clustering

Understand

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.