Source-linked AI summary
Riemannian Difference-of-Convex Optimization for K-Means Clustering
Meng Xu, Bo Jiang, Hanfu Zhang, Ya-Feng Liu, Anthony Man-Cho So
TL;DR
K-means is challenging to solve globally at reasonable computational cost, especially when the number of clusters is large, and existing Riemannian penalties may not preserve its equivalence. The paper establishes an exact DC penalty formulation and proposes RADA-DC to solve it. Experiments report lower objective values on average than tested baselines in large-cluster settings, at competitive computational cost.
Problem
Finding globally optimal K-means partitions is NP-hard, and obtaining high-quality solutions at reasonable cost remains challenging, particularly for many clusters.
Source: §1 · p. 1Method
The paper uses a DC penalty with a global error bound for exactness and proposes RADA-DC, combining dual regularization and DC linearization to solve the nonsmooth Riemannian problem.
Source: §1 · pp. 1–2Results
In large-cluster settings, the approach achieves lower objective values on average than tested baselines at competitive computational cost.
Source: §4.2 · p. 4Takeaways & Limitations
Above a finite penalty threshold, the penalized and cardinality-constrained formulations share the same global minimizers.
Source: §1 · p. 1The convergence guarantee assumes a compact embedded manifold, Lipschitz-gradient smooth objective, closed convex Lipschitz functions, and efficiently computable proximal mappings and subgradients.
Source: §3.2 · p. 3
Abstract
from arXiv · showhide
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 $\epsilon$-Riemannian critical point within $O(\epsilon^{-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.
1. INTRODUCTION
K-means remains difficult to solve globally and efficiently, especially with many clusters, while existing Riemannian penalties do not generally preserve equivalence to K-means. The paper develops a globally exact DC penalty and a single-loop RADA-DC algorithm for the resulting problem.
1. INTRODUCTION
- Lloyd’s algorithm is inexpensive but initialization-sensitive, and obtaining high-quality solutions at reasonable cost remains challenging, particularly with many clusters.SDP and linear-programming relaxations can also be computationally demanding on large datasets.Source: §1 · p. 1
- Existing quadratic and ℓ1 penalties do not generally preserve equivalence to K-means, motivating a continuous penalty for the cardinality-constrained Riemannian formulation.Prior error bounds do not directly cover the joint cardinality and manifold constraints in this model.Source: §1 · p. 1
- A global error bound based on a DC penalty residual establishes that a finite penalty threshold makes the penalized and constrained formulations share their global minimizers.The bound controls distance from manifold points to the joint feasible set.Source: §1 · p. 1
- RADA-DC combines RADA dual regularization with DC linearization in a single-loop method for nonsmooth Riemannian DC optimization.Each outer iteration uses a fixed number of Riemannian gradient steps followed by a proximal dual update.Source: §1 · pp. 1–2
- Under standard assumptions and suitable parameters, RADA-DC reaches an ϵ-Riemannian critical point within O(ϵ^-3) iterations.The approach also yields the lowest K-means objective in most tested large-cluster settings at competitive computational cost.Source: §1 · p. 2
2. K-MEANS AND ITS RIEMANNIAN DC FORMULATION
The section expresses K-means as a cardinality-constrained optimization problem on a compact embedded submanifold. A difference-of-convex penalty and global error bound yield an equivalent penalized formulation for sufficiently large finite penalty parameters.
2.1. K-Means Formulation
- The normalized cluster-indicator matrix has orthonormal columns, satisfies XXᵀ1_n = 1_n, and has exactly n nonzeros.Each row has one positive nonzero entry, encoding one cluster assignment per sample.Source: §2.1 · p. 2
- K-means is reformulated as minimizing its objective over the manifold subject to the cardinality constraint ∥X∥_0 = n.The feasible matrices correspond to normalized cluster indicators up to column-sign changes, which preserve XXᵀ and the objective.Source: §2.1 · p. 2
- The cardinality-constrained formulation uses the compact embedded submanifold defined by XᵀX = I_K and XXᵀ1_n = 1_n.The remaining constraint ∥X∥_0 = n enforces exactly one nonzero per row because the manifold constraints rule out zero rows.Source: §2.1 · p. 2
2.2. DC Penalty Reformulation
- The paper motivates the DC penalty because the earlier ℓ1 regularization does not guarantee the same global minimizers as the constrained problem.The DC penalty is sought to recover that equivalence at a finite parameter value.Source: §2.2 · p. 2
- The DC residual subtracts the sum of the n largest absolute entries from the entrywise ℓ1 norm, and vanishes exactly when ∥X∥_0 ≤ n.On the manifold, every X has at least n nonzeros, so this residual penalizes violations of the cardinality equality.Source: §2.2 · p. 2
- Penalizing the residual gives a Riemannian DC formulation that preserves the constrained problem’s global minimizers for a sufficiently large finite penalty parameter.The section establishes the equivalence by first deriving a global error bound.Source: §2.2 · p. 2
- For τ > 8K^2√n ∥A∥_2^2, the penalized and cardinality-constrained problems have the same global minimizers.The threshold follows from the global error bound and Lipschitz continuity of the objective on the manifold.Source: §2.2 · p. 2
3. THE PROPOSED RADA-DC ALGORITHM
The paper formulates RADA-DC for nonsmooth Riemannian DC optimization, combining dual regularization and DC linearization. Under stated assumptions it has an O(ε^-3) iteration bound, and the K-means penalty model is a special application.
3. THE PROPOSED RADA-DC ALGORITHM
- The general problem places a smooth, possibly nonconvex function and two closed convex, possibly nonsmooth functions over an embedded Riemannian submanifold.The paper identifies the K-means DC penalty formulation as a special case.Source: §3 · p. 2
3.1. Proposed Algorithm
- RADA-DC regularizes the inner maximization, linearizes the nonsmooth concave term, and alternates approximate manifold subproblem solves with dual updates.Each outer iteration uses a prescribed number of Riemannian gradient steps before updating the dual variable.Source: §3.1 · p. 3
3.2. Convergence Analysis
- For ε > 0, if Assumption 1 holds, the sequence generated by Algorithm 1 with λ = ε/(2Lh) contains an ε-RC point within O(ε^-3) iterations.Assumption 1 requires efficient computation of the proximal mapping of h and a subgradient of g at manifold points.Source: §3.2 · p. 3
3.3. Customized Application
- The algorithm applies to the K-means DC penalty model by setting M = F, f = fkm, h(X) = τ||X||1, and g(X) = τ||X||[n].For this application, the dual maximizer is obtained by projecting onto a box, and a subgradient uses the n largest-magnitude entries.Source: §3.3 · p. 3
4. NUMERICAL EXPERIMENTS
The experiments compare RADA-DC with I-AManPG and K-means++ in large-cluster settings. RADA-DC achieves lower objective values on average than tested baselines at competitive computational cost, with results reported for synthetic and image datasets.
4. NUMERICAL EXPERIMENTS
- Each setting is repeated 50 times; RADA-DC and I-AManPG share feasible spectral initialization, then their solutions initialize one Lloyd run.K-means++ uses 1000 independent starts per repetition, retaining the solution with the lowest final objective.Source: §4 · p. 4
4.2. Real-World Image Datasets
- Across ORL40 and Faces94, RADA-DC attains the lowest mean objective value and clustering error, and the shortest mean time except at ORL40 n = 360.Table 1 reports averages over 50 runs, with ORL40 outside and Faces94 inside parentheses.Source: Table 1 · p. 4, §4.2 · p. 4
4.1. Synthetic Data
- On synthetic data with K = 40, RADA-DC has the lowest mean objective value and substantially less total running time than K-means++.As sample count per cluster increases, RADA-DC's mean objective remains nearly unchanged and its running time grows moderately, unlike I-AManPG's increases.Source: §4.1 · p. 4
4.2. Real-World Image Datasets
- The image experiments use ORL40 with K = 40 and Faces94 with K = 50, sampling class-balanced instances across varying dataset sizes.Images are standardized and the leading K left singular vectors form the input matrix for all methods.Source: §4.2 · p. 4
4. NUMERICAL EXPERIMENTS
- In large-K settings, RADA-DC achieves lower objective values on average than tested baselines at competitive computational cost.RADA-DC solves a globally exact penalty model for sufficiently large finite penalty parameters, whereas equivalence is not generally guaranteed for I-AManPG's model.Source: §4.2 · p. 4, §4 · p. 4