A Performance Guarantee for Spectral Clustering
DOI10.1137/20M1352193zbMath1468.05223arXiv2007.05627OpenAlexW3133691047MaRDI QIDQ4999362
Shaofeng Deng, March Boedihardjo, Thomas Strohmer
Publication date: 6 July 2021
Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.05627
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Deterministic network models in operations research (90B10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Spectral clustering and the high-dimensional stochastic blockmodel
- NP-hardness of Euclidean sum-of-squares clustering
- Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
- Entrywise eigenvector analysis of random matrices with low expected rank
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
- The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
- Consistency of spectral clustering in stochastic block models
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Improved Spectral-Norm Bounds for Clustering
- The Planar k-Means Problem is NP-Hard
- An $\ell_{\infty}$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation
- Least squares quantization in PCM
- Uniform Bounds for Invariant Subspace Perturbations
- Strong Consistency of Spectral Clustering for Stochastic Block Models
- Multi-way spectral partitioning and higher-order cheeger inequalities
- The Rotation of Eigenvectors by a Perturbation. III
This page was built for publication: A Performance Guarantee for Spectral Clustering
