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

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

Introduction

This paper provides a rigorous map of the "impossible," "hard," and "easy" zones for high-dimensional subspace clustering. By treating clustering as a matrix factorization problem, the authors identify a significant statistical-to-computational gap: a regime where clustering is mathematically possible but computationally intractable for standard polynomial-time algorithms.

The Challenge of High-Dimensional Clustering

Clustering is a fundamental tool for finding structure in data, but modern datasets are often "high-dimensional"—meaning they have a massive number of features ($d$) relative to the number of samples ($n$). In many cases, the meaningful differences between clusters only exist in a small subset of these features (a "subspace").

The authors focus on a specific model: the $k$-Gaussian Mixture Model (GMM) where the cluster centers (centroids) are sparse. The core challenge is determining the exact point at which we have enough data to recover these clusters. Specifically, they look for "phase transitions"—sharp boundaries where the problem suddenly shifts from being impossible to solve to being solvable, and whether our best algorithms can actually reach those theoretical limits.

Methods

The researchers employ a powerful toolkit from statistical physics and information theory:

  1. Matrix Factorization Mapping: They show that subspace clustering can be rewritten as a low-rank matrix factorization problem ($X = VU^\top + W$). This allows them to use established tools for analyzing how signals are recovered from noise.
  2. The Replica Method: Borrowed from the physics of disordered systems, this method allows the authors to calculate the "Bayesian-optimal" error—the absolute best any algorithm could ever do, regardless of its computational complexity.
  3. Approximate Message Passing (AMP): They analyze the performance of the AMP algorithm. AMP is a state-of-the-art iterative method that is conjectured to be the most powerful "polynomial-time" (efficient) algorithm for this class of problems.
  4. State Evolution: This mathematical technique tracks the performance of AMP as it iterates, providing a precise prediction of when the algorithm will succeed or fail in the high-dimensional limit.

Key Insights and Phase Transitions

Phase diagram illustrating the impossible, hard, and easy regimes for subspace clustering.
  • The "Hard" Phase: The most striking finding is the existence of a "hard" region in the phase diagram (the yellow zone in the figure above). In this zone, the signal-to-noise ratio (SNR) is high enough that a perfect (but infinitely slow) statistical method could find the clusters, but efficient algorithms like AMP are stuck "randomly guessing."
  • Sparsity Widens the Gap: As the centroids become sparser (fewer non-zero components, denoted by lower $\rho$), the gap between what is statistically possible ($\lambda_{it}$) and what is computationally easy ($\lambda_{alg}$) grows significantly.
  • The BBP Transition: The authors link the algorithmic threshold to the BBP transition (a famous result in random matrix theory). Essentially, the algorithm only starts working once the signal is strong enough to "pop out" of the bulk of the noise eigenvalues.
  • Extensive vs. Sub-extensive Sparsity: The paper clarifies a confusion in previous literature. If sparsity is extreme ($s \ll \sqrt{n}$), simple thresholding works well. But in the "extensive" regime ($s$ proportional to $d$), which is common in modern ML, the problem is much harder and requires the sophisticated analysis provided here.

Key Results and Algorithmic Performance

The authors derive explicit formulas for the two critical thresholds:

  • Information-Theoretic Threshold ($\lambda_{it}$): Recovery is possible if the SNR is roughly $\lambda_{it} \approx \sqrt{-k\rho \log \rho} / \sqrt{\alpha}$.
  • Algorithmic Threshold ($\lambda_{alg}$): Efficient algorithms like AMP only succeed if the SNR is roughly $\lambda_{alg} \geq k / \sqrt{\alpha}$.

In these formulas, $\rho$ is the density of the sparse features, $k$ is the number of clusters, and $\alpha$ is the ratio of samples to dimensions.

Mean Squared Error (MSE) of various algorithms compared to theoretical thresholds at different sparsity levels.

The result shows that for very sparse data (small $\rho$), the algorithmic threshold stays relatively constant while the statistical threshold drops, creating a massive "computational desert." As seen in the performance plots above, AMP closely tracks the theoretical state evolution (SE) predictions, successfully recovering the signal once the algorithmic threshold ($\lambda_{alg}$) is crossed, while simpler methods like PCA require an even stronger signal.

Limitations and Future Work

  • Gaussian Assumption: The analysis assumes the noise is perfectly Gaussian and isotropic. Real-world noise is often "heavy-tailed" or structured.
  • Balanced Clusters: The current model assumes all clusters have the same number of points ($p_c = 1/k$). Exploring "unbalanced" clusters is a necessary next step.
  • Algorithm Flavors: While AMP is powerful, the authors suggest exploring Vector AMP (VAMP) to handle more complex, rotationally invariant noise distributions that might appear in practical applications.

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 requires 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 \& Statistical-to-Computational gap}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=yoO8M9gKe28},
}
Figure