Source-linked AI summary
Robust subspace clustering
Mahdi Soltanolkotabi, Ehsan Elhamifar, Emmanuel J. Candès
TL;DR
The paper addresses clustering points near a union of unknown subspaces when observations are noisy and direct noiseless SSC representations are unreliable. It develops a tractable robust SSC extension and rigorous theory, showing effectiveness under bounded noise, suitable subspace separation, and sufficient sampling, including a challenging regime with overlapping subspaces and limited points.
Problem
Noisy observations near multiple unknown subspaces make clustering difficult because both the clean covariates and response vectors are corrupted.
Method
The paper introduces a tractable robust SSC algorithm based on sparse regression, similarity-graph construction, and spectral clustering.
Results
The robust SSC algorithm provably clusters noisy data with high probability under bounded noise, affinity and sampling conditions, while making no false discoveries and many true discoveries.
Takeaways & Limitations
The theory supports clustering in a challenging regime where subspaces overlap along many dimensions and each subspace has relatively few points.
Takeaways & Limitations
The analysis assumes bounded noise and leaves theoretical guarantees for the clustering cleanup step as an open problem.
Abstract
from arXiv · showhide
Subspace clustering refers to the task of finding a multi-subspace representation that best fits a collection of points taken from a high-dimensional space. This paper introduces an algorithm inspired by sparse subspace clustering (SSC) [In IEEE Conference on Computer Vision and Pattern Recognition, CVPR (2009) 2790-2797] to cluster noisy data, and develops some novel theory demonstrating its correctness. In particular, the theory uses ideas from geometric functional analysis to show that the algorithm can accurately recover the underlying subspaces under minimal requirements on their orientation, and on the number of samples per subspace. Synthetic as well as real data experiments complement our theoretical study, illustrating our approach and demonstrating its effectiveness.
1. Introduction.
Subspace clustering separates unlabeled data lying near a union of unknown low-dimensional subspaces. The paper extends sparse subspace clustering to noisy observations and analyzes performance through subspace separation, sampling density, and noise assumptions.
- Motivation: Subspace clustering assigns unlabeled observations to component subspaces rather than fitting one lower-dimensional subspace to all data.The paper motivates this setting with mixtures such as gene-expression patterns from different cancer types.
- Motivation: Noisy subspace clustering is challenging because both the covariates and response vectors are corrupted.Direct noiseless sparse representations may no longer exist when the observed matrix replaces the clean data matrix.
- Contribution: The paper introduces a tractable noisy-data extension of SSC with theory expressed using principal angles, sample counts, and noise level.The model treats observations as points near a union of unknown linear subspaces.
- Key concepts: Subspace affinity measures correlation: it is low for nearly orthogonal subspaces and high when principal angles are small.High affinity makes clustering harder, while lower affinity makes separation easier.
- Key concepts: Sampling density is the number of samples per subspace dimension, ρℓ = Nℓ/dℓ.The paper identifies the number of samples on each subspace as a fundamental performance factor.
2. Robust subspace clustering: Methods and concepts.
The methodology models observed data as noisy versions of clean subspace points and uses heuristic arguments supported by numerical experiments, with theoretical guarantees developed later. It also notes that clustering becomes harder when points align within lower-dimensional structures.
- Observed data are arranged as columns of Y = X + Z, separating clean points X from noise Z.The matrix Y contains N observed data points in R^n.
- The section presents heuristic methodological arguments that are confirmed by numerical experiments, while guarantees for the algorithm’s first step follow later.
- Clustering becomes harder when points with arbitrary orientations align along an even lower-dimensional structure.
- The analysis assumes ρ_ℓ ≤ e d_ℓ/2, with other values handled by replacing ρ_ℓ with ρ_ℓ ∧ e d_ℓ/2.
- In practice, the data columns may be normalized so that each observed point has unit ℓ2 norm.The passage also states that under the SNR assumption, the observed and clean point norms are approximately equal before normalization.
2.1. The normalized model.
The normalized model uses unit-norm clean points with independent Gaussian noise and treats clean- and observed-point normalization as nearly equivalent. The section also situates the approach relative to a prior three-step clustering procedure.
- The normalized model: The noise model uses unit-norm x and i.i.d. Gaussian entries in z with variance σ^2/n.
- The normalized model: For presentation and proofs, the paper uses y = x + z with ∥x∥_ℓ2 = 1 rather than ∥y∥_ℓ2 = 1.The numerical section instead uses the observed-data normalization.
- The normalized model: The paper states that methods and theoretical results hold under either clean-point or observed-point unit-norm normalization.
- Prior procedure: A prior approach constructs a similarity matrix and weighted graph, applies spectral clustering, and fits each resulting cluster with PCA.
2.2. The SSC scheme.
The SSC scheme builds sparse representations among data points, converts them into a similarity graph, clusters the graph spectrally, and fits subspaces with PCA. Robustness is needed because noisy data corrupt both the covariates and response vectors.
- Clustering and fitting: Spectral clustering is applied to the graph G to form clusters, followed by PCA on each cluster.
- Sparse representations: SSC represents each clean point x_i as a sparse linear combination of the other columns of X using ℓ1-minimization.The constraint β_i = 0 removes the trivial self-representation.
- Robust SSC procedure: The robust procedure regresses each noisy vector y_i onto the other columns of Y to produce sparse coefficients collected in B.
- Graph construction: The coefficient matrix B defines graph edge weights through W_ij = |B_ij| + |B_ji|.This symmetrizes the directed sparse representations into a similarity graph.
- Subspace variants: For linear subspaces, the method uses the similarity graph directly; affine subspaces can be handled by adding the constraint β^T 1 = 1.
- Robustness motivation: The noisy-data setting is challenging because both the covariate columns and the response vector are corrupted, so noiseless sparse representations may no longer apply directly.
2.3. Performance metrics for similarity measures.
The paper evaluates similarity measures by distinguishing true discoveries from false discoveries and by testing whether the resulting affinity matrix supports reliable clustering.
- A false discovery links two points from different subspaces when the corresponding affinity entry is nonzero.
- A true discovery is a nonzero affinity linking two points from the same cluster or subspace.
- The subspace detection property holds when there are no false discoveries.Then B becomes block diagonal after permuting columns so that points from each subspace are contiguous.
- The LASSO constructs similarity information by seeking sparse representations of each point while setting its own coefficient to zero.
2.4. LASSO with data-driven regularization.
The paper selects LASSO regularization to balance avoiding false discoveries against retaining roughly a subspace-dimension-sized number of true discoveries, then estimates the unknown dimension data-dependently. Experiments and theory support this strategy for noisy subspace clustering under stated separation and sampling conditions.
- Motivation: Noisy responses and covariates make LASSO-based subspace clustering theoretically unclear, motivating data-driven selection of λ.
- Regularization principle: In the noiseless model, the optimal solution has exactly d nonzero coefficients when false discoveries are absent.Thus, a point from a d-dimensional subspace obtains d neighbors with probability one.
- Regularization principle: The selection rule takes λ as large as possible to prevent false discoveries while retaining roughly 0.5d–0.8d true discoveries.
- Data-driven procedure: Because d is unknown, the procedure estimates it from the ℓ1 norm of a fitted coefficient sequence before constructing λ.
- Scope: The paper leaves a precise asymptotic relationship between λ and expected true discoveries for future work and studies it numerically instead.
- Empirical behavior: λ on the order of 1/d yields a fixed fraction of true discoveries, empirically around 50% at λo and 75% near λo/2.
- Scope: The same λ scaling typically gives few false discoveries and many true discoveries when subspaces are not very close.
- Empirical behavior: At λ near λo, experiments report zero false discoveries and approximately d/2 true discoveries, making it an attractive FPR–TPR trade-off.
3. Theoretical results.
The theoretical analysis gives high-probability guarantees for the algorithm’s first step under affinity, sampling, and bounded-noise conditions. It establishes no false discoveries alongside many true discoveries, including when subspaces have substantial intersections, while complete clustering guarantees remain open.
- Assumptions: The analysis assumes affinity and sampling conditions, with bounded noise; higher noise requires a stricter affinity condition.The stated affinity condition omits σ only because the main theory assumes bounded noise.
- Main guarantees: With τ = 2σ and f(t) ≥ 0.707σt^-1, Algorithm 2 makes no false discoveries with high probability.This guarantee applies to each column whose subspace satisfies the affinity and sampling conditions.
- Main guarantees: With f(t) ≤ α0t^-1, the procedure makes at least a dimension-over-log-density number of true discoveries with high probability.Theorem 3.2 states that this quantity remains roughly on the same order as in the noiseless case when noise is sufficiently small.
- Subspace orientation: The guarantees allow subspaces with intersections whose dimension grows almost linearly with subspace dimension, unlike earlier conditions requiring near-orthogonality.The comparison concerns average versus maximum cosine conditions on principal angles.
- Sampling density: When sampling density grows exponentially with subspace dimension, the number of true discoveries can shrink to about one because tightly packed points need fewer columns for synthesis.The theory excludes exponentially growing density as a proviso, while noting that this regime makes the problem especially easy.
- Scope of guarantees: The theory rigorously analyzes only the first algorithmic step; proving connectivity of each within-subspace similarity graph is left as an unresolved challenge.The authors argue that enough true discoveries should make the induced graphs well connected, but do not prove this because of algorithm-generated dependencies.
4. The bias-corrected Dantzig selector.
The bias-corrected Dantzig selector modifies sparse regression to account for corrupted design data, using a variance-based constraint parameter. Simulations show strong discovery performance, with tuning around 4–6 times the heuristic λo and advantages over the two-step procedure for small subspaces.
- The correction: The corrected Dantzig selector adapts sparse regression to corrupted design matrices, but the paper does not claim theoretical guarantees for this alternative method.Its properties are explored on real and simulated data instead.
- The correction: The procedure seeks a formulation in which the ideal noiseless solution βI remains feasible despite corrupted observations.The construction uses a variance calculation for the constraint and selects λ as a reasonable multiple of the resulting scale.
- The correction: The bias-corrected constraint produces a λ parameter that does not depend on the dimension of the underlying subspace.The resulting formulation is called the bias-corrected Dantzig selector.
- Numerical behavior: Factors between 4 and 6 times the heuristic λo yield good results in the running-example simulations.Figure 6 evaluates performance for λ values ranging from λo to 8λo.
- Numerical behavior: The simulations yield many true discoveries and few false discoveries, while the corrected selector finds more true discoveries than the two-step procedure for small-dimensional subspaces.For large-dimensional subspaces, the two methods are essentially the same; real-data experiments require λ values much larger than λo for good corrected-selector results.
5. Comparisons with other works.
Existing subspace-clustering methods differ in tractability, robustness, and parameter dependence. The paper positions its approach against algebraic, iterative, statistical, spectral, and corrupted-covariate methods using these criteria.
- Comparison criteria: The comparison is organized around tractability, provable robustness to noise, and efficiency near limits determined by samples per subspace and subspace affinity.These criteria frame how many points are needed and how close subspaces may be.
- Method families: Existing methods span algebraic, iterative, statistical, and spectral-clustering-based categories.The paper uses these categories to organize its discussion of related approaches.
- Algebraic methods: GPCA has favorable parameter dependence but is not tractable in subspace dimension and is not robust to noise without added heuristics.A semidefinite-programming variant improves robustness but remains intractable in subspace dimension.
- Iterative methods: K-subspace methods formulate clustering as a nonconvex optimization over subspace bases and segmentation variables, optimized iteratively.This makes their procedure distinct from the paper’s tractable sparse-regression perspective.
- Statistical methods: Statistical approaches model the task with mixtures of degenerate Gaussian observations, including MPPCA and agglomerative lossy compression.MPPCA uses an expectation–maximization-style procedure, while ALC minimizes required code length.
- Spectral methods: Spectral alternatives include SCC, LRR, and Grassmanian optimization, but their tractability, robustness, or parameter dependence remains limited or incompletely understood.SCC is intractable in subspace dimension, LRR lacks understood robustness and parameter dependence, and Grassmanian optimization is nonconvex.
- Parameter dependence: The paper’s theory requires only ρ ≥ ρ⋆ for a fixed numerical constant, contrasting with prior requirements that may grow super-polynomially with subspace dimension.The cited prior bounds can also worsen as dimension and the number of subspaces increase.
- Corrupted covariates: Unlike related corrupted-covariate studies, the paper claims unmodified LASSO can be robust, under substantially different assumptions on uncorrupted covariates.The comparison distinguishes the paper’s modeling assumptions from i.i.d.-row and restricted-eigenvalue settings.
6. Numerical experiments.
The experiments evaluate robust subspace-clustering procedures on synthetic and motion-capture data, where activities form approximately low-dimensional subspaces. Robust SSC variants are compared with a nearest-neighbor baseline using clustering error.
- Experimental setup: Motion-capture experiments segment sensor measurements so that each cluster corresponds to one human activity.Trials 2 and 5 contain eight and seven activities, respectively, making them harder examples.
- Experimental setup: The CMU activity data exhibit low-dimensional structure, as singular-value curves for walking, jumping, and drinking show low-dimensional knees.The ambient dimension is n = 42.
- Methods and evaluation: The comparison evaluates a K-nearest-neighbor baseline, the two-step procedure, and the bias-corrected Dantzig selector by clustering error.The number of subspaces is assumed known before spectral clustering.
- Baseline results: 17.06% and 12.47% are the minimum baseline clustering errors for trials 2 and 5, respectively, after optimizing the temperature parameter for each K.Baseline similarities use an exponential function of Euclidean distance for connected neighbors.
- Robust-method results: Robust SSC variants achieve significantly lower errors than the baseline across a wide parameter range, with the two-step procedure slightly better on the two real-data examples.The two-step error is especially insensitive to σ around λ = λo; the baseline struggles because nearby points can belong to different subspaces.
- Robust-method results: The two trials have subspace affinities above 0.75, indicating that the motion-capture subspaces are highly similar.Affinities are estimated after fitting each group with the smallest dimension capturing at least 90% of its singular-value sum.
7. Discussion and open problems.
The discussion emphasizes robust SSC’s theoretical reach in difficult regimes while identifying unresolved questions about noise limits, deterministic models, clustering guarantees, and parameter selection.
- Main conclusions: Robust SSC is provably tractable even when subspaces overlap along many dimensions and each subspace has relatively few points.Its performance results are expressed using interpretable parameters.
- Open problems: The discussion identifies the maximum allowable noise level as an open question, despite robust SSC accommodating noise levels σ of order one near information-theoretic affinity and sampling limits.The unresolved issue is a fundamental limit for any algorithm, not only tractable ones.
- Open problems: Extending the theory to deterministic subspace orientations and noiseless samples remains future work.The current discussion proposes a future publication for this extension.
- Open problems: The theoretical analysis covers similarity-matrix construction and sparse regression correctness, while guarantees for the subsequent clustering cleanup step remain open.The discussion points to a formulation in as a potential approach.
- Connections: The paper’s data-driven formulation regresses each point against all others, connecting it to related factorization approaches such as nonnegative matrix factorization.The discussion notes a convex formulation similar to SSC in those problems.
SUPPLEMENTARY MATERIAL
The supplement contains proofs for all results developed in the paper.
- Supplementary material: The supplementary material provides proofs of all the paper’s results.It is identified as a separate proofs PDF.