Papers › Efficient Solvers for Sparse Subspace Clustering
Efficient Solvers for Sparse Subspace Clustering
Farhad Pourkamali-Anaraki, James Folberth, Stephen Becker
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 ℓ₁ or ℓ₀ regularization. Using ℓ₁ regularization results in a convex problem but requires O(n²) storage, and is typically solved by the alternating direction method of multipliers which takes O(n³) flops. The ℓ₀ 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 ℓ₁ and ℓ₀ models, and both linear and affine constraints. For both ℓ₁ and ℓ₀, 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 ℓ₁ case with just O(n²) flops. In the ℓ₀ case, our algorithm retains the low-memory overhead, and is the first algorithm to solve the SSC-ℓ₀ 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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections