# Re-embedding data to strengthen recovery guarantees of clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 21 references that are in the map.
- First posted on arXiv 26 Jan 2023.

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

- [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)
- [Recovery of a mixture of Gaussians by sum-of-norms clustering](https://mlsanity.com/paper/1902.07137/) (2019)
- [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)

## Abstract (arXiv)

We propose a clustering method that involves chaining four known techniques into a pipeline yielding an algorithm with stronger recovery guarantees than any of the four components separately. Given n points in mathbb Rd, the first component of our pipeline, which we call leapfrog distances, is reminiscent of density-based clustering, yielding an n× n distance matrix. The leapfrog distances are then translated to new embeddings using multidimensional scaling and spectral methods, two other known techniques, yielding new embeddings of the n points in mathbb Rd', where d' satisfies d'll d in general. Finally, sum-of-norms (SON) clustering is applied to the re-embedded points. Although the fourth step (SON clustering) can in principle be replaced by any other clustering method, our focus is on provable guarantees of recovery of underlying structure. Therefore, we establish that the re-embedding improves recovery SON clustering, since SON clustering is a well-studied method that already has provable guarantees.