Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
The authors cast K-means clustering as a cardinality-constrained optimization problem over a compact embedded submanifold, replacing the discrete constraint with an exact difference-of-convex (DC) penalty. Supported by a global error bound proving exact penalization beyond a finite parameter threshold, they develop RADA-DC, an alternating descent-ascent algorithm that reaches an $\epsilon$-Riemannian critical point in $O(\epsilon^{-3})$ iterations. Across synthetic and real-world benchmarks, this formulation consistently outperforms standard baselines like K-means++ in objective quality at competitive runtimes, particularly when the number of clusters is large.
K-means++ systematically struggles in large-cluster regimes, but reformulating cardinality constraints into a continuous Riemannian difference-of-convex minimax game yields provably exact penalization and superior cluster assignments.
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.