PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Subspace Clustering via Thresholding

Reinhard Heckel, Helmut Bölcskei

arXiv:1307.4891v4stat.MLcs.ITcs.LG

TL;DR

The paper studies clustering noisy and incompletely observed data drawn from unknown low-dimensional subspaces with outliers. It proposes TSC, which thresholds correlations to build a spherical-nearest-neighbor graph for spectral clustering, and proves robustness under noise, missing entries, and intersecting subspaces. The results also provide an affinity–noise tradeoff and an outlier-detection scheme.

  • Problem

    The problem is clustering noisy, incompletely observed high-dimensional points into unknown subspaces and outliers when the number, dimensions, and orientations are unknown.

  • Method

    TSC thresholds correlations to select spherical-distance nearest neighbors, constructs an adjacency matrix, and applies normalized spectral clustering.

  • Results

    TSC provably succeeds under additive noise and incomplete observations when subspaces are sufficiently distinct and sufficiently sampled, with noiseless guarantees of zero clustering error.

  • Takeaways & Limitations

    The analysis supports robustness to intersecting subspaces, relates tolerable noise to subspace affinity, permits missing entries nearly linear in ambient dimension up to a logarithmic factor, and includes provable outlier detection.

  • Takeaways & Limitations

    The noisy-case theorem guarantees absence of false connections rather than zero clustering error, and the noiseless theorem has a constant exponentially dependent on maximum subspace dimension.

Abstract

from arXiv · show

The problem of clustering noisy and incompletely observed high-dimensional data points into a union of low-dimensional subspaces and a set of outliers is considered. The number of subspaces, their dimensions, and their orientations are assumed unknown. We propose a simple low-complexity subspace clustering algorithm, which applies spectral clustering to an adjacency matrix obtained by thresholding the correlations between data points. In other words, the adjacency matrix is constructed from the nearest neighbors of each data point in spherical distance. A statistical performance analysis shows that the algorithm exhibits robustness to additive noise and succeeds even when the subspaces intersect. Specifically, our results reveal an explicit tradeoff between the affinity of the subspaces and the tolerable noise level. We furthermore prove that the algorithm succeeds even when the data points are incompletely observed with the number of missing entries allowed to be (up to a log-factor) linear in the ambient dimension. We also propose a simple scheme that provably detects outliers, and we present numerical results on real and synthetic data.

1 Introduction

The paper addresses clustering high-dimensional noisy data into unknown low-dimensional subspaces and outliers. It introduces TSC and establishes guarantees for noisy, incomplete, and intersecting-subspace settings.

  • Motivation: High-dimensional data often has low-dimensional structure, motivating subspace clustering for applications such as face images.Images of a given face under varying illumination approximately lie in a 9-dimensional linear subspace.
  • Problem: The task is to assign noisy data points to unknown subspaces and outliers when their number, dimensions, and orientations are unknown.Once assignments are found, PCA can estimate the underlying subspaces.
  • Contribution: TSC applies spectral clustering to an adjacency matrix formed by thresholding correlations and selecting nearest neighbors in spherical distance.The method is presented as simple and computationally efficient.
  • Guarantees: TSC provably succeeds under additive Gaussian noise or incomplete observations when subspaces are sufficiently distinct and each contains enough points.In noisy and incomplete settings, the guarantee concerns absence of false connections rather than clustering error directly.
  • Guarantees: In the noiseless case, the analysis guarantees zero clustering error under stated sampling and graph-connectivity conditions.The result is stronger than merely guaranteeing no false connections.
  • Extensions: The paper further reports a tradeoff between subspace orientation and tolerable noise, allows missing entries nearly linear in ambient dimension up to logarithmic factors, and proposes outlier detection.Experiments use synthetic data, MNIST digits, and extended Yale Face Database B images.

2 The TSC algorithm

TSC builds a sparse similarity graph from spherical-distance nearest neighbors, then applies normalized spectral clustering. Its graph structure supports subspace-separating guarantees, while parameter choices balance connectivity against false connections.

  • Algorithm: TSC assumes normalized data and uses an input estimate of the number of subspaces together with a neighborhood parameter q.Outliers are assumed removed before applying the algorithm.
  • Algorithm: It assigns exponentially transformed similarity weights to selected neighbors, symmetrizes them into A = Z + Z^T, and applies normalized spectral clustering.Unselected pairs receive zero weight.
  • Algorithm: For each point, TSC selects q neighbors with the largest absolute correlations, equivalently the nearest points under arccos(|⟨x_i,x_j⟩|).This spherical distance treats antipodal points as equivalent.
  • Parameter tradeoff: Choosing q too small can split a subspace into components, whereas choosing it too large increases cross-subspace connections.The analytical guarantees tolerate a range of q values, although practical performance still depends on the choice.
  • Graph properties: When subspaces are orthogonal and q ≤ min_ℓ(|X_ℓ| − d_ℓ), the graph has no false connections under the stated noiseless sampling setting.Cross-subspace inner products vanish, while sufficiently many within-subspace inner products remain nonzero.
  • LS-TSC: LS-TSC changes the weighting step to use least-squares coefficients while retaining the same graph-connectivity guarantees.Edge weights can affect practical spectral-clustering performance even when analytical results depend only on connectivity.
  • Estimating the number of subspaces: The number of subspaces can be estimated from the normalized Laplacian using the eigengap heuristic when cross-subspace weights are small but nonzero.Exactly zero eigenvalues equal the number of connected components, while small eigenvalues motivate the eigengap heuristic.

