The Catastrophic Failure of the k k -Means Algorithm in High Dimensions, and How Hartigan’s Algorithm Avoids It
Roy R. Lederman, David Silva-Sánchez, Ziling Chen, Gilles Mordant, Amnon Balanov, Tamir Bendory · 2026
Read The Catastrophic Failure of the k k -Means Algorithm in High Dimensions, and How Hartigan’s Algorithm Avoids It by Roy R. Lederman, David Silva-Sánchez, Ziling Chen, Gilles Mordant, Amnon Balanov, Tamir Bendory (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-09936.txt.
Description
The k-means method groups data by repeatedly refining cluster centers, and Lloyd's version is among the most used. A 2026 paper led by Roy R. Lederman, with five co-authors, proves a stark failure mode in high dimensions with heavy noise. With high probability, nearly every starting split is already stable, so the method simply hands back the split it began with.
That failure bites even when other methods could recover the true clusters with ease. In contrast, the authors prove Hartigan's variant of k-means escapes the trap entirely. The contrast explains why practitioners often struggle with k-means on high-dimensional noisy data, and it draws a bright line between two algorithms that look like close cousins.
Catalog record
| CREATOR | Roy R. Lederman, David Silva-Sánchez, Ziling Chen, Gilles Mordant, Amnon Balanov, Tamir Bendory |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 102 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-09936