# Sketch-and-solve approaches to k-means clustering by semidefinite programming

arXiv: https://arxiv.org/abs/2211.15744 · HTML: https://mlsanity.com/paper/2211.15744/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 46 references that are in the map.
- First posted on arXiv 28 Nov 2022.

## Builds on (most cited first, 26 of 26)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [TEASER: Fast and Certifiable Point Cloud Registration](https://mlsanity.com/paper/2001.07715/) (2020)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [Community detection in sparse networks via Grothendieck's inequality](https://mlsanity.com/paper/1411.4686/) (2014)
- [Clustering subgaussian mixtures by semidefinite programming](https://mlsanity.com/paper/1602.06612/) (2016)
- [Relax, no need to round: integrality of clustering formulations](https://mlsanity.com/paper/1408.4045/) (2014)
- [Random Laplacian matrices and convex relaxations](https://mlsanity.com/paper/1504.03987/) (2015)
- [SOS-SDP: an Exact Solver for Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2104.11542/) (2021)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [A note on Probably Certifiably Correct algorithms](https://mlsanity.com/paper/1509.00824/) (2015)
- [Probably certifiably correct k-means clustering](https://mlsanity.com/paper/1509.07983/) (2015)
- [When Do Birds of a Feather Flock Together? k-Means, Proximity, and Conic Programming](https://mlsanity.com/paper/1710.06008/) (2017)
- [The ratio-cut polytope and K-means clustering](https://mlsanity.com/paper/2006.15225/) (2020)
- [Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clustering](https://mlsanity.com/paper/2201.08226/) (2022)
- [Recovery guarantees for exemplar-based clustering](https://mlsanity.com/paper/1309.3256/) (2013)
- [Sketching semidefinite programs for faster clustering](https://mlsanity.com/paper/2008.04270/) (2020)
- [Community Detection with a Subsampled Semidefinite Program](https://mlsanity.com/paper/2102.01419/) (2021)
- [Monte Carlo approximation certificates for k-means clustering](https://mlsanity.com/paper/1710.00956/) (2017)
- [Certifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering](https://mlsanity.com/paper/1806.11429/) (2018)
- [Improved Conic Reformulations for K-means Clustering](https://mlsanity.com/paper/1706.07105/) (2017)

## Built on by (most cited first, 1 of 1)

- [Accelerating data-driven algorithm selection for combinatorial partitioning problems](https://mlsanity.com/paper/2402.14332/) (2024)

## Abstract (arXiv)

We introduce a sketch-and-solve approach to speed up the Peng-Wei semidefinite relaxation of k-means clustering. When the data is appropriately separated we identify the k-means optimal clustering. Otherwise, our approach provides a high-confidence lower bound on the optimal k-means value. This lower bound is data-driven; it does not make any assumption on the data nor how it is generated. We provide code and an extensive set of numerical experiments where we use this approach to certify approximate optimality of clustering solutions obtained by k-means++.