# Compressive K-means

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2016.

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

- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [Controlling Wasserstein Distances by Kernel Norms with Application to Compressive Statistical Learning](https://mlsanity.com/paper/2112.00423/) (2021)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [Mean Nystr"om Embeddings for Adaptive Compressive Learning](https://mlsanity.com/paper/2110.10996/) (2021)
- [Sketch and shift: a robust decoder for compressive clustering](https://mlsanity.com/paper/2312.09940/) (2023)
- [Asymmetric compressive learning guarantees with applications to quantized sketches](https://mlsanity.com/paper/2104.10061/) (2021)
- [Learning primal-dual sparse kernel machines](https://mlsanity.com/paper/2108.12199/) (2021)
- [M2M: A general method to perform various data analysis tasks from a differentially private sketch](https://mlsanity.com/paper/2211.14062/) (2022)
- [CADeSH: Collaborative Anomaly Detection for Smart Homes](https://mlsanity.com/paper/2303.01021/) (2023)
- [Compressive Meta-Learning](https://mlsanity.com/paper/2508.11090/) (2025)

## Abstract (arXiv)

The Lloyd-Max algorithm is a classical approach to perform K-means clustering. Unfortunately, its cost becomes prohibitive as the training dataset grows large. We propose a compressive version of K-means (CKM), that estimates cluster centers from a sketch, i.e. from a drastically compressed representation of the training dataset. We demonstrate empirically that CKM performs similarly to Lloyd-Max, for a sketch size proportional to the number of cen-troids times the ambient dimension, and independent of the size of the original dataset. Given the sketch, the computational complexity of CKM is also independent of the size of the dataset. Unlike Lloyd-Max which requires several replicates, we further demonstrate that CKM is almost insensitive to initialization. For a large dataset of 10^7 data points, we show that CKM can run two orders of magnitude faster than five replicates of Lloyd-Max, with similar clustering performance on artificial data. Finally, CKM achieves lower classification errors on handwritten digits classification.