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

Type
Publication
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)$$.