When do birds of a feather flock together? \(k\)-means, proximity, and conic programming

DOI10.1007/s10107-018-1333-xzbMath1434.90123arXiv1710.06008OpenAlexW2963814147MaRDI QIDQ2288194

Yanyan Li

Publication date: 17 January 2020

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

clusteringconvex relaxationGaussian mixture model\(k\)-means

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Semidefinite programming (90C22) Quadratic programming (90C20)

Related Items (11)

The Ratio-Cut Polytope and K-Means Clustering ⋮ Diffusion \(K\)-means clustering on manifolds: provable exact recovery via semidefinite relaxations ⋮ \(k\)-median: exact recovery in the extended stochastic ball model ⋮ Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering ⋮ SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering ⋮ Hanson-Wright inequality in Hilbert spaces with application to \(K\)-means clustering for non-Euclidean data ⋮ Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018 ⋮ Convex relaxation methods for community detection ⋮ Partial recovery bounds for clustering with the relaxed \(K\)-means ⋮ A Performance Guarantee for Spectral Clustering ⋮ Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model

Uses Software

• SDPNAL+

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
• \(k\)-means requires exponentially many iterations even in the plane
• A spectral algorithm for learning mixture models
• User-friendly tail bounds for sums of random matrices
• NP-hardness of Euclidean sum-of-squares clustering
• Probably certifiably correct \(k\)-means clustering
• On semidefinite relaxations for the block model
• Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
• Lectures on Modern Convex Optimization
• Relax, No Need to Round
• A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
• Improved Spectral-Norm Bounds for Clustering
• K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality
• The Planar k-Means Problem is NP-Hard
• Spectral Algorithms
• Clustering subgaussian mixtures by semidefinite programming
• Centroidal Voronoi Tessellations: Applications and Algorithms
• Least squares quantization in PCM
• Smoothed Analysis of the k-Means Method
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Learning Theory

This page was built for publication: When do birds of a feather flock together? \(k\)-means, proximity, and conic programming