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

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 $delta>0$. In particular, given a finite set $mathcal S subset mathbb R^N$ of $S$ points and a distortion level $epsilon>0$, as soon as $M > M_0 = O(epsilon^{-2} log S)$, we can (randomly) construct a mapping from $(mathcal S, ell_2)$ to $(deltamathbb Z^M, ell_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(sqrt{(log S)/M})$ when $M$ increases. Moreover, for coarse quantization, i.e., for high $delta$ compared to the set radius, the distortion is mainly additive, while for small $delta$ we tend to a Lipschitz isometric embedding. Finally, we prove the existence of a "nearly" quasi-isometric embedding of $(mathcal S, ell_2)$ into $(deltamathbb Z^M, ell_2)$. This one involves a non-linear distortion of the $ell_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(sqrt[4]{(log S)/M})$.