A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-reduced Data

Yining Wang, Yu-Xiang Wang, Aarti SinghICML 2015 · OpenReview

Subspace clustering is a cornerstone of modern machine learning, used for everything from facial recognition to identifying motion in video. The core idea is simple: high-dimensional data points often do not just float randomly in space; instead, they cluster around low-dimensional "flats" or subspaces. The gold standard for finding these clusters is Sparse Subspace Clustering (SSC).

However, SSC has a "big data" problem. As dimensions grow, the underlying optimization becomes computationally grueling. While researchers often use dimensionality reduction techniques—like random projections—to speed things up, the field has lacked a solid theoretical guarantee that the clustering results remain valid after compression, especially when the data is noisy or needs to stay private. A recent paper from Carnegie Mellon University provides that missing link.

TL;DR

The authors provide a new deterministic framework proving that Sparse Subspace Clustering (SSC) remains accurate even after data is aggressively compressed via random projections. Their analysis shows that SSC is robust to both adversarial noise and stochastic errors in this reduced space, paving the way for the first privacy-preserving subspace clustering algorithms.

The Problem: The Curse of Dimensionality

Running SSC on high-dimensional raw data, such as high-resolution images or genomic sequences, is often inefficient or outright impossible. To cope, practitioners typically project data into a lower-dimensional space before clustering.

While this works well in practice, the theoretical justification has been lagging. Previous proofs of SSC's success often relied on "semi-random" models, assuming data points or subspaces are distributed nicely and uniformly. Real-world data is rarely that polite; it is often deterministic, noisy, or even maliciously perturbed. The authors set out to prove that SSC works on dimensionality-reduced data under the most general, "fully deterministic" settings.

Methods: Analyzing Lasso SSC

The paper focuses on the Lasso version of SSC, which is better suited for noisy data than the original "exact" version. The workflow they analyze follows four steps:

  1. Compress: Project the high-dimensional data matrix $X$ into a lower dimension $p$ using a projection matrix $\Psi$ (e.g., a Gaussian matrix).
  2. Normalize: Ensure the projected columns have unit norm.
  3. Solve Lasso: For each point, find a sparse representation using other points in the reduced space.
  4. Cluster: Build a similarity graph and use spectral clustering to find the groups.

The core of their technical contribution is showing that these projections act as subspace embeddings. This means the projection preserves the "two-norm" (the length) of any vector within the low-rank subspaces. By bounding how much the "dual directions" of the optimization problem shift after projection, they prove that the Self-Expressiveness Property (SEP)—the idea that a point is only represented by others in its own cluster—is maintained.

Key Insights and Ideas

  • Intrinsic Rank vs. Ambient Dimension: The most important takeaway is that the required dimension after compression ($p$) depends on the intrinsic rank ($r$) of the subspaces, not the original high dimension ($d$). You can squash data significantly as long as you respect the underlying complexity of the clusters.
  • The Geometric Gap: The success of SSC depends on the "gap" between subspace incoherence (how distinct the different subspaces are) and the inradius (how well-distributed the points are within a subspace). The authors show this gap is approximately preserved under projection.
  • Privacy as a Side Effect: Random projections naturally provide a level of "differential privacy." By adding a bit of Gaussian noise to the projected data, the authors show you can protect individual data attributes while still achieving near-perfect clustering.
  • Deterministic Robustness: Unlike previous work, this analysis holds even if an adversary chooses the worst possible data points, provided they still roughly fit the subspace model.

Key Results

The authors validated their theory using classic computer vision benchmarks, including the Extended Yale Face B dataset and Hopkins-155. They provided a concrete upper bound on the projection error that ensures SSC will still succeed.

Clustering error of SSC compared to LRR and TSC across reduced dimensions.

In experiments on the Yale Face B dataset, Lasso SSC significantly outperformed other popular methods like Low Rank Representation (LRR) and Threshold-based Subspace Clustering (TSC) when the projection dimension was small. Furthermore, the paper quantifies exactly how much noise (stochastic or adversarial) the system can handle before the "geometric gap" closes and clustering fails.

Limitations and Future Work

While the paper makes a huge leap in privacy-preserving clustering, the authors note a limitation: their current privacy results apply to attribute-level privacy (protecting specific entries in the data matrix). Achieving column-level privacy (protecting an entire individual's data point) while maintaining high clustering accuracy remains an open challenge.

Heatmap showing the effect of the regularization coefficient and reduced dimension on SEP violation.

Additionally, while the deterministic analysis is powerful, it requires the regularization parameter ($\lambda$) to be carefully tuned. As shown above, if $\lambda$ is too small, the "strong convexity" of the problem vanishes, making the results unstable and increasing SEP violations. Future work could look into more automated ways to find this "sweet spot" in compressed settings.

Summary updated

Abstract

Subspace clustering groups data into several lowrank subspaces. In this paper, we propose a theoretical framework to analyze a popular optimization-based algorithm, Sparse Subspace Clustering (SSC)...
BibTeX
@inproceedings{wang2015deterministic,
  author = {Yining Wang and Yu-Xiang Wang and Aarti Singh},
  title = {{A Deterministic Analysis of Noisy Sparse Subspace Clustering for Dimensionality-reduced Data}},
  booktitle = {International Conference on Machine Learning},
  year = {2015},
  url = {https://openreview.net/forum?id=H1ZzFnbObr},
}
Figure