# An Observation on Lloyd's k-Means Algorithm in High Dimensions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 14 references that are in the map.
- First posted on arXiv 17 Jun 2025.

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

- [Consistency and inconsistency in k-means clustering](https://mlsanity.com/paper/2507.06226/) (2025)

## Abstract (arXiv)

Clustering and estimating cluster means are core problems in statistics and machine learning, with k-means and Expectation Maximization (EM) being two widely used algorithms. In this work, we provide a theoretical explanation for the failure of k-means in high-dimensional settings with high noise and limited sample sizes, using a simple Gaussian Mixture Model (GMM). We identify regimes where, with high probability, almost every partition of the data becomes a fixed point of the k-means algorithm. This study is motivated by challenges in the analysis of more complex cases, such as masked GMMs, and those arising from applications in Cryo-Electron Microscopy.