When Buffon’s needle problem helps in quantizing the Johnson-Lindenstrauss Lemma

Abstract: 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 presentation, we will 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 ⊂ \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 \(((δ \mathbb 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( (\log(S/M))^{1/2})\) 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 δ the embedding tends to a Lipschitz isometric embedding.

We will also explain that there exists “almost” a quasi-isometric embedding of \((\mathcal S, \ell_{2})\) in \(((δ \mathbb 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((\log(S/M))^{1/4})\).

Finally, the presentation will be illustrated by simple numerical simulations showing that the additive and the multiplicative errors behave as predicted when \(\delta\) and \(M\) vary.