PaperlayerView exact revision on arXiv

Source-linked AI summary

Noisy Sparse Subspace Clustering

Yu-Xiang Wang, Huan Xu

arXiv:1309.1233v2stat.ML

TL;DR

The paper asks whether SSC can provably recover subspaces when observations contain adversarial or random noise. It analyzes a modified LASSO-SSC formulation under deterministic and randomized models, showing exact recovery below geometric noise thresholds and strong tolerance in certain stochastic regimes. These results explain SSC’s empirical performance while identifying scope boundaries for robustness.

  • Problem

    Existing SSC theory largely assumed noiseless data, despite practical applications containing noisy or corrupted observations.

  • Method

    The paper develops a theoretical analysis of modified LASSO-SSC for deterministic data, random noise, and combined data-noise models.

  • Results

    LASSO-SSC exactly detects subspaces under deterministic noise thresholds and can tolerate noise much larger than the signal in stochastic settings.

  • Takeaways & Limitations

    The results provide theoretical justification for SSC on noisy real problems and guidelines for judging whether SSC may work in specific applications.

  • Takeaways & Limitations

    The paper’s robustness notion covers noise or arbitrary corruptions added to legitimate data, not outliers.

Abstract

from arXiv · show

This paper considers the problem of subspace clustering under noise. Specifically, we study the behavior of Sparse Subspace Clustering (SSC) when either adversarial or random noise is added to the unlabelled input data points, which are assumed to be in a union of low-dimensional subspaces. We show that a modified version of SSC is \emph{provably effective} in correctly identifying the underlying subspaces, even with noisy data. This extends theoretical guarantee of this algorithm to more practical settings and provides justification to the success of SSC in a class of real applications.

1. Introduction

Subspace clustering seeks to recover latent subspaces in high-dimensional data, while SSC’s practical success under noisy observations lacked theoretical explanation. This paper analyzes a modified SSC method and establishes exact recovery guarantees under noise.

  • Motivation: Subspace clustering groups high-dimensional data into their original low-dimensional subspaces, which can represent objects, people, subnets, users, or communities.Applications include motion trajectories, face images, network hop counts, movie ratings, and social graphs.
  • SSC: SSC represents each data point as a sparse linear combination of the remaining points using ℓ1 minimization.The desired representation uses points from the same subspace as the target.
  • Problem: Existing SSC analyses assumed data points lie exactly on subspaces, an assumption violated by perspective distortion, tracking errors, and pixel quantization.Motion trajectories, for example, are only approximately rank-4.
  • Contribution: The paper analyzes a modified SSC formulation for noisy or corrupted data and proves exact subspace-cluster recovery when noise remains below a geometric threshold.The threshold is determined by a gap between the inradius and subspace incoherence.
  • Contribution: The noisy analysis requires handling a noisy dictionary because SSC uses sample points as the sparse-recovery dictionary.This differs from prior noisy structure-recovery results that provide approximation or perturbation bounds.

2. Related works

Prior work established broad noiseless SSC guarantees, but noisy-data guarantees were scarce and often empirical. This paper extends geometric analysis to deterministic and randomized noisy settings and reports stronger noise-tolerance results in certain regimes.

  • Noiseless guarantees: Noiseless SSC guarantees progressed from disjoint subspaces to some overlapping subspaces through geometric conditions involving inradius r and incoherence µ.The geometric guarantee requires r − µ > 0.
  • Noiseless guarantees: The paper’s robust analysis inherits coverage of disjoint and overlapping subspaces from the preceding geometric SSC analysis.This extension is formalized in the paper’s later theoretical results.
  • Noisy guarantees: Previous noisy subspace-clustering studies were mostly empirical, although robust extensions of LRR and SSC relax hard equality constraints with penalty terms.Few methods had provable guarantees for noisy data at the time discussed.
  • Noise tolerance: In the semi-random model, the analysis handles noise much larger than the signal and improves on the compared SSC result under stated regimes.The paper also reports a stronger result when d ≤ O(√n), allowing signal-to-noise ratio to approach zero as ambient dimension grows.
  • Scope: The paper’s robustness notion excludes outliers and concerns only noise or arbitrary corruptions added to legitimate data.Outlier handling is treated as a different problem and is not directly comparable here.

