Partial recovery bounds for clustering with the relaxed \(K\)-means

DOI10.4171/MSL/8zbMath1426.62186arXiv1807.07547MaRDI QIDQ2319817

Christophe Giraud, Nicolas Verzelen

Publication date: 20 August 2019

Published in: Mathematical Statistics and Learning (Search for Journal in Brave)

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

zbMATH Keywords

clusteringstochastic block modelmixture of sub-Gaussianpartial recovery boundrelaxed \(K\)-means

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Pattern recognition, speech recognition (68T10)

Related Items (11)

Iterative algorithm for discrete structure recovery ⋮ Diffusion \(K\)-means clustering on manifolds: provable exact recovery via semidefinite relaxations ⋮ Unnamed Item ⋮ Hanson-Wright inequality in Hilbert spaces with application to \(K\)-means clustering for non-Euclidean data ⋮ Maximum likelihood estimation of sparse networks with missing observations ⋮ Unnamed Item ⋮ Optimality of spectral clustering in the Gaussian mixture model ⋮ Unnamed Item ⋮ Sharp optimal recovery in the two component Gaussian mixture model ⋮ An \({\ell_p}\) theory of PCA and spectral clustering ⋮ Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model

Uses Software

• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A spectral algorithm for learning mixture models
• Community detection in sparse networks via Grothendieck's inequality
• Hanson-Wright inequality and sub-Gaussian concentration
• On semidefinite relaxations for the block model
• A constant-factor approximation algorithm for the \(k\)-median problem
• Convex relaxation methods for community detection
• Sharp optimal recovery in the two component Gaussian mixture model
• Model assisted variable clustering: minimax-optimal recovery and algorithms
• Hanson-Wright inequality in Hilbert spaces with application to \(K\)-means clustering for non-Euclidean data
• When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
• Exact recovery in the Ising blockmodel
• Consistency of spectral clustering in stochastic block models
• Convexified modularity maximization for degree-corrected stochastic block models
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Phase transitions in semidefinite relaxations
• Relax, No Need to Round
• Community Detection and Stochastic Block Models
• Asymptotic mutual information for the balanced binary stochastic block model
• Clustering subgaussian mixtures by semidefinite programming
• Exponential Error Rates of SDP for Block Models: Beyond Grothendieck’s Inequality
• Least squares quantization in PCM
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Mixture models, robustness, and sum of squares proofs
• List-decodable robust mean estimation and learning mixtures of spherical gaussians
• Probability Inequalities for Sums of Bounded Random Variables
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• How robust are reconstruction thresholds for community detection?
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Learning Theory

This page was built for publication: Partial recovery bounds for clustering with the relaxed \(K\)-means