# Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 40 references that are in the map.
- First posted on arXiv 29 May 2023.

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

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [Clustering subgaussian mixtures by semidefinite programming](https://mlsanity.com/paper/1602.06612/) (2016)
- [Cutoff for exact recovery of Gaussian mixture models](https://mlsanity.com/paper/2001.01194/) (2020)
- [Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/1811.05642/) (2018)
- [Wasserstein K-means for clustering probability distributions](https://mlsanity.com/paper/2209.06975/) (2022)
- [Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous Data](https://mlsanity.com/paper/2209.15097/) (2022)

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

- [Scalable Second-order Riemannian Optimization for K-means Clustering](https://mlsanity.com/paper/2509.21675/) (2025)
- [Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima](https://mlsanity.com/paper/2505.03717/) (2025)
- [Graph-based Clustering Revisited: A Relaxation of Kernel k-Means Perspective](https://mlsanity.com/paper/2509.18826/) (2025)
- [Learning Multi-type heterogeneous interacting particle systems](https://mlsanity.com/paper/2602.03954/) (2026)
- [An Exterior Method for Nonnegative Matrix Factorization](https://mlsanity.com/paper/2605.19325/) (2026)
- [Model Selection and Parameter Estimation of One-Dimensional Gaussian Mixture Models](https://mlsanity.com/paper/2404.12613/) (2024)
- [Transport Clustering: Solving Low-Rank Optimal Transport via Clustering](https://mlsanity.com/paper/2603.03578/) (2026)
- [Riemannian Difference-of-Convex Optimization for K-Means Clustering](https://mlsanity.com/paper/2609.34310/) (2026)
- [GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimization](https://mlsanity.com/paper/2609.36074/) (2026)

## Abstract (arXiv)

K-means clustering is a widely used machine learning method for identifying patterns in large datasets. Recently, semidefinite programming (SDP) relaxations have been proposed for solving the K-means optimization problem, which enjoy strong statistical optimality guarantees. However, the prohibitive cost of implementing an SDP solver renders these guarantees inaccessible to practical datasets. In contrast, nonnegative matrix factorization (NMF) is a simple clustering algorithm widely used by machine learning practitioners, but it lacks a solid statistical underpinning and theoretical guarantees. In this paper, we consider an NMF-like algorithm that solves a nonnegative low-rank restriction of the SDP-relaxed K-means formulation using a nonconvex Burer--Monteiro factorization approach. The resulting algorithm is as simple and scalable as state-of-the-art NMF algorithms while also enjoying the same strong statistical optimality guarantees as the SDP. In our experiments, we observe that our algorithm achieves significantly smaller mis-clustering errors compared to the existing state-of-the-art while maintaining scalability.