# Optimality of Spectral Clustering in the Gaussian Mixture Model

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2019.

## Built on by (most cited first, 30 of 42)

- [Selective inference for k-means clustering](https://mlsanity.com/paper/2203.15267/) (2022)
- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming](https://mlsanity.com/paper/2305.18436/) (2023)
- [Learning Low-Dimensional Nonlinear Structures from High-Dimensional Noisy Data: An Integral Operator Approach](https://mlsanity.com/paper/2203.00126/) (2022)
- [Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound](https://mlsanity.com/paper/2212.08642/) (2022)
- [Optimal Clustering in Anisotropic Gaussian Mixture Models](https://mlsanity.com/paper/2101.05402/) (2021)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Interpretable Machine Learning for Discovery: Statistical Challenges & Opportunities](https://mlsanity.com/paper/2308.01475/) (2023)
- [Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures](https://mlsanity.com/paper/2201.09040/) (2022)
- [Stacked SVD or SVD stacked? A Random Matrix Theory perspective on data integration](https://mlsanity.com/paper/2507.22170/) (2025)
- [Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model](https://mlsanity.com/paper/2207.04600/) (2022)
- [Intensity Profile Projection: A Framework for Continuous-Time Representation Learning for Dynamic Networks](https://mlsanity.com/paper/2306.06155/) (2023)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [Capturing the Denoising Effect of PCA via Compression Ratio](https://mlsanity.com/paper/2204.10888/) (2022)
- [Optimal Clustering of Discrete Mixtures: Binomial, Poisson, Block Models, and Multi-layer Networks](https://mlsanity.com/paper/2311.15598/) (2023)
- [Transformers as Unsupervised Learning Algorithms: A study on Gaussian Mixtures](https://mlsanity.com/paper/2505.11918/) (2025)
- [Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learning](https://mlsanity.com/paper/2304.09154/) (2023)
- [Consistency of Lloyd's Algorithm Under Perturbations](https://mlsanity.com/paper/2309.00578/) (2023)
- [A provable initialization and robust clustering method for general mixture models](https://mlsanity.com/paper/2401.05574/) (2024)
- [Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps](https://mlsanity.com/paper/2104.03298/) (2021)
- [Cluster-and-Conquer: A Framework For Time-Series Forecasting](https://mlsanity.com/paper/2110.14011/) (2021)
- [Factor Adjusted Spectral Clustering for Mixture Models](https://mlsanity.com/paper/2408.12564/) (2024)
- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)
- [A Bayesian Approach To Graph Partitioning](https://mlsanity.com/paper/2204.12927/) (2022)
- [A Non-Parametric Bootstrap for Spectral Clustering](https://mlsanity.com/paper/2209.05812/) (2022)
- [Asymptotics for The k-means](https://mlsanity.com/paper/2211.10015/) (2022)
- [Semidefinite programming on population clustering: a global analysis](https://mlsanity.com/paper/2301.00344/) (2023)
- [Scalable Clustering: Large Scale Unsupervised Learning of Gaussian Mixture Models with Outliers](https://mlsanity.com/paper/2302.14599/) (2023)
- [Performance Gaps in Multi-view Clustering under the Nested Matrix-Tensor Model](https://mlsanity.com/paper/2402.10677/) (2024)

## Abstract (arXiv)

Spectral clustering is one of the most popular algorithms to group high dimensional data. It is easy to implement and computationally efficient. Despite its popularity and successful applications, its theoretical properties have not been fully understood. In this paper, we show that spectral clustering is minimax optimal in the Gaussian Mixture Model with isotropic covariance matrix, when the number of clusters is fixed and the signal-to-noise ratio is large enough. Spectral gap conditions are widely assumed in the literature to analyze spectral clustering. On the contrary, these conditions are not needed to establish optimality of spectral clustering in this paper.