# On the tightness of an SDP relaxation of k-means

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2015.

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

- [Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions](https://mlsanity.com/paper/2208.04055/) (2022)
- [Distribution free optimality intervals for clustering](https://mlsanity.com/paper/2107.14442/) (2021)

## Abstract (arXiv)

Recently, Awasthi et al. introduced an SDP relaxation of the k-means problem in mathbb Rm. In this work, we consider a random model for the data points in which k balls of unit radius are deterministically distributed throughout mathbb Rm, and then in each ball, n points are drawn according to a common rotationally invariant probability distribution. For any fixed ball configuration and probability distribution, we prove that the SDP relaxation of the k-means problem exactly recovers these planted clusters with probability 1-e-Omega(n) provided the distance between any two of the ball centers is >2+ε, where ε is an explicit function of the configuration of the ball centers, and can be arbitrarily small when m is large.