# On Convex Clustering Solutions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 24 references that are in the map.
- First posted on arXiv 18 May 2021.

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

- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [Network Lasso: Clustering and Optimization in Large Graphs](https://mlsanity.com/paper/1507.00280/) (2015)
- [Splitting Methods for Convex Clustering](https://mlsanity.com/paper/1304.0499/) (2013)
- [Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm](https://mlsanity.com/paper/1810.02677/) (2018)
- [Statistical Properties of Convex Clustering](https://mlsanity.com/paper/1503.08340/) (2015)
- [Recovering Trees with Convex Clustering](https://mlsanity.com/paper/1806.11096/) (2018)
- [Recovery of a mixture of Gaussians by sum-of-norms clustering](https://mlsanity.com/paper/1902.07137/) (2019)
- [Learning on Hypergraphs with Sparsity](https://mlsanity.com/paper/1804.00836/) (2018)
- [An Efficient Semismooth Newton Based Algorithm for Convex Clustering](https://mlsanity.com/paper/1802.07091/) (2018)

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

- [Local versions of sum-of-norms clustering](https://mlsanity.com/paper/2109.09589/) (2021)
- [Re-embedding data to strengthen recovery guarantees of clustering](https://mlsanity.com/paper/2301.10901/) (2023)
- [Adaptive Self-supervised Robust Clustering for Unstructured Data with Unknown Cluster Number](https://mlsanity.com/paper/2407.20119/) (2024)

## Abstract (arXiv)

Convex clustering is an attractive clustering algorithm with favorable properties such as efficiency and optimality owing to its convex formulation. It is thought to generalize both k-means clustering and agglomerative clustering. However, it is not known whether convex clustering preserves desirable properties of these algorithms. A common expectation is that convex clustering may learn difficult cluster types such as non-convex ones. Current understanding of convex clustering is limited to only consistency results on well-separated clusters. We show new understanding of its solutions. We prove that convex clustering can only learn convex clusters. We then show that the clusters have disjoint bounding balls with significant gaps. We further characterize the solutions, regularization hyperparameters, inclusterable cases and consistency.