3. Problem setup

The setup models normalized data from a union of subspaces with additive noise and studies a relaxed LASSO-based SSC formulation. Success is defined through same-subspace supports and a resulting block-diagonal affinity structure.

  • Data model: The uncorrupted matrix Y contains unit-norm columns drawn from a union of L subspaces, while observed data follow X = Y + Z.The noise matrix Z may be arbitrary.
  • SSC formulation: Original SSC solves a linear program for each point, assembles coefficient vectors into C, and applies spectral clustering to W = |C| + |C|^T.With nonzero noise, the original equality-constrained formulation may be infeasible.
  • SSC formulation: The noisy method uses an unconstrained LASSO formulation because standard SSC’s equality constraint can break down under noise.Although the formulation is standard LASSO, SSC analysis requires support-recovery conditions beyond conventional RIP or null-space guarantees.
  • Detection property: LASSO subspace detection requires each coefficient vector to be nonzero and supported only on samples from the target point’s subspace.The second requirement is called the Self-Expressiveness Property, or SEP.
  • Detection property: When the detection property holds, the coefficient and affinity matrices are exactly block diagonal with one disjoint block per subspace cluster.This property is stronger than what spectral clustering necessarily requires for perfect segmentation.
  • Caveat: The detection property is not sufficient for perfect segmentation because it does not ensure connectivity within each diagonal block.High-confidence connectivity remains an open problem except in nearly trivial independent-subspace cases.
  • Analysis models: The analysis provides sufficient conditions for LASSO subspace detection under four deterministic and randomized data-noise models.The models are fully deterministic, deterministic data with random noise, semi-random data with random noise, and fully random.

4. Main results

The paper develops geometric conditions under which modified SSC identifies subspaces despite deterministic or random noise. Its guarantees recover the noiseless condition, extend to overlapping subspaces, and include regimes where noise exceeds signal.

  • Geometric quantities: Projected dual directions are formed by projecting a dual solution onto the subspace and normalizing, with one direction associated with each data point.These directions support the projected subspace incoherence property used in the noisy analysis.
  • Geometric quantities: The inradius measures data dispersion: well-dispersed samples produce larger inradius, while concentrated samples produce smaller inradius.The inradius is the radius of the largest Euclidean ball inscribed in the relevant convex body.
  • Deterministic model: When noise vanishes, the condition reduces to µℓ < rℓ, matching the noiseless SSC guarantee, and unconstrained LASSO works for any λ > 1.Thus the noisy analysis specializes to the earlier noiseless result as δ = 0.
  • Randomized models: The guarantees cover overlapping subspaces and show only logarithmic dependence on the number of subspaces, while remaining sensitive to subspace dimension.The semi-random theorem expresses the result through subspace affinity and permits overlapping subspaces, even when they share a basis.
  • Deterministic model: Under deterministic noise, LASSO-SSC succeeds when noise is below a threshold determined by the geometric gap between inradius and subspace incoherence.A sufficient condition is δ ≤ O(r(rℓ−µℓ)), and the theorem guarantees a non-empty range of λ.
  • Randomized models: Random noise weakens the noise impact through concentration, enabling constant-level noise even when the geometric gap is as small as O(√(d/n)).Theorem 8 also establishes tolerance for noise significantly larger than the signal, with SNR potentially tending to 0 as ambient dimension grows.

5. Proof of the Deterministic Result

