# A Quantized Johnson Lindenstrauss Lemma: The Finding of Buffon's Needle

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2013.

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

- [QLESS: A Quantized Approach for Data Valuation and Selection in Large Language Model Fine-Tuning](https://mlsanity.com/paper/2502.01703/) (2025)
- [Image Coding for Machines via Feature-Preserving Rate-Distortion Optimization](https://mlsanity.com/paper/2504.02216/) (2025)
- [Sparse-Inductive Generative Adversarial Hashing for Nearest Neighbor Search](https://mlsanity.com/paper/2306.06928/) (2023)
- [L2G-Net: Local to Global Spectral Graph Neural Networks via Cauchy Factorizations](https://mlsanity.com/paper/2602.18837/) (2026)

## Abstract (arXiv)

In 1733, Georges-Louis Leclerc, Comte de Buffon in France, set the ground of geometric probability theory by defining an enlightening problem: What is the probability that a needle thrown randomly on a ground made of equispaced parallel strips lies on two of them? In this work, we show that the solution to this problem, and its generalization to N dimensions, allows us to discover a quantized form of the Johnson-Lindenstrauss (JL) Lemma, i.e., one that combines a linear dimensionality reduction procedure with a uniform quantization of precision δ>0. In particular, given a finite set mathcal S subset mathbb RN of S points and a distortion level ε>0, as soon as M > M0 = O(ε-2 log S), we can (randomly) construct a mapping from (mathcal S, ℓ2) to (δmathbb ZM, ℓ1) that approximately preserves the pairwise distances between the points of mathcal S. Interestingly, compared to the common JL Lemma, the mapping is quasi-isometric and we observe both an additive and a multiplicative distortions on the embedded distances. These two distortions, however, decay as O(√(log S)/M) when M increases. Moreover, for coarse quantization, i.e., for high δ compared to the set radius, the distortion is mainly additive, while for small δ we tend to a Lipschitz isometric embedding. Finally, we prove the existence of a "nearly" quasi-isometric embedding of (mathcal S, ℓ2) into (δmathbb ZM, ℓ2). This one involves a non-linear distortion of the ℓ2-distance in mathcal S that vanishes for distant points in this set. Noticeably, the additive distortion in this case is slower, and decays as O(√[4](log S)/M).