Optimality of spectral clustering in the Gaussian mixture model
From MaRDI portal
(Redirected from 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
(31)- Statistical Significance of Clustering with Multidimensional Scaling
- Minimum spectral connectivity projection pursuit. Divisive clustering using optimal projections for spectral clustering
- Spectral clustering algorithm for the allometric extension model
- CHIME: clustering of high-dimensional Gaussian mixtures with EM algorithm and its optimality
- Estimating Higher-Order Mixed Memberships via the l2,∞ Tensor Perturbation Bound
- Asymptotic limits of spiked eigenvalues and eigenvectors of signal-plus-noise matrices with weak signals and heteroskedastic noise
- Clustering a mixture of Gaussians with unknown covariance
- Sharp-SSL: Selective High-Dimensional Axis-Aligned Random Projections for Semi-Supervised Learning
- Optimal estimation of misclassification rate for two-class clustering with sub-Gaussian noises
- Deflated HeteroPCA: overcoming the curse of ill-conditioning in heteroskedastic PCA
- 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
- Analysis of singular subspaces under random perturbations
- Learning low-dimensional nonlinear structures from high-dimensional noisy data: an integral operator approach
- Optimal clustering by Lloyd's algorithm for low-rank mixture model
- A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers
- Feature screening for clustering analysis of count data with an application to single-cell RNA-sequencing
- Degree-Heterogeneous Latent Class Analysis for High-Dimensional Discrete Data
- A semiparametric Gaussian mixture model with spatial dependence and its application to whole-slide image clustering analysis
- Eigen Selection in Spectral Clustering: A Theory-Guided Practice
- Consistency of Lloyd's algorithm under perturbations
- Scalable Clustering: Large Scale Unsupervised Learning of Gaussian Mixture Models with Outliers
- 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)
