# The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2022.

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

- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Differentially Private Wasserstein Barycenters](https://mlsanity.com/paper/2510.03021/) (2025)
- [Improved Coresets for Euclidean k-Means](https://mlsanity.com/paper/2211.08184/) (2022)
- [Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures](https://mlsanity.com/paper/2506.00165/) (2025)

## Abstract (arXiv)

We study the effect of Johnson-Lindenstrauss transforms in various projective clustering problems, generalizing recent results which only applied to center-based clustering [MMR19]. We ask the general question: for a Euclidean optimization problem and an accuracy parameter ε ∈ (0, 1), what is the smallest target dimension t ∈ mathbbN such that a Johnson-Lindenstrauss transform Pi colon ℝd → ℝt preserves the cost of the optimal solution up to a (1+ε)-factor. We give a new technique which uses coreset constructions to analyze the effect of the Johnson-Lindenstrauss transform. Our technique, in addition applying to center-based clustering, improves on (or is the first to address) other Euclidean optimization problems, including: bullet For (k,z)-subspace approximation: we show that t = tildeO(zk2 / ε3) suffices, whereas the prior best bound, of O(k/ε2), only applied to the case z = 2 [CEMMP15]. bullet For (k,z)-flat approximation: we show t = tildeO(zk2/ε3) suffices, completely removing the dependence on n from the prior bound tildeO(zk2 log n/ε3) of [KR15]. bullet For (k,z)-line approximation: we show t = O((k log log n + z + log(1/ε)) / ε3) suffices, and ours is the first to give any dimension reduction result.