# Riemannian Difference-of-Convex Optimization for K-Means Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 31 references that are in the map.
- First posted on arXiv 28 Sep 2026.

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

- [Cutoff for exact recovery of Gaussian mixture models](https://mlsanity.com/paper/2001.01194/) (2020)
- [Clustering by Orthogonal NMF Model and Non-Convex Penalty Optimization](https://mlsanity.com/paper/1906.00570/) (2019)
- [Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming](https://mlsanity.com/paper/2305.18436/) (2023)
- [An exact penalty approach for optimization with nonnegative orthogonality constraints](https://mlsanity.com/paper/1907.12424/) (2019)
- [The difference of convex algorithm on Hadamard manifolds](https://mlsanity.com/paper/2112.05250/) (2021)
- [Tight Error Bounds for the Sign-Constrained Stiefel Manifold](https://mlsanity.com/paper/2210.05164/) (2022)
- [On the power of linear programming for K-means clustering](https://mlsanity.com/paper/2402.01061/) (2024)
- [A Riemannian Alternating Descent Ascent Algorithmic Framework for Nonconvex-Linear Minimax Problems on Riemannian Manifolds](https://mlsanity.com/paper/2409.19588/) (2024)
- [A Riemannian Optimization Approach to Clustering Problems](https://mlsanity.com/paper/2208.03858/) (2022)
- [An Inexact Proximal Framework for Nonsmooth Riemannian Difference-of-Convex Optimization](https://mlsanity.com/paper/2509.08561/) (2025)
- [Scalable Second-order Riemannian Optimization for K-means Clustering](https://mlsanity.com/paper/2509.21675/) (2025)
- [Big-Data Clustering: K-Means or K-Indicators?](https://mlsanity.com/paper/1906.00938/) (2019)
- [Extreme Point Pursuit -- Part I: A Framework for Constant Modulus Optimization](https://mlsanity.com/paper/2403.06506/) (2024)
- [Proximal methods for structured nonsmooth optimization over Riemannian submanifolds](https://mlsanity.com/paper/2411.15776/) (2024)

## Abstract (arXiv)

K-means is a widely adopted clustering approach in signal processing and machine learning. In this paper, we study K-means clustering through a cardinality-constrained formulation on a compact embedded submanifold. We replace the cardinality constraint with a difference-of-convex (DC) penalty and establish a global error bound to prove that the penalized and constrained formulations share the same global minimizers whenever the penalty parameter exceeds a finite threshold. To solve the resulting nonsmooth Riemannian DC problem, we reformulate it as a minimax problem and propose RADA-DC, a Riemannian alternating descent ascent method combining dual regularization with DC linearization. Under standard assumptions and suitable parameter choices, RADA-DC finds an ε-Riemannian critical point within O(ε-3) iterations. We conduct experiments on synthetic and real-world datasets to demonstrate that the proposed method outperforms the tested baselines, including K-means++, in solution quality at competitive computational cost when the number of clusters is large.