3 Performance results for the noiseless case

For noiseless data, TSC achieves exact clustering under affinity, sampling, and neighborhood-size conditions, including intersecting subspaces through a weaker affinity measure. Its guarantees also show dimension-independent behavior and clarify the tradeoff between connectivity and false connections.

  • Affinity conditions: Subspace affinity is bounded by 1, and any nontrivial intersection forces aff_infinity(S_k, S_l)=1, explaining why the intersecting-subspace theorem uses aff instead.The two affinity notions are related to the principal angles between subspaces.
  • Theorem 1: TSC’s exact-segmentation guarantees assume uniformly sampled points on each subspace and constrain q between logarithmic and linear-scale bounds.The lower bound supports connectivity, while the upper bound prevents false connections.
  • Theorem 1: When subspaces do not intersect and each contains sufficiently many points, TSC correctly segments the data with high probability.The success probability increases as the number of points per subspace grows, including regimes where subspace counts and sample sizes scale differently.
  • Graph construction: The graph proof balances q: larger values improve connectivity, whereas excessive values increase cross-subspace connections and can violate the no-false-connections property.Normalized spectral clustering then recovers the connected components when they correspond to the true subspaces.
  • Theorem 2: For intersecting subspaces, TSC still achieves exact segmentation under a condition expressed with aff(S_k, S_l), although the required affinity condition becomes stricter as the total sample size increases.The stricter condition reflects the increased chance that some sampled point lies near an intersection.
  • Dimension dependence: TSC can avoid false connections without requiring a relation between sample counts and subspace dimensions, even allowing sample counts linear in dimension.Its nearest-neighbor premise depends on sufficiently small inter-subspace affinity rather than local neighborhoods in the ambient metric.

4 Impact of noise

The analysis shows that TSC remains robust to additive Gaussian noise when subspace orientations are sufficiently distinct and dimensions are small relative to the ambient dimension. In the noisy setting, the guarantee concerns absence of false connections rather than clustering error directly.

  • Guarantee: Unlike the noiseless results, the noisy theorem guarantees no false connections but does not directly guarantee zero clustering error.The graph property ensures that connected edges do not link different subspaces, but it is weaker than correct clustering of every point.
  • Noise robustness: TSC succeeds under additive Gaussian noise when subspace orientations are sufficiently distinct and each subspace has enough sampled points.The noisy-data guarantee uses absence of false connections as its performance measure.
  • Noise robustness: Greater separation between subspace orientations increases the noise level TSC can tolerate.The condition explicitly links subspace affinity to tolerable noise.
  • Noise robustness: Even massive noise is tolerable when subspace dimensions are sufficiently small relative to the ambient dimension.This conclusion follows from the dependence on dmax/m in the noisy-case condition.

5 Incomplete data

For randomly oriented subspaces and random points, TSC remains successful with arbitrary missing entries in the data vectors. The allowed number of missing entries can be linear in the ambient dimension up to a logarithmic factor.

  • Model and guarantee: TSC succeeds with high probability when each data vector has up to s arbitrary unobserved entries under a random-subspace model.The theorem sets the unobserved entries to zero and guarantees no false connections under its sampling and parameter conditions.
  • Missingness tolerance: The number of missing entries per data vector may be linear in the ambient dimension up to a logarithmic factor.This is the principal incomplete-data robustness conclusion.
  • Scope: The result can also cover subspace dimensions linear in the ambient dimension, but random subspaces are then approximately pairwise orthogonal.Thus the high-dimensional guarantee occurs in a model with affinities close to zero.

6 Outlier detection

The paper detects outliers by thresholding each point’s maximum inner product with the rest of the data. Under uniform spherical models, this rule detects all outliers without misclassifying inliers with high probability, including under massive noise.

  • Noiseless case: The outlier model treats outliers as uniform random points on the ambient unit sphere, while inliers are uniform on their corresponding subspace spheres.The noiseless analysis assumes independent sampling across subspaces and outliers.
  • Detection rule: The rule classifies a point as an outlier when its maximum inner product with all other points is sufficiently small.Equivalently, it identifies points whose spherical distance to every other point is large.
  • Noiseless case: Under the theorem’s conditions, all outliers are detected and no inlier is misclassified with high probability, without assumptions on subspace orientations.The guarantee requires enough points from each subspace and permits the number of outliers to be exponential in m/dmax.
  • Noisy case: Under additive Gaussian noise, outlier detection can still succeed when dmax/m is sufficiently small.The noisy outlier model uses Gaussian outliers and normalizes the noisy data points.