The deterministic proof establishes subspace-preserving recovery by analyzing an equivalent constrained problem, constructing a dual certificate, and enforcing separation and non-triviality conditions. Geometric bounds on projected dual variables yield sufficient noise and regularization conditions.

  • Proof strategy: The proof analyzes an equivalent constrained formulation of modified SSC and its dual, introducing slack variables for the noise.The dual program supplies the certificate framework used to prove subspace-preserving recovery.
  • Proof strategy: SEP is proved by constructing a dual certificate whose conditions ensure optimal coefficient supports remain within the correct subspace cluster.The argument organizes the proof around duality, certificate construction, and verification of the required inequalities.
  • Geometric bounds: Optimality restricts the dual solution more tightly than feasibility alone, placing it inside the intersection of the polar set and the ∥ν2∥ bound.The figures illustrate that the feasible polar region can allow very large ν2 values, whereas optimality yields a smaller region.
  • Geometric bounds: The projected dual variable is decomposed into components parallel and perpendicular to the current subspace, then bounded using polar-set geometry and circumradius–inradius relations.The proof bounds inner products with noisy points by separately controlling the projected components and the noise contribution.
  • Conditions for recovery: The resulting dual separation condition imposes a sufficient relationship among noise magnitude δ, regularization λ, and geometric structure, reducing to the noiseless condition when δ = 0.This condition is required across all subspaces and extends the geometric criterion based on inradius and incoherence.
  • Conditions for recovery: A separate optimal-value argument excludes the trivial solution, while the final admissible parameter condition is expressed through a non-empty inequality involving δ.The paper notes that the non-triviality bound improves its conference-version bound and supports stronger noise tolerance.

6. Proof of Results for Randomized Cases

The randomized-case proofs establish probabilistic bounds for dual separation and non-trivial solutions, then derive valid regularization ranges and sampling-based conditions for noisy SSC.

  • Randomized bounds: Gaussian noise properties and spherical-cap bounds control inner products, projected noise components, and incoherence terms in the randomized analyses.These ingredients support concentration and union-bound arguments for the randomized models.
  • Randomized bounds: The dual separation condition holds for all data points with probability at least 1−8/N under the random noise model when the stated conditions are satisfied.This result follows after probabilistically bounding the relevant cosine terms and noise magnitudes.
  • Non-triviality: The randomized proofs separately ensure that the LASSO solution is non-trivial with probability at least 1 −6/N2.This complements dual separation, which alone does not exclude the all-zero solution.
  • Parameter range: For random noise, the valid λ range expands to an order of Θ(1/r) ≤λ ≤Θ(r/(ϵ max{δ2, δ})) when µ is small.The range is obtained by substituting probabilistic bounds into the theorem’s inequalities.
  • Geometric conditions: Random-sampling lemmas bound the inradius and subspace incoherence, allowing these quantities to be substituted into the main noisy-SSC theorem.The inradius bound assumes κℓdℓ random samples per subspace, while the incoherence bound applies to deterministic subspaces with random sampling.

7. Experiments

Experiments evaluate LASSO-SSC under Gaussian noise using synthetic and face-clustering data. The results broadly confirm the theory: robustness depends strongly on subspace dimension and weakly on the number of subspaces.

  • Experimental setup: Four numerical experiments use ADMM-based LASSO-SSC, including three synthetic studies and one real Extended YaleB face-clustering study.The synthetic experiments vary noise magnitude, subspace rank, and number of subspaces.
  • Experimental setup: The simulations scan λ over an exponential grid and measure success with relative violation of the Self-Expressiveness Property, while also checking for trivial solutions.Data and subspaces are sampled uniformly and corrupted by Gaussian noise.
  • Synthetic experiments: Figure 8 shows a very large valid λ range, with noise dependence roughly 1/σ as predicted by the theory.Figures 10 and 11 additionally show sensitivity to subspace rank d and number of subspaces L.
  • Face experiments: Face experiments use rank-9 PCA representations and rank-3 robust-matrix-completion representations from Extended YaleB.The dataset contains 38 subjects with 64 illumination-varied images per subject.
  • Face experiments: The valid detection range is much larger for rank-3 than rank-9 faces, yet LASSO-SSC succeeds for both ranks under considerable noise across all 38 subjects.Recovery is reported as insensitive to the number of faces clustered.

