Optimality of Spectral Clustering in the Gaussian Mixture Model
Preprint
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 35 references indexed in Scilit:
- Eigen Selection in Spectral Clustering: A Theory-Guided PracticeJournal of the American Statistical Association, 2021
- Random perturbation of low rank matrices: Improving classical boundsLinear Algebra and its Applications, 2018
- A Simple SVD Algorithm for Finding Hidden PartitionsCombinatorics, Probability and Computing, 2017
- Consistent selection of the number of clusters via crossvalidationBiometrika, 2010
- Graph Partitioning via Adaptive Spectral TechniquesCombinatorics, Probability and Computing, 2009
- Consensus Clustering: A Resampling-Based Method for Class Discovery and Visualization of Gene Expression Microarray DataMachine Learning, 2003
- Generalization of an Inequality by Talagrand and Links with the Logarithmic Sobolev InequalityJournal of Functional Analysis, 2000
- An improved spectral bisection algorithm and its application to dynamic load balancingParallel Computing, 1995
- 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