# Recovery guarantees for exemplar-based clustering

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2013.

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

- [Local versions of sum-of-norms clustering](https://mlsanity.com/paper/2109.09589/) (2021)
- [Sum-of-norms clustering does not separate nearby balls](https://mlsanity.com/paper/2104.13753/) (2021)
- [Sketch-and-solve approaches to k-means clustering by semidefinite programming](https://mlsanity.com/paper/2211.15744/) (2022)
- [Robust Point Matching with Distance Profiles](https://mlsanity.com/paper/2312.12641/) (2023)
- [BalLOT: Balanced k-means clustering with optimal transport](https://mlsanity.com/paper/2512.05926/) (2025)

## Abstract (arXiv)

For a certain class of distributions, we prove that the linear programming relaxation of k-medoids clustering---a variant of k-means clustering where means are replaced by exemplars from within the dataset---distinguishes points drawn from nonoverlapping balls with high probability once the number of points drawn and the separation distance between any two balls are sufficiently large. Our results hold in the nontrivial regime where the separation distance is small enough that points drawn from different balls may be closer to each other than points drawn from the same ball; in this case, clustering by thresholding pairwise distances between points can fail. We also exhibit numerical evidence of high-probability recovery in a substantially more permissive regime.