Sparse Subspace Clustering: Algorithm, Theory, and Applications

Ehsan Elhamifar; Rene Vidal

Source-linked AI summary

Sparse Subspace Clustering: Algorithm, Theory, and Applications

Ehsan Elhamifar, Rene Vidal

arXiv:1203.1005v3Mar 5, 2012cs.CVcs.IRcs.ITcs.LGmath.OCstat.ML

TL;DR

The paper addresses clustering high-dimensional data that lie in unions of low-dimensional subspaces, where conventional clustering does not model the underlying structure. It proposes SSC, which combines sparse self-representation, an ℓ1 relaxation, and spectral clustering, and reports theoretical recovery guarantees, nuisance handling, and strong empirical performance. The authors identify unresolved theory for corrupted data and scalability to very large datasets.

Problem
Subspace clustering seeks to separate high-dimensional data according to underlying low-dimensional subspaces rather than centroid-based clusters.
Method
SSC sparsely represents each point using other data points, uses an efficiently solvable ℓ1 relaxation, constructs a similarity graph, and applies spectral clustering.
Results
Under appropriate subspace and data-distribution conditions, SSC recovers desired sparse representations and outperforms state-of-the-art methods on motion segmentation and face clustering.
Takeaways & Limitations
SSC can incorporate models for noise, sparse outliers, missing entries, and affine subspaces directly into its sparse optimization program.
Takeaways & Limitations
The paper leaves theoretical analysis for sparse recovery with corrupted data and scalability to very large datasets as future work.

Abstract

from arXiv · show

In many real-world problems, we are dealing with collections of high-dimensional data, such as images, videos, text and web documents, DNA microarray data, and more. Often, high-dimensional data lie close to low-dimensional structures corresponding to several classes or categories the data belongs to. In this paper, we propose and study an algorithm, called Sparse Subspace Clustering (SSC), to cluster data points that lie in a union of low-dimensional subspaces. The key idea is that, among infinitely many possible representations of a data point in terms of other points, a sparse representation corresponds to selecting a few points from the same subspace. This motivates solving a sparse optimization program whose solution is used in a spectral clustering framework to infer the clustering of data into subspaces. Since solving the sparse optimization program is in general NP-hard, we consider a convex relaxation and show that, under appropriate conditions on the arrangement of subspaces and the distribution of data, the proposed minimization program succeeds in recovering the desired sparse representations. The proposed algorithm can be solved efficiently and can handle data points near the intersections of subspaces. Another key advantage of the proposed algorithm with respect to the state of the art is that it can deal with data nuisances, such as noise, sparse outlying entries, and missing entries, directly by incorporating the model of the data into the sparse optimization program. We demonstrate the effectiveness of the proposed algorithm through experiments on synthetic data as well as the two real-world problems of motion segmentation and face clustering.

1 INTRODUCTION

High-dimensional data often lie in unions of low-dimensional subspaces, motivating clustering methods that model subspace structure rather than centroid-based proximity. SSC uses sparse self-representation, convex optimization, and spectral clustering to address this problem across challenging data settings.

Motivation: High-dimensional data frequently lie in low-dimensional structures associated with different classes or categories.Examples include feature trajectories, face images, and handwritten digits with varying imaging or geometric conditions.
Motivation: Subspace clustering separates data according to underlying subspaces, supporting applications including image processing, motion segmentation, and temporal video segmentation.Standard clustering methods are generally unsuitable because subspace data need not be distributed around cluster centroids.
Prior methods: Existing iterative, algebraic, statistical, and spectral methods face limitations involving initialization, known subspace parameters, noise, outliers, intersections, neighborhood selection, or computational complexity.Local spectral methods especially struggle with points near subspace intersections and depend on neighborhood size.
SSC approach: SSC represents each point sparsely using other data points, builds a similarity graph from the coefficients, and applies spectral clustering to infer subspace assignments.The method exploits the idea that a sparse representation selects a few points from the same subspace, even when they are not nearby.
Theory: The ℓ1 relaxation recovers desired sparse representations under conditions on subspace arrangement and data distribution without known bases or known point memberships.The formulation addresses a more challenging setting than block-sparse recovery because the subspaces and memberships are unknown.
Contributions: SSC is efficiently solvable, requires no initialization, incorporates models for noise, sparse outliers, missing entries, and affine subspaces, and outperforms state-of-the-art methods on motion and face clustering.The paper reports experiments on synthetic data and real-world motion-segmentation and face-clustering problems.

