Efficient Solvers for Sparse Subspace Clustering
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.
Code (1)
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Learning with $\ell^{0}$-Graph: $\ell^{0}$-Induced Sparse Subspace Clustering
Sparse subspace clustering methods, such as Sparse Subspace Clustering (SSC) \cite{ElhamifarV13} and $\ell^{1}$-graph \cite{YanW09,ChengYYFH10}, are effective in partitioning the data that lie in a union of subspaces. Mo…
ClusteringStochastic Sparse Subspace Clustering
State-of-the-art subspace clustering methods are based on self-expressive model, which represents each data point as a linear combination of other data points. By enforcing such representation to be sparse, sparse subspa…
ClusteringSparse Subspace Clustering with Entropy-Norm
Sparse subspace clustering (SSC) and spectral clustering (SC) are both state-of-the-art methods to identify complex clusters in high-dimensional input space. However, there are few researches to discuss the relation betw…
ClusteringKernel Sparse Subspace Clustering on Symmetric Positive Definite Manifolds
Sparse subspace clustering (SSC), as one of the most successful subspace clustering methods, has achieved notable clustering accuracy in computer vision tasks. However, SSC applies only to vector data in Euclidean space.…
ClusteringGraph Connectivity in Noisy Sparse Subspace Clustering
Subspace clustering is the problem of clustering data points into a union of low-dimensional linear/affine subspaces. It is the mathematical abstraction of many important problems in computer vision, image processing and…
Clustering