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

Abstract

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(ε⁻³) 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.

A switching proximal gradient method for constrained difference-of-convex optimization problems
Yuncheng Liu, Chuangliang Zhang, Bo Yang
arXiv27 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Inference for conditional Fréchet means via Riemannian Robust Bias Correction
Ryunosuke Miyazaki, Chang Jun Im
arXiv1 Nov 2026PreprintarXiv licenceFull textStatisticsarXiv
Computing Fréchet Means on Unknown Submanifolds of Riemannian Manifolds
Ian McPherson, Mauro Maggioni
arXiv19 Oct 2026PreprintarXiv licenceFull textGeometry & topology Optimisation & controlarXiv
On C^k convex variants of Stein's Weighted L² Conjecture for Bochner-Riesz means
Ruixiang Zhang
arXiv22 Sep 2026PreprintCC BY-NC-ND 4.0Full textAnalysis & PDEsarXiv
An Algebraic Approach to Constrained K-means Clustering
Hiroki Oohori, Kentaro Fukushima, Michio Yamamoto
arXiv10 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{xu2026riemannian,
  title = {{Riemannian Difference-of-Convex Optimization for K-Means Clustering}},
  author = {Meng Xu and Bo Jiang and Hanfu Zhang and Ya-Feng Liu and Anthony Man-Cho So},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.34310},
  eprint = {2609.34310},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.34310},
}

RIS

TY  - UNPB
TI  - Riemannian Difference-of-Convex Optimization for K-Means Clustering
AU  - Meng Xu
AU  - Bo Jiang
AU  - Hanfu Zhang
AU  - Ya-Feng Liu
AU  - Anthony Man-Cho So
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.34310
UR  - https://arxiv.org/abs/2609.34310
AB  - 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.
ER  -

Abstract

Related

Cite