  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.
