# Recovery of a mixture of Gaussians by sum-of-norms clustering

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2019.

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

- [Local versions of sum-of-norms clustering](https://mlsanity.com/paper/2109.09589/) (2021)
- [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)
- [Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees](https://mlsanity.com/paper/2303.16841/) (2023)
- [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)
- [Adaptive Self-supervised Robust Clustering for Unstructured Data with Unknown Cluster Number](https://mlsanity.com/paper/2407.20119/) (2024)

## Abstract (arXiv)

Sum-of-norms clustering is a method for assigning n points in ℝd to K clusters, 1≤ K≤ n, using convex optimization. Recently, Panahi et al. proved that sum-of-norms clustering is guaranteed to recover a mixture of Gaussians under the restriction that the number of samples is not too large. The purpose of this note is to lift this restriction, i.e., show that sum-of-norms clustering with equal weights can recover a mixture of Gaussians even as the number of samples tends to infinity. Our proof relies on an interesting characterization of clusters computed by sum-of-norms clustering that was developed inside a proof of the agglomeration conjecture by Chiquet et al. Because we believe this theorem has independent interest, we restate and reprove the Chiquet et al. result herein.