mlsanityData to 7 Oct 2026

Optimality of Spectral Clustering in the Gaussian Mixture Model

arXiv 1911.00538 ↗First posted 1 Nov 2019math.ST cs.LG math.SPcited by 42

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 10; 2023: 10; 2024: 7; 2025: 5; 2026: 6.

42 papers.

Sort:

  1. 2022Selective inference for k-means clusteringcited by 21
  2. 2021Clustering a Mixture of Gaussians with Unknown Covariancecited by 14
  3. 2022Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clusteringcited by 14
  4. 2023Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programmingcited by 9
  5. 2022Learning Low-Dimensional Nonlinear Structures from High-Dimensional Noisy Data: An Integral Operator Approachcited by 8
  6. 2022Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Boundcited by 8
  7. 2021Optimal Clustering in Anisotropic Gaussian Mixture Modelscited by 7
  8. 2023Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCAcited by 7
  9. 2023Interpretable Machine Learning for Discovery: Statistical Challenges & Opportunitiescited by 7
  10. 2022Optimal Estimation and Computational Limit of Low-rank Gaussian Mixturescited by 6
  11. 2022Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Modelcited by 5
  12. 2023Intensity Profile Projection: A Framework for Continuous-Time Representation Learning for Dynamic Networkscited by 5
30 more
  1. 2023Adversarially robust clustering with optimality guaranteescited by 4
  2. 2025Stacked SVD or SVD stacked? A Random Matrix Theory perspective on data integrationcited by 4
  3. 2022Capturing the Denoising Effect of PCA via Compression Ratiocited by 3
  4. 2023Optimal Clustering of Discrete Mixtures: Binomial, Poisson, Block Models, and Multi-layer Networkscited by 3
  5. 2023Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learningcited by 2
  6. 2023Consistency of Lloyd's Algorithm Under Perturbationscited by 2
  7. 2024A provable initialization and robust clustering method for general mixture modelscited by 2
  8. 2025Transformers as Unsupervised Learning Algorithms: A study on Gaussian Mixturescited by 2
  9. 2021Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gapscited by 1
  10. 2021Cluster-and-Conquer: A Framework For Time-Series Forecastingcited by 1
  11. 2024Factor Adjusted Spectral Clustering for Mixture Modelscited by 1
  12. 2025Near-Optimal Clustering in Mixture of Markov Chainscited by 1
  13. 2022A Bayesian Approach To Graph Partitioningcited by 0
  14. 2022A Non-Parametric Bootstrap for Spectral Clusteringcited by 0
  15. 2022Asymptotics for The k-meanscited by 0
  16. 2023Semidefinite programming on population clustering: a global analysiscited by 0
  17. 2023Scalable Clustering: Large Scale Unsupervised Learning of Gaussian Mixture Models with Outlierscited by 0
  18. 2024Performance Gaps in Multi-view Clustering under the Nested Matrix-Tensor Modelcited by 0
  19. 2024A multi-core periphery perspective: Ranking via relative centralitycited by 0
  20. 2024Adaptive Mean Estimation in the Hidden Markov sub-Gaussian Mixture Modelcited by 0
  21. 2024Cluster Quilting: Spectral Clustering for Patchwork Learningcited by 0
  22. 2024Unsupervised Machine Learning for Detecting and Locating Human-Made Objects in 3D Point Cloudcited by 0
  23. 2025Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithmscited by 0
  24. 2025High-dimensional Clustering and Signal Recovery under Block Signalscited by 0
  25. 2026Low-degree Lower bounds for clustering in moderate dimensioncited by 0
  26. 2026Uncovering Locally Low-dimensional Structure in Networks by Locally Optimal Spectral Embeddingcited by 0
  27. 2026Individual-heterogeneous sub-Gaussian Mixture Modelscited by 0
  28. 2026Fast estimation of Gaussian mixture components via centering and singular value thresholdingcited by 0
  29. 2026Mixed Membership sub-Gaussian Modelscited by 0
  30. 2026One-Bit Clustering for Two Component Sub-Gaussian Mixture Modelscited by 0