Optimality of spectral clustering in the Gaussian mixture model
Authors:
Top Cited Papers
- 1 October 2021
- journal article
- research article
- Published by Institute of Mathematical Statistics in The Annals of Statistics
- Vol. 49 (5) , 2506-2530
Abstract
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.Keywords
All Related Versions
This publication has 52 references indexed in Scilit:
- Consistent selection of the number of clusters via crossvalidationBiometrika, 2010
- Spectral AlgorithmsFoundations and Trends® in Theoretical Computer Science, 2009
- Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results2006
- On clusteringsJournal of the ACM, 2004
- Laplacian Eigenmaps for Dimensionality Reduction and Data RepresentationNeural Computation, 2003
- Estimating the Number of Clusters in a Data Set Via the Gap StatisticJournal of the Royal Statistical Society Series B: Statistical Methodology, 2001
- Adaptive estimation of a quadratic functional by model selectionThe Annals of Statistics, 2000
- Partitioning of unstructured problems for parallel processingComputing Systems in Engineering, 1991
- Unsupervised speaker adaptation based on hierarchical spectral clusteringIEEE Transactions on Acoustics, Speech, and Signal Processing, 1989
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982