Optimality of spectral clustering in the Gaussian Mixture Model
OPEN ACCESS
Loading...
Author / Producer
Date
2020-08-05
Publication Type
Working Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
Pages / Article No.
1911.00538
Publisher
Cornell University
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Clustering; High-dimensional estimation; PCA; Gaussian mixture model; k-means clustering
Organisational unit
02537 - Seminar für Statistik (SfS) / Seminar for Statistics (SfS)
Notes
Funding
Related publications and datasets
Is previous version of: