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

Date
May 19, 2014
Event
“5th International Conference on Computational Harmonic Analysis Program” (ICCHA5)
Location
Vanderbilt University, TN, USA

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.