2 SPARSE SUBSPACE CLUSTERING

SSC clusters data lying in a union of low-dimensional subspaces by finding sparse representations whose selected points ideally come from the same subspace, then applying spectral clustering. The method uses convex optimization to obtain sparse coefficients and constructs a similarity graph for segmentation.

SSC assumes data points lie in a union of unknown low-dimensional subspaces and seeks their number, dimensions, bases, and segmentation.
2.1 Sparse Optimization Program: Each data point is represented by a few other points through a global sparse optimization program, encoding subspace-membership information.The data matrix serves as a self-expressive dictionary, while the zero-diagonal constraint prevents representing a point using itself.
2.1 Sparse Optimization Program: A subspace-sparse representation has nonzero coefficients only on points from the same subspace as the represented point.For a point in a dℓ-dimensional subspace, dℓ other points in general directions can represent it in general.
2.1 Sparse Optimization Program: The ℓ1 program minimizes ∥ci∥1 subject to yi = Yci and cii = 0, providing an efficiently solvable convex relaxation that favors sparse representations.The matrix form is min ∥C∥1 subject to Y = YC and diag(C) = 0.
2.2 Clustering using Sparse Coefficients: The coefficients define a symmetric similarity matrix W = |C| + |C|⊤, whose graph is ideally separated into connected components corresponding to the subspaces.Spectral clustering is then applied to normalized rows associated with the bottom eigenvectors of the normalized graph Laplacian, followed by K-means.
2.2 Clustering using Sparse Coefficients: Spectral clustering can tolerate a few representation errors when edges connecting different subspaces remain weak.Sparse coefficients may optionally be normalized by their infinity norm to better handle data points with different norms.

3 PRACTICAL EXTENSIONS

SSC is extended to affine subspaces and corrupted or incomplete data by incorporating affine constraints and corruption models directly into convex sparse optimization programs. The resulting coefficients support spectral clustering without a separate error-correction stage.

Noise and Sparse Outlying Entries: After optimization, SSC builds a similarity graph from C and applies spectral clustering, handling corrupted data without a separate error-correction algorithm.The corruption model is incorporated into the sparse optimization program itself.
Noise and Sparse Outlying Entries: SSC models corrupted data as Y = YC + E + Z, where C is sparse, E captures sparse outliers, and Z captures noise.The optimization uses ℓ1 penalties for sparsity and a Frobenius penalty for small noise entries; λe and λz balance the terms.
Noise and Sparse Outlying Entries: The corruption-aware optimization is convex and can be solved efficiently using convex programming tools.The formulation jointly estimates sparse coefficients, sparse outlying entries, and noise.
Noise and Sparse Outlying Entries: Theoretical guarantees for the proposed optimization program in the corrupted-data case remain the subject of current research.The paper notes a broad bound on the coefficient magnitude but does not present complete corrupted-data guarantees here.
Incomplete Data: Incomplete data with a small fraction of missing entries can be converted into sparse outliers, while sufficiently shared known entries permit projection to complete data before SSC.When the common known-coordinate set is not small relative to the ambient dimension, SSC is applied after retaining those coordinates.
Affine Subspaces: For affine subspaces, each point can be represented by an affine combination of dℓ + 1 other points from its containing subspace.The affine formulation adds linear equality constraints and also includes linear subspaces as a special case.

4 SUBSPACE-SPARSE RECOVERY THEORY

The recovery theory characterizes when sparse optimization selects points from the same subspace. Independent subspaces guarantee recovery broadly, while disjoint subspaces require conditions linking principal angles and within-subspace data distribution.

