Subspace clustering in high-dimensions: Phase transitions \& Statistical-to-Computational gap

Luca Pesce, Bruno Loureiro, Florent Krzakala, Lenka Zdeborová

Introduction

In high-dimensional machine learning, the "curse of dimensionality" often suggests that noise will inevitably overwhelm signal as the number of features grows. However, real-world datasets—ranging from genomic sequences to image libraries—frequently exhibit a property where only a small subset of dimensions is relevant to the underlying structure. This phenomenon is the basis for subspace clustering, where data points are organized into clusters defined by sparse centroids.

This research provides a rigorous asymptotic characterization of the subspace clustering landscape. By mapping the problem to a matrix factorization framework, the authors identify critical phase transitions and a significant "statistical-to-computational gap"—a regime where clustering is theoretically possible but remains computationally intractable for efficient algorithms.

Problem Formulation

The study models the data as a $k$-cluster Gaussian Mixture Model (GMM) with $s$-sparse centroids. To analyze the limits of recovery, the researchers transform the clustering task into an asymmetric matrix factorization problem defined by the equation:

$$X = \sqrt{\frac{\lambda}{s}} VU^\top + W$$

In this model, $X$ represents the observed data, $V$ and $U$ represent the cluster assignments and sparse centroids respectively, $W$ is additive Gaussian noise, and $\lambda$ represents the Signal-to-Noise Ratio (SNR). The goal is to determine the conditions under which the assignments $V$ can be recovered from $X$.

Methodology

The authors employ a multi-disciplinary approach drawing from statistical physics and information theory:

  1. Bayesian-Optimal Estimation: Using the "replica method" from statistical physics, they calculate the exact Information-Theoretic (IT) threshold—the absolute minimum SNR required for any method to outperform a random guess.
  2. Approximate Message Passing (AMP): The authors deploy a tailored AMP algorithm, which is conjectured to be the most powerful polynomial-time algorithm for this class of problems.
  3. State Evolution (SE): They use SE equations to track the performance of AMP in the high-dimensional limit, allowing for precise predictions of when the algorithm will succeed or fail.

The Three Phases of Clustering

The research identifies three distinct regimes in the clustering landscape based on the signal strength:

  • The Impossible Phase: The SNR is too low for any method, regardless of computational power, to recover the cluster assignments better than a random guess.
  • The Hard Phase: A regime where the signal exists and reconstruction is theoretically possible (the IT threshold has been crossed), but efficient algorithms like AMP fail. In this phase, the algorithm gets trapped in a "meta-stable" state or a local minimum at zero correlation with the truth.
  • The Easy Phase: The SNR is high enough that AMP successfully correlates with the true cluster assignments, reaching the algorithmic threshold.

Key Insights

The Impact of Sparsity

A central finding is that sparsity widens the computational gap. As the centroids become sparser (i.e., the fraction of non-zero components $\rho$ decreases), the distance between the IT threshold and the algorithmic threshold grows. The authors derive explicit scaling for these thresholds in the high-sparsity regime:

  • IT Threshold: $\lambda_{it} \approx \sqrt{-k\rho \log \rho} / \sqrt{\alpha}$
  • Algorithmic Threshold: $\lambda_{alg} = k / \sqrt{\alpha}$

The BBP Transition

The algorithmic threshold $\lambda_{alg}$ is shown to correspond to the BBP (Baik-Ben Arous-Péché) transition in random matrix theory. This is the point where a "spike" (the signal) emerges from the "bulk" of the noise eigenvalues in the data's covariance matrix. This connection explains why standard spectral methods often fail below this specific SNR.

AMP Performance

In the "extensive sparsity" regime, where the number of relevant features scales linearly with the total dimension, AMP is shown to significantly outperform standard spectral methods such as PCA and even Sparse-PCA, effectively pushing the boundaries of what is computationally achievable.

Limitations and Future Directions

While the paper provides a landmark characterization of subspace clustering, it notes several avenues for future work:

  • Noise Distributions: The current results assume additive Gaussian noise. Future research could utilize Vector AMP (VAMP) to extend these findings to more general, rotationally invariant noise distributions.
  • Cluster Balance: The study assumes balanced clusters ($p_c = 1/k$). Investigating how unbalanced cluster sizes affect the phase transitions is a necessary step for real-world applicability.
  • Sparsity Scaling: While the focus was on the "extensive" regime, further work is needed to bridge the gap between this and the "sub-extensive" regime ($s \lesssim \sqrt{n}$).

Conclusion

By establishing the exact asymptotic limits of subspace clustering, this work clarifies the fundamental trade-offs between statistical information and computational efficiency. It provides a theoretical roadmap for understanding when high-dimensional clustering is a solvable problem and when the underlying structure is destined to remain hidden from efficient algorithms.

Summary updated

Abstract

A simple model to study subspace clustering is the high-dimensional $k$-Gaussian mixture model where the cluster means are sparse vectors. Here we provide an exact asymptotic characterization of the statistically optimal reconstruction error in this model in the high-dimensional regime with extensive sparsity, i.e. when the fraction of non-zero components of the cluster means $\rho$, as well as the ratio $\alpha$ between the number of samples and the dimension are fixed, while the dimension diverges. We identify the information-theoretic threshold below which obtaining a positive correlation with the true cluster means is statistically impossible. Additionally, we investigate the performance of the approximate message passing (AMP) algorithm analyzed via its state evolution, which is conjectured to be optimal among polynomial algorithm for this task. We identify in particular the existence of a statistical-to-computational gap between the algorithm that require a signal-to-noise ratio $\lambda_{\text{alg}} \ge k / \sqrt{\alpha} $ to perform better than random, and the information theoretic threshold at $\lambda_{\text{it}} \approx \sqrt{-k \rho \log{\rho}} / \sqrt{\alpha}$. Finally, we discuss the case of sub-extensive sparsity $\rho$ by comparing the performance of the AMP with other sparsity-enhancing algorithms, such as sparse-PCA and diagonal thresholding.
BibTeX
@inproceedings{pesce2022subspace,
  author = {Luca Pesce and Bruno Loureiro and Florent Krzakala and Lenka Zdeborová},
  title = {{Subspace clustering in high-dimensions: Phase transitions \textbackslash\{\}\& Statistical-to-Computational gap}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=yoO8M9gKe28},
}
Figure