# Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 55 references that are in the map.
- First posted on arXiv 3 Nov 2022.

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

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning](https://mlsanity.com/paper/1402.4419/) (2014)
- [Splitting Methods for Convex Clustering](https://mlsanity.com/paper/1304.0499/) (2013)
- [Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization](https://mlsanity.com/paper/1306.4650/) (2013)
- [Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm](https://mlsanity.com/paper/1810.02677/) (2018)
- [Recovering Trees with Convex Clustering](https://mlsanity.com/paper/1806.11096/) (2018)
- [Convex Biclustering](https://mlsanity.com/paper/1408.0856/) (2014)
- [Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs](https://mlsanity.com/paper/1409.8147/) (2014)
- [Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization](https://mlsanity.com/paper/1901.01477/) (2019)
- [Solution Path Clustering with Adaptive Concave Penalty](https://mlsanity.com/paper/1404.6289/) (2014)
- [Relaxed Majorization-Minimization for Non-smooth and Non-convex Optimization](https://mlsanity.com/paper/1511.08062/) (2015)

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

- [Causal Clustering for Conditional Average Treatment Effects Estimation and Subgroup Discovery](https://mlsanity.com/paper/2509.05775/) (2025)
- [Clusterpath Gaussian Graphical Modeling](https://mlsanity.com/paper/2407.00644/) (2024)
- [Tree-Guided L1-Convex Clustering](https://mlsanity.com/paper/2503.24012/) (2025)
- [Affinity Graph Connectivity in Convex Clustering](https://mlsanity.com/paper/2605.24673/) (2026)

## Abstract (arXiv)

Convex clustering is a modern method with both hierarchical and k-means clustering characteristics. Although convex clustering can capture complex clustering structures hidden in data, the existing convex clustering algorithms are not scalable to large data sets with sample sizes greater than several thousands. Moreover, it is known that convex clustering sometimes fails to produce a complete hierarchical clustering structure. This issue arises if clusters split up or the minimum number of possible clusters is larger than the desired number of clusters. In this paper, we propose convex clustering through majorization-minimization (CCMM) -- an iterative algorithm that uses cluster fusions and a highly efficient updating scheme derived using diagonal majorization. Additionally, we explore different strategies to ensure that the hierarchical clustering structure terminates in a single cluster. With a current desktop computer, CCMM efficiently solves convex clustering problems featuring over one million objects in seven-dimensional space, achieving a solution time of 51 seconds on average.