Independent Subspace Model: For independent subspaces, ℓq-minimization with q < ∞ always recovers subspace-sparse representations under the stated rank conditions.The result applies to every nonzero point in each subspace and does not require assumptions on within-subspace data distribution beyond rank(Yi) = di.
Disjoint Subspace Model: For disjoint subspaces, ℓ1 recovery holds when the within-subspace representation has smaller ℓ1 norm than representations using the other subspaces.The condition is evaluated for nonzero vectors in the intersection of one subspace with the direct sum of the others.
Disjoint Subspace Model: A sufficient condition requires the smallest principal angle to exceed a value determined by the data distribution in the target subspace.The bound can become high when data-point norms are unevenly distributed across subspaces.
Independent Subspace Model: Independent subspaces guarantee ℓ1 subspace-sparse recovery because their intersection with the direct sum of the other subspaces is only the origin.This makes the relevant recovery condition hold automatically.
Geometric Interpretation: Geometrically, recovery holds when the target-subspace polytope reaches an intersection point before the polytope formed from the other subspaces.Decreasing subspace angles or making the target data nearly degenerate can reverse this order and cause recovery failure at the intersection.

5 GRAPH CONNECTIVITY

The paper analyzes connectivity in SSC's similarity graph and adds row-sparsity regularization to encourage points within each subspace to form connected components.

Connectivity conditions: SSC separates subspaces when sparse representations avoid cross-subspace connections, but same-subspace connectivity is also required for correct spectral clustering.Experiments generally found one connected component per subspace, although prior theory identifies possible fragmentation for dimensions at least 4 under odd data distributions.
Connectivity regularization: The row-sparsity regularizer promotes selecting a few common points across sparse representations, increasing connectivity within each subspace.It minimizes the number of nonzero rows of C, corresponding to common selected data points.
Example: In the three-line example, λr = 0 yields three graph components matching the subspaces, whereas a large λr can yield one component spanning all three.The alternative solution selects points from other subspaces, sacrificing subspace sparsity.
Connectivity regularization: The convex program minimizes ℓ1 sparsity plus λr-weighted row sparsity subject to self-expression and zero diagonal constraints.λr controls the trade-off between solution sparsity and graph connectivity.
Example: Large λr values can prevent recovery of subspace-sparse representations, motivating a small row-sparsity regularization weight.The example shows that optimizing connectivity too strongly can introduce cross-subspace representations.

6 EXPERIMENTS WITH SYNTHETIC DATA

Synthetic experiments test how principal-angle separation and the number of points affect SSC's sparse recovery and clustering errors. Errors decrease as either quantity increases and reach zero in sufficiently favorable settings.

Experimental design: The experiments vary the smallest principal angle and the number of points per subspace to test their predicted effects on SSC recovery.The ambient dimension is D = 50, with θ ∈ [6, 60] degrees and Ng ∈ [d + 1, 32d].
Experimental design: Three equal-dimensional subspaces are generated so each lies in the direct sum of the other two, making cross-subspace reconstruction possible.The construction isolates the effects of principal-angle separation and data distribution.
Evaluation: The study measures subspace-sparse recovery error and spectral-clustering error, where zero recovery error means each point uses only points from its own subspace.The clustering error is computed after constructing the similarity graph from sparse coefficients.
Dataset statistics: The experiments also examine principal-angle proximity and cross-subspace nearest-neighbor overlap in the Hopkins 155 and Extended Yale B datasets.Figure 10 reports motion subspaces of dimension at most 4 and face subspaces of dimension around 9.
Results: When the principal angle or point count is small, both errors are large; increasing either variable reduces both errors.For sufficiently large θ and Ng, the experiments obtain zero errors.

7 EXPERIMENTS WITH REAL DATA

Real-data experiments evaluate SSC for motion segmentation and face clustering against several subspace-clustering methods. SSC achieves low clustering error across the tested settings, including noisy, corrupted, and dimension-reduced data.