7 Comparison with SSC/RSSC and other algorithms

Compared with SSC and RSSC, TSC uses a local nearest-neighbor criterion rather than global sparse representation. This reduces computational demands while retaining analytical guarantees that are structurally similar to those of SSC and RSSC.

  • Comparison with SSC/RSSC: TSC builds its adjacency matrix from local inner-product comparisons, whereas SSC and RSSC use global sparse representations through ℓ1-minimization or Lasso.The local criterion makes TSC computationally much less demanding.
  • Analytical guarantees: TSC’s noiseless clustering condition is identical to SSC’s corresponding condition up to constants and logarithmic factors.The TSC theorem additionally guarantees zero clustering error rather than only no false connections.
  • Analytical guarantees: In the noisy case, TSC and RSSC have corresponding conditions that are identical up to constants and logarithmic factors, with different noise-factor assumptions.RSSC requires bounded σ, whereas TSC does not require that assumption.
  • Outlier robustness: For both TSC and RSSC, the number of outliers can be exponential in m/dmax and success probability increases with the number of points per subspace.The comparison also notes that the per-subspace sample counts can be linear in the subspace dimensions.
  • Parameter selection: TSC requires an input parameter q, although a data-driven variant provides performance guarantees essentially equivalent to the reported results.RSSC instead chooses its Lasso regularization parameter in a data-driven fashion.

8 Numerical results

The numerical experiments evaluate TSC using clustering, subspace-number, and false-connection errors across intersecting, incomplete, noisy, and real data settings. TSC remains effective under substantial intersections, missing entries, and noise, while its performance on faces depends on preprocessing and comparison method.

  • Intersecting subspaces: CE stays close to zero when the intersection dimension of two 10-dimensional subspaces is not too large.The experiment averages CE, EL, and FDE over 100 problem instances.
  • Incomplete data: TSC succeeds with a large fraction of missing entries in data vectors, including six subspaces of R50 with pairwise affinity at least 1/3.Figure 4 varies subspace dimension, sample count, and the number of missing entries.
  • Additive noise: TSC succeeds under large noise variance and under massive noise when d/m is sufficiently small.For L = 5 subspaces in R400 with d = 5, d/m = 1/80, the results confirm Theorem 3’s predictions.
  • Handwritten digits: For MNIST, SSC performs better with few images per digit, whereas TSC and LS-TSC outperform SSC with many images.The crossover occurs around n ≲80 versus n ≳80 images per digit; TSC also has significantly smaller FDE than SSC in the low-sample regime.
  • Face clustering: On Yale faces after preprocessing, TSC outperforms LSA, SCC, and LRR but remains worse than LatLRR, LRSC, and SSC in the reported comparisons.The preprocessing removes the first two principal components, and TSC remains computationally less demanding than the compared methods without preprocessing.

A.2 Proof of Lemma 2

The proof establishes connectivity of a nearest-neighbor graph for points sampled on the unit sphere by partitioning the sphere into equal-area regions and controlling local point counts. These bounds show that a logarithmic neighborhood size suffices with high probability.

  • Proof strategy: The proof partitions S^{d−1} into M equal-area regions of small spherical diameter and connects points through neighboring regions.Each region is required to contain at least one sampled point.
  • Connectivity conclusion: On the event that every region is occupied and every relevant cap has at most k points, the 2k-nearest-neighbor graph is connected.Each point connects to all points in neighboring regions, and this holds simultaneously for all sampled points.
  • Geometric control: For every point in a region, a spherical cap of radius 2θ⋆ contains all neighboring regions and lies inside a cap of radius 3θ⋆.This converts geometric containment into a bound on the number of nearest neighbors.
  • Probabilistic control: Choosing k = 3np and using binomial tail bounds controls the probability that any cap contains more than k points.The cap probability is p = L(C(cm, 3θ⋆))/L(S^{d−1}).
  • Final bound: The resulting failure-probability bound is at most 2 n^{γ−1}γ log n under the stated dimensional and sample-size conditions.The proof also verifies that 2k is bounded by a constant multiple of log n.

C Proof of Theorem 3

