# A Geometric Approach to k-means

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 56 references that are in the map.
- First posted on arXiv 13 Jan 2022.

## Builds on (most cited first, 13 of 13)

- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences](https://mlsanity.com/paper/1609.00978/) (2016)
- [Global analysis of Expectation Maximization for mixtures of two Gaussians](https://mlsanity.com/paper/1608.07630/) (2016)
- [From Symmetry to Geometry: Tractable Nonconvex Problems](https://mlsanity.com/paper/2007.06753/) (2020)
- [On the Optimization Landscape of Tensor Decompositions](https://mlsanity.com/paper/1706.05598/) (2017)
- [Structured Local Optima in Sparse Blind Deconvolution](https://mlsanity.com/paper/1806.00338/) (2018)
- [Analysis of the Optimization Landscapes for Overcomplete Representation Learning](https://mlsanity.com/paper/1912.02427/) (2019)
- [Global Convergence of Least Squares EM for Demixing Two Log-Concave Densities](https://mlsanity.com/paper/1906.06776/) (2019)
- [Structures of Spurious Local Minima in k-means](https://mlsanity.com/paper/2002.06694/) (2020)
- [Unique sparse decomposition of low rank matrices](https://mlsanity.com/paper/2106.07736/) (2021)

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

- [Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression](https://mlsanity.com/paper/2405.18237/) (2024)
- [Jigsaw Game: Federated Clustering](https://mlsanity.com/paper/2407.12764/) (2024)

## Abstract (arXiv)

kmeans clustering is a fundamental problem in many scientific and engineering domains. The optimization problem associated with kmeans clustering is nonconvex, for which standard algorithms are only guaranteed to find a local optimum. Leveraging the hidden structure of local solutions, we propose a general algorithmic framework for escaping undesirable local solutions and recovering the global solution or the ground truth clustering. This framework consists of iteratively alternating between two steps: (i) detect mis-specified clusters in a local solution, and (ii) improve the local solution by non-local operations. We discuss specific implementation of these steps, and elucidate how the proposed framework unifies many existing variants of kmeans algorithms through a geometric perspective. We also present two natural variants of the proposed framework, where the initial number of clusters may be over- or under-specified. We provide theoretical justifications and extensive experiments to demonstrate the efficacy of the proposed approach.