Setup: SSC is compared with LSA, SCC, LRR, and LRSC on Hopkins 155 motion segmentation and Extended Yale B face clustering.The datasets contain 2–3 motions across 155 videos and images from 38 subjects, respectively.
Dataset characteristics: Both datasets contain closely arranged subspaces: principal angles are below 10 degrees for motions and between 10 and 20 degrees for faces.Nearest-neighbor overlap statistics further characterize the separation challenge.
Motion segmentation: SSC outperforms the other algorithms with small clustering error on the evaluated motion-segmentation cases, with similarity-matrix normalization improving results by about 0.5%.The authors attribute success to principal-angle separation and feature-trajectory distribution, while noting that normalization's improvement is small.
Motion segmentation: SSC obtains less than 2.5% clustering error across a broad range of αz values on Hopkins 155 using both original and PCA-reduced data.The error pattern is similar for 2F-dimensional trajectories and 4n-dimensional PCA projections.
Algorithm comparison: LRR's post-processing substantially improves its clustering, whereas LRR-H can still perform relatively poorly for 8 and 10 subjects; LRSC obtains zero error in the cited comparison.The paper also reports that SCC is drastically slower because its complexity grows exponentially with subspace dimension.
Face clustering: SSC achieves 1.86% and 10.94% clustering error for 2 and 10 subjects, respectively, when directly incorporating sparse outlier corruption.These errors are lower than those obtained after applying RPCA to all data points.

8 CONCLUSIONS AND FUTURE WORK

The paper concludes that SSC uses sparse representations and spectral clustering to segment data in unions of low-dimensional subspaces, while incorporating several data nuisances directly. Experiments on real data support its effectiveness, and future work targets theory for nuisances, graph connectivity, and scalability.

Conclusions: SSC finds sparse representations in the dictionary of other data points and uses them to cluster points in low-dimensional subspaces.The algorithm builds a similarity graph from sparse coefficients and applies spectral clustering.
Conclusions: Average computational time is evaluated on Extended Yale B as a function of the number of subjects.
Conclusions: SSC incorporates models for noise, sparse outlying entries, missing entries, and affine subspaces directly into its sparse optimization program.
Conclusions: Real-data experiments on face images and video motions showed SSC’s effectiveness and superiority over the state of the art.
Future Work: Future work includes analyzing subspace-sparse recovery with nuisances, explaining similarity-graph connectivity, and scaling optimization plus spectral clustering to very large datasets.The authors identify these as theoretical and practical research directions.

PROOF OF PROPOSITION 1

The proposition analyzes an optimization program that separates representation coefficients from corruption and noise terms. Under bounds on the corresponding regularization parameters, an optimal solution can assign an entire data point to the relevant nuisance term.

Optimization Program: The optimization program enforces Y = YC + E + Z with diag(C) = 0, separating representation, outlier, and noise components.
Proposition: Proposition 1 states that, without Z, λe ≤ 1/µe ensures at least one point has (cℓ, eℓ) = (0, yℓ).
Proposition: Without E, λz ≤ 1/µz ensures at least one point has (cℓ, zℓ) = (0, yℓ).
Proof Strategy: The proof decomposes the global optimization into N columnwise programs yi = Yci + ei + zi with cii = 0.
Proof Strategy: The parameter conditions make the zero-coefficient solution optimal in the respective programs, yielding the proposition’s existence claims.

PROOF OF THEOREM 1

Theorem 1 proves subspace-sparse recovery for data drawn from independent subspaces. The proof uses independence to show that representations involving other subspaces cannot replace a representation within the data point’s own subspace.

Result: For every nonzero y in Si, ℓq-minimization recovers a subspace-sparse representation with nonzero coefficients only from Si.
Assumptions: The theorem considers n independent subspaces, with Yi containing Ni points of rank di and Y−i containing points from all other subspaces.
Proof: The proof writes y = Yic and assumes an alternative representation involving Y−i to derive a contradiction.
Proof: Independence makes Si and the direct sum of the other subspaces disjoint except at the origin, forcing the competing representation’s Y−i component to vanish.

