# Simple, unified analysis of Johnson-Lindenstrauss with applications

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 32 references that are in the map.
- First posted on arXiv 10 Feb 2024.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Epistemic Neural Networks](https://mlsanity.com/paper/2107.08924/) (2021)
- [Hypermodels for Exploration](https://mlsanity.com/paper/2006.07464/) (2020)
- [Approximate Thompson Sampling via Epistemic Neural Networks](https://mlsanity.com/paper/2302.09205/) (2023)
- [Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent](https://mlsanity.com/paper/2402.10228/) (2024)

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

- [Probability Tools for Sequential Random Projection](https://mlsanity.com/paper/2402.14026/) (2024)

## Abstract (arXiv)

We present a simplified and unified analysis of the Johnson-Lindenstrauss (JL) lemma, a cornerstone of dimensionality reduction for managing high-dimensional data. Our approach simplifies understanding and unifies various constructions under the JL framework, including spherical, binary-coin, sparse JL, Gaussian, and sub-Gaussian models. This unification preserves the intrinsic geometry of data, essential for applications from streaming algorithms to reinforcement learning. We provide the first rigorous proof of the spherical construction's effectiveness and introduce a general class of sub-Gaussian constructions within this simplified framework. Central to our contribution is an innovative extension of the Hanson-Wright inequality to high dimensions, complete with explicit constants. By using simple yet powerful probabilistic tools and analytical techniques, such as an enhanced diagonalization process, our analysis solidifies the theoretical foundation of the JL lemma by removing an independence assumption and extends its practical applicability to contemporary algorithms.