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

IEEE Transactions on Information Theory

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 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 \((\delta\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(\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 \((\delta\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(\sqrt[4]{\log S}/M)\).