# Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 29 Mar 2023.

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

- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [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)
- [Provable Convex Co-clustering of Tensors](https://mlsanity.com/paper/1803.06518/) (2018)
- [The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction](https://mlsanity.com/paper/1411.2404/) (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)
- [Convex clustering via ℓ1 fusion penalization](https://mlsanity.com/paper/1412.0753/) (2014)
- [An Efficient Semismooth Newton Based Algorithm for Convex Clustering](https://mlsanity.com/paper/1802.07091/) (2018)
- [Local versions of sum-of-norms clustering](https://mlsanity.com/paper/2109.09589/) (2021)
- [A Dimension Reduction Technique for Large-scale Structured Sparse Optimization Problems with Application to Convex Clustering](https://mlsanity.com/paper/2108.07462/) (2021)

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

- [Adaptive Self-supervised Robust Clustering for Unstructured Data with Unknown Cluster Number](https://mlsanity.com/paper/2407.20119/) (2024)

## Abstract (arXiv)

In this paper, we propose a randomly projected convex clustering model for clustering a collection of n high dimensional data points in ℝd with K hidden clusters. Compared to the convex clustering model for clustering original data with dimension d, we prove that, under some mild conditions, the perfect recovery of the cluster membership assignments of the convex clustering model, if exists, can be preserved by the randomly projected convex clustering model with embedding dimension m = O(ε-2log(n)), where 0 < ε < 1 is some given parameter. We further prove that the embedding dimension can be improved to be O(ε-2log(K)), which is independent of the number of data points. Extensive numerical experiment results will be presented in this paper to demonstrate the robustness and superior performance of the randomly projected convex clustering model. The numerical results presented in this paper also demonstrate that the randomly projected convex clustering model can outperform the randomly projected K-means model in practice.