Optimality of spectral clustering in the Gaussian mixture model

DOI10.1214/20-AOS2044zbMATH Open1480.62129arXiv1911.00538OpenAlexW3211977733MaRDI QIDQ2054516FDOQ2054516

Anderson Y. Zhang, Harrison H. Zhou, Matthias Löffler

Publication date: 3 December 2021

Published in: The Annals of Statistics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1911.00538

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

zbMATH Keywords

\(k\)-meansGaussian mixture modelspectral clusteringspectral perturbation

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Inference from stochastic processes and spectral analysis (62M15)

Cites Work

• Estimating the number of clusters in a data set via the gap statistic
• Spectral clustering and the high-dimensional stochastic blockmodel
• Least squares quantization in PCM
• Consistency of spectral clustering in stochastic block models
• Minimax rates of community detection in stochastic block models
• Mathematical Foundations of Infinite-Dimensional Statistical Models
• A Simple SVD Algorithm for Finding Hidden Partitions
• Title not available (Why is that?)
• Consistency of spectral clustering
• Fast community detection by SCORE
• Community detection in degree-corrected block models
• Adaptive estimation of a quadratic functional by model selection.
• Entrywise eigenvector analysis of random matrices with low expected rank
• Spectral Algorithms
• Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters Are Unknown
• Title not available (Why is that?)
• Title not available (Why is that?)
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Consensus clustering: A resampling-based method for class discovery and visualization of gene expression microarray data
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
• Learning Theory
• Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Role of normalization in spectral clustering for stochastic blockmodels
• On clusterings
• Consistent selection of the number of clusters via crossvalidation
• The Planar k-Means Problem is NP-Hard
• An r-Dimensional Quadratic Placement Algorithm
• Graph Partitioning via Adaptive Spectral Techniques
• Title not available (Why is that?)
• A spectral algorithm for learning mixture models
• Uniform Convergence of Adaptive Graph-Based Regularization
• On the Quality of Spectral Separators
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Asymptotics and concentration bounds for bilinear forms of spectral projectors of sample covariance
• Cutoff for Exact Recovery of Gaussian Mixture Models
• An improved spectral bisection algorithm and its application to dynamic load balancing
• Perturbation of Linear Forms of Singular Vectors Under Gaussian Noise
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• High dimensional deformed rectangular matrices with applications in matrix denoising
• Partial recovery bounds for clustering with the relaxed \(K\)-means

Cited In (12)

• Statistical Significance of Clustering with Multidimensional Scaling
• Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method
• 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
• Eigen Selection in Spectral Clustering: A Theory-Guided Practice
• Title not available (Why is that?)
• Leave-one-out singular subspace perturbation analysis for spectral clustering
• Title not available (Why is that?)
• 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)