The proof of Theorem 3 bounds false connections and connectivity failures through separate probabilistic controls on inter-subspace affinities and within-subspace neighborhoods. Combining these bounds yields the theorem under the stated sampling and noise conditions.

  • Proof decomposition: The proof separates the probability of false connections from the probability that each within-subspace graph is connected.It denotes these events by NFC and C, respectively.
  • False-connection conclusion: Setting β = √6 log N and using the bounds for the three proof steps yields the desired lower bound for the graph having no false connections.The condition m ≥ 6 log N ensures β ≤ √m.
  • Conclusion: The theorem follows after the separate probability bounds are combined under the stated assumptions.The proof concludes by showing that the required inequalities are implied by condition (8).
  • Connectivity control: For the connectivity component, the proof bounds local-neighborhood events and then aggregates them over points using union bounds.The resulting estimates are established in Steps 1–3.
  • False-connection control: The analysis controls cross-subspace correlations by bounding the relevant random variables and applying union bounds over competing subspaces and points.The argument introduces parameters α, ϵ, and ν to control the threshold conditions.

D Proof of Theorem 4

The proof of Theorem 4 verifies the clustering condition for Gaussian subspace bases by showing that suitable restricted submatrices are approximately pairwise orthogonal. Concentration bounds and union bounds provide the required high-probability guarantee.

  • Reduction: The proof reduces Theorem 4 to showing that Gaussian subspace matrices satisfy the clustering condition with high probability.The key property is approximate pairwise orthogonality of certain submatrices.
  • Parameter choice: Choosing δ from the theorem constants yields the required inequality 2δ m/(m − 2s) ≤ c1 < 1.This verifies the clustering condition after applying the restricted-matrix lemma.
  • Conclusion: Theorem 4 then follows with probability at least 1 − 4e^{−c′m}.The conclusion uses the high-probability matrix property together with the earlier clustering lemma.
  • Concentration argument: The argument applies a concentration lemma to normalized Gaussian submatrices and uses a union bound over subspace pairs and deleted-row sets.The construction rescales the surviving rows before applying the concentration result.

E Proof of Theorem 5

The proof of Theorem 5 analyzes the outlier detector in two directions: failing to detect true outliers and incorrectly labeling inliers as outliers. Union bounds then yield separate error guarantees for both events.

  • Proof structure: The proof first bounds the probability that the detector misses one or more outliers, then bounds the probability that it misclassifies one or more inliers.These are the two statements established by Theorem 5.
  • Outlier misses: For a given outlier, violating the detection threshold is bounded using a union bound and the unit-norm assumption.Aggregating over all N0 outliers bounds the probability of missing at least one.
  • Outlier misses: The probability that the scheme fails to detect one or more outliers is at most 2N0/N^2.This is the result after taking the union bound over all outliers.
  • False outlier labels: For an inlier, the proof bounds the probability of satisfying the outlier condition and then aggregates over all inliers in each subspace.The argument uses condition (11) to control the threshold scale.

F Proof of Theorem 6

The proof establishes outlier-detection guarantees by separately bounding failures for outliers and inliers, then applying union bounds under conditions ensuring β ≤ √m. It also handles additive noise through more technical probability bounds.

  • Proof structure: The additive-noise proof follows the structure of the proof of Theorem 5, but its individual steps are more technical because of the noise term.The proof also resolves the required condition by showing it follows from assumption (13).
  • Outlier detection analysis: The proof separately bounds the probability of failing to detect a given outlier and of misclassifying a given inlier.The outlier analysis uses Gaussian inner-product bounds, while the inlier analysis is handled separately before union bounds are applied.
  • Parameter conditions: β = √6 log N is used in the outlier analysis, with β ≤ √m ensured under the stated assumption.The proof verifies this condition by choosing c1 ≤ 1/6 and invoking the bound on m.
  • Probability bounds: The outlier-failure bound combines separate estimates for Gaussian inner products and cases where the comparison point is an inlier or an outlier.These estimates are combined in the final bound for violation of the outlier-detection condition.
  • Union bounds: A union bound over all inliers in X_ℓ bounds the probability that one or more inliers are misclassified as outliers.The proof then uses a union bound over all N0 outliers to obtain the corresponding overall result.

G Supplementary results

The supplementary section collects standard concentration tools used throughout the paper, including Gaussian tail bounds, Lipschitz concentration, norm concentration, and spherical inner-product bounds.

  • Gaussian concentration: The paper summarizes a standard Gaussian tail bound for a scalar normal random variable.This result is introduced as a frequently used tool in the paper.
  • Gaussian concentration: A Lipschitz concentration theorem gives a tail bound for functions of a standard Gaussian vector.The theorem applies to functions with a specified Lipschitz constant.
  • Gaussian concentration: Applying the Lipschitz theorem to f(x) = ∥x∥2 yields a concentration result for the Euclidean norm of a Gaussian vector.The application uses Lipschitz constant L = 1 and Jensen’s inequality.
  • Spherical concentration: A proposition provides a tail bound for the inner product between a uniformly distributed point on the sphere S^{m−1} and a fixed vector.The result is stated for β ≥ 0.
Loading 1307.4891v4…