# Local versions of sum-of-norms clustering

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 20 Sep 2021.

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

- [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)
- [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)
- [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)
- [K-median: exact recovery in the extended stochastic ball model](https://mlsanity.com/paper/2109.02547/) (2021)

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

- [Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees](https://mlsanity.com/paper/2303.16841/) (2023)
- [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)
- [Affinity Graph Connectivity in Convex Clustering](https://mlsanity.com/paper/2605.24673/) (2026)

## Abstract (arXiv)

Sum-of-norms clustering is a convex optimization problem whose solution can be used for the clustering of multivariate data. We propose and study a localized version of this method, and show in particular that it can separate arbitrarily close balls in the stochastic ball model. More precisely, we prove a quantitative bound on the error incurred in the clustering of disjoint connected sets. Our bound is expressed in terms of the number of datapoints and the localization length of the functional.