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 δ>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).