PROOF OF THEOREM 2

Theorem 2 gives a necessary and sufficient condition for ℓ1-minimization to recover subspace-sparse representations in disjoint subspaces. The condition compares minimum ℓ1 representations of intersection vectors using a subspace against all other subspaces.

Sufficient Condition: If every nonzero x in Si ∩ ⊕j≠iSj has a strictly smaller ℓ1 representation using Yi than using Y−i, SSC recovers all subspace-sparse representations in Si.
Assumptions: The theorem considers n disjoint subspaces with Yi of rank di and Y−i containing points from every other subspace.
Proof: The proof represents x as both y − Yic* and combinations within Si and the other subspaces, then compares the resulting feasible solutions.
Proof: Triangle inequality and the strict intersection condition contradict optimality when a representation is not subspace-sparse.
Necessary Condition: If the condition fails, an intersection vector can be represented with no larger ℓ1 norm using other subspaces, contradicting subspace-sparse recovery.

PROOF OF THEOREM 3

Theorem 3 establishes a sufficient condition under which ℓ1-minimization recovers subspace-sparse representations for data drawn from disjoint subspaces. The proof bounds within-subspace and outside-subspace representation norms and compares them using principal angles and data norms.

Theorem statement: Theorem 3 considers data drawn from n disjoint subspaces and gives a condition ensuring subspace-sparse recovery for every nonzero y in a subspace.The recovered coefficient vector is nonzero and supported on the corresponding subspace.
Upper bound: The proof upper-bounds the ℓ1 norm of a representation using full-column-rank submatrices of the data from the target subspace.The bound uses the smallest singular value of a selected submatrix.
Comparison condition: The sufficient condition β_i < β_−i guarantees that the target-subspace representation has smaller ℓ1 norm than any competing outside-subspace representation.This inequality implies the condition required by Theorem 2.
Lower bound: It lower-bounds the ℓ1 norm of representations using points outside the target subspace by applying the Hölder inequality.The outside-subspace representation is written as x = Y_−i a_−i before deriving the lower bound.
Geometric quantities: The outside-subspace bound depends on the smallest principal angle between subspaces and the maximum ℓ2 norm of columns from the other subspaces.The quantity ∥Y_−i∥_1,2 measures the largest column norm outside the target subspace.

SOLVING THE SPARSE OPTIMIZATION PROGRAM

The paper develops an ADMM implementation for its sparse optimization programs by introducing auxiliary variables, augmenting equality constraints, and iteratively updating primal and dual variables. The resulting procedure produces an optimal sparse coefficient matrix while offering implementation choices for different problem sizes.

Computational considerations: Generic convex solvers such as CVX can be computationally expensive and may not scale well with dimension or sample count.The paper compares algorithm runtimes on Extended Yale B and notes that faster specialized solvers can improve SSC and LRR.
ADMM formulation: The sparse optimization programs are solved with an ADMM method designed for efficient implementation.The approach targets the general optimization program and introduces auxiliary variables to facilitate updates.
Optimization program: Eliminating Z yields an equivalent program with reconstruction, affine-sum, and zero-diagonal constraints on the coefficient matrix C.The formulation includes Y = YC + E + Z, C^⊤1 = 1, and diag(C) = 0 before eliminating Z.
Auxiliary variables: An auxiliary matrix A separates the constraints A^⊤1 = 1 and A = C − diag(C), enabling alternating updates of the optimization variables.Penalty terms preserve the optimal solution while making the objective strictly convex in (C, E, A).
Algorithm: Each ADMM iteration updates A, C, E, and the Lagrange multipliers, then stops when constraint and successive-iterate residuals fall below tolerance or maxIter is reached.The implementation initializes variables to zero and outputs C* as the final sparse coefficient matrix.
Numerical implementation: The method uses matrix inversion for smaller N and conjugate-gradient methods for large N when solving the A-update linear system.The A-update requires solving an N × N system of linear equations.