Source-linked AI summary
A geometric analysis of subspace clustering with outliers
Mahdi Soltanolkotabi, Emmanuel J. Candés
TL;DR
The paper asks how to cluster unlabeled points near a union of unknown subspaces when their number and dimensions are unknown. It develops a geometric analysis of SSC and extensions, proving effectiveness for intersecting and nearly ambient-dimensional subspaces and for data with many outliers. The results are supported by theoretical guarantees and a numerical study.
Problem
Subspace clustering must group unlabeled points near multiple unknown subspaces without knowing the number or dimensions of those subspaces.
Method
The paper analyzes SSC geometrically across deterministic, semi-random, and fully random models and develops extensions for outlier-corrupted data.
Results
SSC is provably effective for intersecting subspaces, nearly ambient-dimensional subspaces, and data with outliers that can overwhelm the clean observations.
Takeaways & Limitations
The geometric analysis broadens the settings where SSC has provable guarantees and provides insights that may apply to other sparse recovery problems.
Takeaways & Limitations
The analysis leaves noisy subspace clustering to future work and identifies small-cluster regimes where separating outliers is inherently hard.
Abstract
from arXiv · showhide
This paper considers the problem of clustering a collection of unlabeled data points assumed to lie near a union of lower-dimensional planes. As is common in computer vision or unsupervised learning applications, we do not know in advance how many subspaces there are nor do we have any information about their dimensions. We develop a novel geometric analysis of an algorithm named sparse subspace clustering (SSC) [In IEEE Conference on Computer Vision and Pattern Recognition, 2009. CVPR 2009 (2009) 2790-2797. IEEE], which significantly broadens the range of problems where it is provably effective. For instance, we show that SSC can recover multiple subspaces, each of dimension comparable to the ambient dimension. We also prove that SSC can correctly cluster data points even when the subspaces of interest intersect. Further, we develop an extension of SSC that succeeds when the data set is corrupted with possibly overwhelmingly many outliers. Underlying our analysis are clear geometric insights, which may bear on other sparse recovery problems. A numerical study complements our theoretical analysis and demonstrates the effectiveness of these methods.
1. Introduction.
The paper studies clustering unlabeled data lying near a union of unknown subspaces and develops theory showing SSC works in broader settings, including intersecting and nearly high-dimensional subspaces.
- 1.1. Motivation.: Subspace clustering jointly groups unlabeled points and fits a low-dimensional subspace to each cluster when data lie near multiple subspaces.The paper frames this as an alternative to approximating all observations with one subspace.
- 1.3.2. Our contributions.: SSC can correctly cluster data from intersecting subspaces, including cases where the minimum principal angle vanishes.This broadens earlier analyses based on minimum-angle restrictions.
- 1.3.2. Our contributions.: Modifications to SSC succeed with many outliers, even when outliers far exceed the total number of clean observations.The analysis also identifies small-cluster regimes where separating outliers is inherently hard.
- 1.4.1. Models.: SSC is analyzed under deterministic, semi-random, and fully random models for subspace orientations and point distributions.The models differ in whether subspaces, points, or both are random.
- 1.3.2. Our contributions.: SSC can effectively cluster subspaces whose dimensions grow almost linearly with the ambient dimension in generic settings.The fully random analysis states that dimensions may be roughly linear in the ambient dimension.
- 1.4.2. Segmentation without outliers.: Theorem 1.2 establishes high-probability subspace detection for uniformly random subspaces and points under a dimension-dependent condition.For smaller dimensions, the paper states that the success probability is much higher than near the upper bound.
1. Solve
The paper’s outlier-detection procedure uses sparse representations to distinguish outliers from points lying in low-dimensional subspaces, then clusters the remaining points. Its analysis establishes reliable detection under both non-overwhelming and exponentially growing outlier populations.
- Detection rule: Sparse representations distinguish outliers because their expansions are expected to be less sparse than those of subspace points.The procedure solves an ℓ1-minimization problem for each point and thresholds the optimal value.
- Theoretical guarantees: Algorithm 2 detects all outliers when their number is not overwhelming.
- Theoretical guarantees: With high probability, Algorithm 2 detects all outliers when uniformly random spherical outliers satisfy the theorem’s numerical condition.The condition depends on the ambient dimension and the number of outliers, with c a numerical constant.
- Theoretical guarantees: For uniformly sampled points on arbitrary-orientation d-dimensional subspaces, the procedure avoids labeling subspace points as outliers under the stated condition.
- Theoretical guarantees: The stronger result permits all outliers to be detected even when their number grows exponentially in the root of the ambient dimension.This guarantee makes no assumptions about subspace orientations or point distributions; uniform sampling also prevents wrongful detection of subspace points.
2. Main results.
The paper develops geometric conditions under which SSC correctly detects subspaces, including intersecting subspaces, and extends the approach to outlier detection. The results relate success to subspace affinity, point distribution, sample size, and ambient dimension.
- The analysis uses dual points, dual directions, inradius, and subspace incoherence to characterize geometry relevant to SSC success.Inradius measures point spread, while incoherence measures affinity between subspaces; skewed point distributions can hinder ℓ1 synthesis.
- SSC’s subspace detection property ensures each point is represented only by points from its own subspace.
- SSC can correctly cluster uniformly sampled points when subspace affinity is below a threshold roughly proportional to the square root of subspace dimension.The guarantee allows subspaces to intersect, provided their affinity remains sufficiently small.
- The success probability improves with more points per subspace, while clustering becomes harder for many small-dimensional subspaces.The stated probability bounds depend on the number of subspaces, dimensions, and points sampled per subspace.
- The outlier scheme can detect all outliers with high probability even when their number grows exponentially in the root of the ambient dimension.Under uniform sampling on each subspace, the scheme does not wrongfully classify subspace points as outliers.
3. Discussion and comparison with other work.
The paper compares its SSC guarantees with prior conditions, showing less restrictive recovery regimes for intersecting subspaces, nearly linear dimensions, and large numbers of outliers.
- Deterministic model: SSC’s deterministic sufficient condition is less restrictive than the earlier comparison condition, while a tractable weaker condition can verify it.The paper notes that checking the main condition is NP-hard in general.
- Intersecting subspaces: For intersecting subspaces, the prior condition cannot hold, whereas the paper’s condition holds when the intersection is not too large or some angles are not too small.This explains why SSC can succeed even when subspaces are not disjoint.
- Fully random model: Theorem 1.2 allows subspace dimensions to be almost linear in the ambient dimension, extending the regime covered by the comparison result.The comparison is made under the fully random model.
- Geometric comparison: The paper’s geometric insight tests inner products between actual points on one subspace and dual directions on another, rather than all cross-subspace directions.This distinction underlies the broader recovery guarantees.
- Outliers: Prior subspace-recovery formulations may be nonconvex because their feasible set is the Grassmannian, whereas the proposed algorithm is convex and practical.The cited comparison concerns minimizing an ℓp-based functional over subspaces.
- Outliers: The proposed convex outlier-detection algorithm allows far more outliers than the compared approaches, sometimes exceeding the total number of inlier points.The paper contrasts this with methods whose outlier limits depend on ambient dimension or typical inlier counts.
4. Geometric perspective on the separation condition.
The paper recasts ℓ1 minimization and SSC’s separation condition geometrically using convex polytopes, polar sets, faces, and dual directions.
- 4.1. Linear programming theory: The geometric analysis uses K-norms and polar sets to understand the subspace detection property and the sufficient separation condition.The paper introduces these concepts as central tools for the analysis.
- 4.1. Linear programming theory: The dual linear program and strong duality connect the ℓ1 minimization value to a geometric norm defined by a symmetrized convex hull.The data matrix columns generate the polytope K = conv(±a1,...,±aN).
- 4.1. Linear programming theory: Support detection becomes identification of the face of K intersected by the ray through y; that face’s extreme points identify nonzero coefficients.This provides the geometric interpretation of the optimizer’s support.
- 4.2. A geometric view of the subspace detection property: When the detection property holds, the closest face associated with a point in a subspace lies within that same subspace.The construction considers the symmetrized convex hull of the other points in that subspace.
- 4.2. A geometric view of the subspace detection property: The sufficient condition restricts projections of points from other subspaces to regions determined by planes through the within-subspace face.If those points remain inside the relevant regions, the selected face lies in the target subspace.
- 4.2. A geometric view of the subspace detection property: Dual directions approximate the normal directions of the restricting planes, linking the geometric region test to the paper’s coherence condition.Figure 9 illustrates this relationship for a target subspace.
5. Numerical results.
Numerical experiments examine SSC’s error metrics, robustness to intersecting and closely aligned subspaces, subspace dimension, noise, spectral-gap estimation, and outlier detection.
- 5.1.1. Error metrics.: SSC’s feature detection error measures whether each point’s selected neighbors come from its own subspace, ranging from 0 for perfect detection to 1 for selecting other-subspace points.
- 5.1.1. Error metrics.: Clustering error is the fraction of misclassified points after spectral clustering, while number estimation uses a 0–1 error and the normalized-Laplacian spectral gap.
- 5.1.3. Effect of the affinity between subspaces.: At normalized affinity 0.9 and density ρ = 3.25, SSC correctly estimated the number of subspaces and achieved zero clustering error.Across experiments, sufficiently high point density enabled success even at large affinity.
- 5.1.5. Effect of noise on spectral gap.: With noise levels σ from 0 to 0.4, the spectral gap decreased as σ increased but remained detectable, and the number of subspaces was always correctly inferred.The subspace detection property did not hold even for noiseless data in this experimental regime.
- 5.1.6. Comparison with other methods.: SSC produced a wider eigenvalue gap than the classical method for d = 10, while for d = 30 only SSC produced a detectable gap in noisy and noiseless cases.The wider gap made number estimation more robust to noise in the d = 10 comparison.
- 5.2. Segmentation with outliers.: With as many outliers as data points, the optimal ℓ1 values were lower for data points than outliers; the conjectured threshold worked perfectly at d/n = 1/20.At d/n = 1/10, it detected all outliers but misclassified a few data points.
6. Background on Geometric Functional Analysis.
This section introduces geometric-functional-analysis concepts and inequalities used in the paper’s proofs, including norms, duality, convex bodies, and concentration results.
- The proofs rely heavily on techniques from Geometric Functional Analysis and introduce basic concepts and results from that field.
- Norms and measures: The maximal and average values of a norm on the sphere are introduced, with σ denoting the sphere’s uniform probability measure.
- Norms and measures: The mean width M*(K) is defined as the expected value of the dual norm over the unit sphere.
- Norms and measures: The section records the inequality M(K)M(K^o) ≥ 1, derived using the dual-norm relationship and Cauchy–Schwarz.
- Geometric tools: Additional tools include concentration of measure, properties of convex symmetric polytopes, Banach–Mazur distance, John’s theorem, and volume-ratio inequalities.
7. Proofs.
The proofs formulate SSC’s sparse-representation problem and its dual as linear programs, then use strong duality to connect their common optimum with a convex-geometric norm.
- The primal and dual optimization problems P(y,A) and D(y,A) are introduced as the central linear-programming formulations.
- Strong duality gives the primal and dual the same optimal value, denoted optval(y,A), with infeasible primal problems assigned value infinity.
- The common optimum equals the norm induced by the convex hull K(A) = conv(±a1,...,±aN), whose polar is described by an ℓ∞ constraint.
7.1. Proof of Theorem 2.5.
The proof of Theorem 2.5 establishes SSC’s subspace detection property by constructing dual certificates and reducing the required inequalities to a geometric condition involving convex bodies.
- For each point, the proof indexes same-subspace columns, constructs the required vectors, and verifies the certificate conditions for the associated primal problem.
- A standard dual-certificate lemma guarantees that every ℓ1-optimal representation uses support within a prescribed index set when a feasible certificate satisfies the stated conditions.
- The remaining verification requires an inequality for every point outside the target subspace, using the circumradius of a symmetric convex body and its polar’s inradius.
- The resulting inequality is precisely the sufficient condition in Theorem 2.5, completing the proof.
7.2. Proof of Theorem 2.8.
The proof establishes SSC’s subspace detection property by bounding inradii and subspace incoherence, then applying a probabilistic polytope lemma and concentration arguments.
- The proof develops a lower bound for inradii and an upper bound for subspace incoherence.
- Condition (2.2) in Theorem 2.8 makes the deterministic condition in Theorem 2.5 hold with high probability, yielding the subspace detection property.
- A random-polytope lemma lower bounds the inradius when uniformly sampled sphere points satisfy (1 + δ)d < N < d e^d/2.
- For sufficiently many points, specifically N > d(1 + δ0), the inradius bound holds under the lemma’s stated numerical condition.
- Uniform sampling makes dual directions uniformly distributed on each subspace, with uniqueness holding with probability 1.
- A Lipschitz concentration argument, spherical-cap bounds, and a union bound control the relevant random inner products.
7.3. Proof of Theorem 1.2.
The proof of Theorem 1.2 analyzes the fully random model through random inradius and incoherence bounds, combining spherical-cap estimates with a union bound.
- The proof again uses an inradius lower bound and develops an upper bound for subspace incoherence.
- In the fully random model, data columns and dual directions are uniformly distributed on their subspaces’ unit spheres, although the dual directions are not independent.
- Spherical-cap bounds control inner products between dual directions and points from other subspaces because the paired vectors are independent.
- Applying the union bound to at most N^2 pairs completes the incoherence step.
- The proof begins by introducing lemmas relating mean and maximal norms with respect to convex polytopes.
7.4. Proof of Theorem 2.9.
The proof of Theorem 2.9 derives norm bounds for convex polytopes and combines expectation, concentration, and union-bound arguments to obtain the theorem’s claims.
- The polytope argument uses dual norms, John’s lemma, and a face-count bound for the polar polytope.
- Sphere-volume estimates and Stirling’s approximation provide the needed dimensional bounds in the polytope analysis.
- The proof of the outlier-related part lower bounds optval(y,A) in expectation and then applies concentration to obtain a high-probability bound.
- The expectation and concentration lemmas, combined with a union bound, establish the first part of Theorem 2.9.
- The remaining arguments reuse the proof of Theorem 2.9(a) together with the inradius bound from Theorem 2.8.