8. Conclusion and Future Directions

The paper concludes that LASSO-SSC can exactly detect subspaces under noise and provides theoretical guidance for its practical use. It also identifies more application-relevant success measures as future work.

  • Conclusion: The analysis shows that LASSO-SSC exactly detects subspaces under noisy data, including deterministic data and noise.For stochastic noise, the paper reports operation even when noise is much larger than the signal.
  • Experimental scope: LASSO-SSC performance on real noise and data corruptions is documented in prior motion-segmentation experiments, whereas this study injects artificial noise in the face experiment.This distinguishes the experimental corruption model used here from previously documented real corruptions.
  • Conclusion: Robustness scales orderwise with noise level and subspace dimension, while remaining insensitive to the number of subspaces.These findings are presented as theoretical explanations for empirical success and guidance for practitioners.
  • Future directions: The paper notes that subspace detection is not necessary for perfect clustering, and perfect clustering itself may be unnecessary in applications allowing some misclassifications.It proposes stronger robustness guarantees under more practical success metrics as an open direction.

Appendix A. Differences to Soltanolkotabi et al. (2014)

The appendix contrasts this work with Soltanolkotabi et al. (2014) in assumptions, guarantees, parameter selection, and proof techniques, emphasizing complementary theoretical viewpoints.

  • Guarantees: This work gives weaker but more general non-triviality results because they do not require the semi-random assumption.The comparison contrasts merely requiring a non-zero coefficient with guaranteeing a constant fraction of non-zero coefficients.
  • Parameter selection: Unlike the compared two-pass adaptive procedure, this work proves guarantees for any λ in a specified range and permits independent tuning for each Lasso-SSC.The appendix advises choosing λ slightly above the threshold required for non-triviality.
  • Proof techniques: The proof bounds the out-of-subspace dual component without probabilistic assumptions, making the argument more general but looser than the semi-random comparison.The alternative relies on a restricted isometry property for each subspace’s data block.
  • Overall comparison: The authors describe the results as complementary to Soltanolkotabi et al. (2014), offering a novel viewpoint on theoretical subspace-clustering analysis.The appendix also notes a worse dependence on subspace dimension d in the specialized semi-random bound.

Appendix B. Numerical algorithm to solve Matrix-LASSO-SSC

This appendix presents a numerical procedure for solving Matrix-LASSO-SSC using ADMM, with alternating closed-form updates and a symmetrized affinity-matrix output. The matrix formulation is reported as faster than column-by-column ADMM-Lasso while achieving nearly the same numerical accuracy.

  • Optimization approach: ADMM is introduced to solve an equivalent Matrix-LASSO-SSC optimization program because general-purpose solvers are slow and non-scalable.The appendix describes the ADMM formulation for fast computation.
  • Optimization approach: The augmented Lagrangian adds a quadratic penalty for the equality constraint and alternates optimization over J, C, and Λ until convergence.Λ is the dual variable and µ is a parameter controlling the augmented-Lagrangian procedure.
  • Update rules: The J and C updates have closed-form solutions, with soft-thresholding used for the non-differentiable C update at the origin.The Λ update uses gradient descent, and the update equations arise from setting the relevant derivatives to zero.
  • Algorithm output: The algorithm initializes C, J, Λ, and k at zero, iterates until convergence, and outputs W = |C| + |C|T as the affinity matrix.Its inputs are data points in X, a tradeoff parameter λ, and numerical parameters µ0 and ρ.
  • Efficiency: For ρ = 1, the inverse of (λY^T Y + µI) can be precomputed, enabling linear-time iterations.Empirically, µ = λ worked well and convergence required roughly 50–100 iterations.
  • Efficiency: The matrix version is much faster than column-by-column ADMM-Lasso while attaining almost the same numerical accuracy.The comparison is referenced to experiments in Figures 14–17.
Loading 1309.1233v2…