# Cutoff for exact recovery of Gaussian mixture models

arXiv: https://arxiv.org/abs/2001.01194 · HTML: https://mlsanity.com/paper/2001.01194/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jan 2020.

## Built on by (most cited first, 18 of 18)

- [Wasserstein K-means for clustering probability distributions](https://mlsanity.com/paper/2209.06975/) (2022)
- [Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming](https://mlsanity.com/paper/2305.18436/) (2023)
- [Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model](https://mlsanity.com/paper/2310.19854/) (2023)
- [Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clustering](https://mlsanity.com/paper/2201.08226/) (2022)
- [Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model](https://mlsanity.com/paper/2207.04600/) (2022)
- [GeONet: a neural operator for learning the Wasserstein geodesic](https://mlsanity.com/paper/2209.14440/) (2022)
- [Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models](https://mlsanity.com/paper/2402.15432/) (2024)
- [Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous Data](https://mlsanity.com/paper/2209.15097/) (2022)
- [Scalable Second-order Riemannian Optimization for K-means Clustering](https://mlsanity.com/paper/2509.21675/) (2025)
- [Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima](https://mlsanity.com/paper/2505.03717/) (2025)
- [Graph-based Clustering Revisited: A Relaxation of Kernel k-Means Perspective](https://mlsanity.com/paper/2509.18826/) (2025)
- [Learning Multi-type heterogeneous interacting particle systems](https://mlsanity.com/paper/2602.03954/) (2026)
- [The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It](https://mlsanity.com/paper/2602.09936/) (2026)
- [Model Selection and Parameter Estimation of One-Dimensional Gaussian Mixture Models](https://mlsanity.com/paper/2404.12613/) (2024)
- [Adaptive Mean Estimation in the Hidden Markov sub-Gaussian Mixture Model](https://mlsanity.com/paper/2406.12446/) (2024)
- [One-Bit Clustering for Two Component Sub-Gaussian Mixture Models](https://mlsanity.com/paper/2606.21873/) (2026)
- [Riemannian Difference-of-Convex Optimization for K-Means Clustering](https://mlsanity.com/paper/2609.34310/) (2026)
- [GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimization](https://mlsanity.com/paper/2609.36074/) (2026)

## Abstract (arXiv)

We determine the information-theoretic cutoff value on separation of cluster centers for exact recovery of cluster labels in a K-component Gaussian mixture model with equal cluster sizes. Moreover, we show that a semidefinite programming (SDP) relaxation of the K-means clustering method achieves such sharp threshold for exact recovery without assuming the symmetry of cluster centers.