Optimality of spectral clustering in the Gaussian mixture model
From MaRDI portal
Publication:2054516
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.
Recommendations
- Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
- Consistency of spectral clustering
- Kernel spectral clustering of large dimensional data
- Spectral clustering and block models: a review and a new algorithm
- The geometry of kernelized spectral clustering
Cites work
- scientific article; zbMATH DE number 3417498 (Why is no real title available?)
- A Simple SVD Algorithm for Finding Hidden Partitions
- A spectral algorithm for learning mixture models
- A tensor approach to learning mixed membership community models
- Adaptive estimation of a quadratic functional by model selection.
- An r-Dimensional Quadratic Placement Algorithm
- An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
- An improved spectral bisection algorithm and its application to dynamic load balancing
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Asymptotics and concentration bounds for bilinear forms of spectral projectors of sample covariance
- Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
- Community detection in degree-corrected block models
- Consensus clustering: A resampling-based method for class discovery and visualization of gene expression microarray data
- Consistency of spectral clustering
- Consistency of spectral clustering in stochastic block models
- Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
- Consistent selection of the number of clusters via crossvalidation
- Cutoff for Exact Recovery of Gaussian Mixture Models
- Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
- Entrywise eigenvector analysis of random matrices with low expected rank
- Estimating the number of clusters in a data set via the gap statistic
- Fast community detection by SCORE
- Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality
- Graph partitioning via adaptive spectral techniques
- High dimensional deformed rectangular matrices with applications in matrix denoising
- Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
- Learning Theory
- Learning spectral clustering, with application to speech separation
- Least squares quantization in PCM
- Mathematical foundations of infinite-dimensional statistical models
- Minimax rates of community detection in stochastic block models
- On clusterings: good, bad and spectral
- On the Quality of Spectral Separators
- Partial recovery bounds for clustering with the relaxed \(K\)-means
- Perturbation of linear forms of singular vectors under Gaussian noise
- Role of normalization in spectral clustering for stochastic blockmodels
- Spectral algorithms
- Spectral clustering and the high-dimensional stochastic blockmodel
- The Planar k-Means Problem is NP-Hard
- Uniform Convergence of Adaptive Graph-Based Regularization
Cited in
(17)- Statistical Significance of Clustering with Multidimensional Scaling
- Minimum spectral connectivity projection pursuit. Divisive clustering using optimal projections for spectral clustering
- CHIME: clustering of high-dimensional Gaussian mixtures with EM algorithm and its optimality
- Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method
- Kernel spectral clustering of large dimensional data
- Optimal estimation and computational limit of low-rank Gaussian mixtures
- The sensitivity of the number of clusters in a Gaussian mixture model to prior distributions
- Partial recovery for top-\(k\) ranking: optimality of MLE and suboptimality of the spectral method
- Learning low-dimensional nonlinear structures from high-dimensional noisy data: an integral operator approach
- A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers
- Eigen Selection in Spectral Clustering: A Theory-Guided Practice
- scientific article; zbMATH DE number 7307486 (Why is no real title available?)
- Leave-one-out singular subspace perturbation analysis for spectral clustering
- Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
- scientific article; zbMATH DE number 7071835 (Why is no real title available?)
- An \({\ell_p}\) theory of PCA and spectral clustering
- Sharp optimal recovery in the two component Gaussian mixture model
This page was built for publication: Optimality of spectral clustering in the Gaussian mixture model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2054516)
