paper:doi-10-1109-tip-2017-2691557Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
Original abstract (expand)
Subspace clustering refers to the problem of segmenting data drawn from a union of subspaces. State-of-the-art approaches for solving this problem follow a two-stage approach. In the first step, an affinity matrix is learned from the data using sparse or low-rank minimization techniques. In the second step, the segmentation is found by applying spectral clustering to this affinity. While this approach has led to the state-of-the-art results in many applications, it is suboptimal, because it does not exploit the fact that the affinity and the segmentation depend on each other. In this paper, we propose a joint optimization framework — Structured Sparse Subspace Clustering (S3C) — for learning both the affinity and the segmentation. The proposed S3C framework is based on expressing each data point as a structured sparse linear combination of all other data points, where the structure is induced by a norm that depends on the unknown segmentation. Moreover, we extend the proposed S3C framework into Constrained S3C (CS3C) in which available partial side-information is incorporated into the stage of learning the affinity. We show that both the structured sparse representation and the segmentation can be found via a combination of an alternating direction method of multipliers with spectral clustering. Experiments on a synthetic data set, the Extended Yale B face data set, the Hopkins 155 motion segmentation database, and three cancer data sets demonstrate the effectiveness of our approach.
Similar preprints — Semantic Scholar
Cited by (2)
- Do Sparse Autoencoders Capture Concept Manifolds?
Sparse autoencoders trained on Llama3.1-8B (layer 19, 500M Pile tokens, 25 SAEs across Standard, JumpReLU, TopK, BatchTopK and Matryoshka architectures at VE > 0.85) do not capture continuous concept
- Structuring Sparsity: Block-Sparse Featurizers Capture Visual Concept Manifolds
Lifting the featurizer's atom from a direction to a block of directions recovers concept manifolds that SAEs shatter, and block sparsity is the MAP-matched prior for a representation that is a sparse