# Toward a unified theory of sparse dimensionality reduction in Euclidean space

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2013.

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

- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Tensor Random Projection for Low Memory Dimension Reduction](https://mlsanity.com/paper/2105.00105/) (2021)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Hashing embeddings of optimal dimension, with applications to linear least squares](https://mlsanity.com/paper/2105.11815/) (2021)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)
- [Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity](https://mlsanity.com/paper/2411.08773/) (2024)
- [Estimating leverage scores via rank revealing methods and randomization](https://mlsanity.com/paper/2105.11004/) (2021)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [Learning-Augmented Sketches for Hessians](https://mlsanity.com/paper/2102.12317/) (2021)
- [Confidence-Optimal Random Embeddings](https://mlsanity.com/paper/2104.05628/) (2021)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2306.06611/) (2023)
- [ℓp-Regression in the Arbitrary Partition Model of Communication](https://mlsanity.com/paper/2307.05117/) (2023)

## Abstract (arXiv)

Let Phi∈ℝm× n be a sparse Johnson-Lindenstrauss transform [KN14] with s non-zeroes per column. For a subset T of the unit sphere, varepsilon∈(0,1/2) given, we study settings for m,s required to ensure  mathopmathbbE_Phi supx∈ T left||Phi x|22 - 1 right| < varepsilon ,  i.e. so that Phi preserves the norm of every x∈ T simultaneously and multiplicatively up to 1+varepsilon. We introduce a new complexity parameter, which depends on the geometry of T, and show that it suffices to choose s and m such that this parameter is small. Our result is a sparse analog of Gordon's theorem, which was concerned with a dense Phi having i.i.d. Gaussian entries. We qualitatively unify several results related to the Johnson-Lindenstrauss lemma, subspace embeddings, and Fourier-based restricted isometries. Our work also implies new results in using the sparse Johnson-Lindenstrauss transform in numerical linear algebra, classical and model-based compressed sensing, manifold learning, and constrained least squares problems such as the Lasso.