# Sum-of-norms clustering does not separate nearby balls

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 28 Apr 2021.

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

- [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)
- [Relax, no need to round: integrality of clustering formulations](https://mlsanity.com/paper/1408.4045/) (2014)
- [Recovering Trees with Convex Clustering](https://mlsanity.com/paper/1806.11096/) (2018)
- [Probably certifiably correct k-means clustering](https://mlsanity.com/paper/1509.07983/) (2015)
- [When Do Birds of a Feather Flock Together? k-Means, Proximity, and Conic Programming](https://mlsanity.com/paper/1710.06008/) (2017)
- [Recovery of a mixture of Gaussians by sum-of-norms clustering](https://mlsanity.com/paper/1902.07137/) (2019)
- [The ratio-cut polytope and K-means clustering](https://mlsanity.com/paper/2006.15225/) (2020)
- [Convex clustering via ℓ1 fusion penalization](https://mlsanity.com/paper/1412.0753/) (2014)
- [Recovery guarantees for exemplar-based clustering](https://mlsanity.com/paper/1309.3256/) (2013)
- [Certifying clusters from sum-of-norms clustering](https://mlsanity.com/paper/2006.11355/) (2020)

## 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)
- [Affinity Graph Connectivity in Convex Clustering](https://mlsanity.com/paper/2605.24673/) (2026)

## Abstract (arXiv)

Sum-of-norms clustering is a popular convexification of K-means clustering. We show that, if the dataset is made of a large number of independent random variables distributed according to the uniform measure on the union of two disjoint balls of unit radius, and if the balls are sufficiently close to one another, then sum-of-norms clustering will typically fail to recover the decomposition of the dataset into two clusters. As the dimension tends to infinity, this happens even when the distance between the centers of the two balls is taken to be as large as 2√2. In order to show this, we introduce and analyze a continuous version of sum-of-norms clustering, where the dataset is replaced by a general measure. In particular, we state and prove a local-global characterization of the clustering that seems to be new even in the case of discrete datapoints.