# Splitting Methods for Convex Clustering

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Apr 2013.

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

- [Reinforcement Learning with Heterogeneous Data: Estimation and Inference](https://mlsanity.com/paper/2202.00088/) (2022)
- [Local versions of sum-of-norms clustering](https://mlsanity.com/paper/2109.09589/) (2021)
- [Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering](https://mlsanity.com/paper/2211.01877/) (2022)
- [Multi-Prototypes Convex Merging Based K-Means Clustering Algorithm](https://mlsanity.com/paper/2302.07045/) (2023)
- [Sum-of-norms clustering does not separate nearby balls](https://mlsanity.com/paper/2104.13753/) (2021)
- [On Convex Clustering Solutions](https://mlsanity.com/paper/2105.08348/) (2021)
- [Supervised Multivariate Learning with Simultaneous Feature Auto-grouping and Dimension Reduction](https://mlsanity.com/paper/2112.09746/) (2021)
- [A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments](https://mlsanity.com/paper/2209.10866/) (2022)
- [Converting ADMM to a Proximal Gradient for Efficient Sparse Estimation](https://mlsanity.com/paper/2104.10911/) (2021)
- [Network Clustering for Latent State and Changepoint Detection](https://mlsanity.com/paper/2111.01273/) (2021)
- [Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees](https://mlsanity.com/paper/2303.16841/) (2023)
- [Causal Clustering for Conditional Average Treatment Effects Estimation and Subgroup Discovery](https://mlsanity.com/paper/2509.05775/) (2025)
- [Fitting Sparse Markov Models to Categorical Time Series Using Convex Clustering](https://mlsanity.com/paper/2202.05485/) (2022)
- [Inference of Multiscale Gaussian Graphical Model](https://mlsanity.com/paper/2202.05775/) (2022)
- [Fusion Subspace Clustering for Incomplete Data](https://mlsanity.com/paper/2205.10872/) (2022)
- [Simple and Scalable Algorithms for Cluster-Aware Precision Medicine](https://mlsanity.com/paper/2211.16553/) (2022)
- [Re-embedding data to strengthen recovery guarantees of clustering](https://mlsanity.com/paper/2301.10901/) (2023)
- [Clusterpath Gaussian Graphical Modeling](https://mlsanity.com/paper/2407.00644/) (2024)
- [Adaptive Self-supervised Robust Clustering for Unstructured Data with Unknown Cluster Number](https://mlsanity.com/paper/2407.20119/) (2024)
- [Tree-Guided L1-Convex Clustering](https://mlsanity.com/paper/2503.24012/) (2025)
- [Bilevel Models for Adversarial Learning and A Case Study](https://mlsanity.com/paper/2510.25121/) (2025)
- [A New Framework for Convex Clustering in Kernel Spaces: Finite Sample Bounds, Consistency and Performance Insights](https://mlsanity.com/paper/2511.05159/) (2025)
- [Convex Clustering Redefined: Robust Learning with the Median of Means Estimator](https://mlsanity.com/paper/2511.14784/) (2025)
- [Sparse Convex Biclustering](https://mlsanity.com/paper/2601.01757/) (2026)
- [Biconvex Biclustering](https://mlsanity.com/paper/2604.03936/) (2026)
- [A Unified Framework for Structure-Aware Clustering and Heterogeneous Causal Graph Learning](https://mlsanity.com/paper/2605.19313/) (2026)
- [Affinity Graph Connectivity in Convex Clustering](https://mlsanity.com/paper/2605.24673/) (2026)
- [Range Penalization: Theoretical Insights with Applications in Federated Learning](https://mlsanity.com/paper/2606.10916/) (2026)

## Abstract (arXiv)

Clustering is a fundamental problem in many scientific applications. Standard methods such as k-means, Gaussian mixture models, and hierarchical clustering, however, are beset by local minima, which are sometimes drastically suboptimal. Recently introduced convex relaxations of k-means and hierarchical clustering shrink cluster centroids toward one another and ensure a unique global minimizer. In this work we present two splitting methods for solving the convex clustering problem. The first is an instance of the alternating direction method of multipliers (ADMM); the second is an instance of the alternating minimization algorithm (AMA). In contrast to previously considered algorithms, our ADMM and AMA formulations provide simple and unified frameworks for solving the convex clustering problem under the previously studied norms and open the door to potentially novel norms. We demonstrate the performance of our algorithm on both simulated and real data examples. While the differences between the two algorithms appear to be minor on the surface, complexity analysis and numerical experiments show AMA to be significantly more efficient.