When Buffon’s needle problem meets the Johnson-Lindenstrauss Lemma
[caption id=“attachment_346” align=“alignnone” width=“640”]
“I suppose that in a room where the floor is simply divided by parallel joints one throws a stick (N/A: later called “needle”) in the air, and that one of the players bets that the stick will not cross any of the parallels on the floor, and that the other in contrast bets that the stick will cross some of these parallels; one asks for the chances of these two players.”
The English translation is due to [1]. The solution (published by Leclerc in 1777) is astonishingly simple: for a short needle compared to the separation $ \delta$ between two consecutive parallels, the probability of having one intersection between the needle and the parallels is equal to the needle length times $ \frac{1}{\pi\delta}$ ! If the needle is longer, then this probability is less easy to express but the expectation of the number of intersections (which can now be bigger than one) remains equal to this value. Surprisingly, this result still holds if the needle is replaced by a finite smooth curve that some authors then call the “noodle” problem (e.g., in [5]) The reason why this problem rang a bell is related to its similarity with a quantization process! Indeed, think for a while to the needle as the segment formed by two points $ \boldsymbol x,\boldsymbol y$ in the plane $ \mathbb R^2$ and assume all the parallel joints normal to the first canonical axis $ \boldsymbol e_1$ of $ \mathbb R^2$. Let us also think to the area defined by two consecutive joints as an infinite strip of width $ \delta$. Then, the number of intersections that this “needle” makes with the grid of parallel joints is related to the distance between the two strips occupied by the two points, i.e., to the distance between a uniform quantization (or rounding off) of the $ \boldsymbol e_1$-coordinate of the two points! From this observation, if I realized that if we randomly turn these two points with a random rotation $ \boldsymbol R$ of $ SO(2)$ and if a random translation $ u$ along the $ e_1$-axis is added to their coordinates, the context of the initial Buffon’s problem is exactly recovered! Interestingly enough, after this randomized transformation, the first coordinate of one of the two points (defining the needle extremities), say $ \boldsymbol x$, reads $ \boldsymbol e_1^T (\boldsymbol R \boldsymbol x + u \boldsymbol e_1) = (\boldsymbol R^T \boldsymbol e_1)^T \boldsymbol x + u\quad \sim\quad \boldsymbol \theta^T \boldsymbol x + u$ where $ \boldsymbol \theta$ is a uniform random variable on the circle $ \mathbb S^1 \subset \mathbb R^2$. What you observe on the right of the last equivalence is nothing but a random projection of the point $ \boldsymbol x$ on the direction $ \boldsymbol \theta \in \mathbb S^1$. This was really amazing to discover: after these very simple developments, I had in front of me a kind of triple equivalence between Buffon’s needle problem, quantization process in the plane and a well-known linear random projection procedure. This boded well for a possible extension of this context to high-dimensional (random) projection procedures, e.g., those used in common linear dimensionality reduction methods and in the compressed sensing theory. Actually, this gave me a new point of view for solving these two connected questions: How to combine the well-known Johnson-Lindenstrauss Lemma with a quantization of the embedding it proposes? What (new) distortion of the embedding can we expect from this non-linear operation? Let me recall the tenet of the JL Lemma: For a set $ \mathcal S \subset \mathbb R^N$ of $ S$ points, if you fix $ 0<\epsilon<1$ and $ \delta >0$, as soon as $ M > M_0 = O(\epsilon^{-2}\log S)$, there exist a mapping $ \boldsymbol f:\mathbb R^N\to \mathbb R^M$ such that, for all pairs $ \boldsymbol u,\boldsymbol v\in \mathcal S$, $ (1 - \epsilon)\,\|\boldsymbol u - \boldsymbol v\| \leq \|\boldsymbol f(\boldsymbol u) - \boldsymbol f(\boldsymbol v)\|\ \leq\ (1 + \epsilon)\|\boldsymbol u - \boldsymbol u\|,$
with some possible variants on the selected norms, e.g., from some measure concentration results in Banach space [6], the result is still true with the same condition on $ M$ if we take the $ \ell_1$ norm of $ \boldsymbol f(\boldsymbol u) - \boldsymbol f(\boldsymbol v)$. This is this variant that matters in the rest of this post.
It took me some while but after having generalized Buffon’s needle problem to a $ N$-dimensional space (where the needle is still a 1-D segment “thrown” randomly in a grid of $ (N-1)$-dimensional parallel hyperplane that are $ \delta>0$ apart) – which provided a few interesting asymptotic relations concerning this probabilistic problem – I was also able to generalize the previous equivalence as follows: Uniformly quantizing the random projections in $ \mathbb R^M$ of two points in $ \mathbb R^N$ and measuring the difference between their quantized values is fully equivalent to study the number of intersections made by the segment determined by those two points (seen as a Buffon’s needle) with a parallel grid of $ (N-1)$-dimensional hyperplanes. This equivalence was the starting point to discover the following proposition (the main result of the paper referenced above) which can be seen as a quantized form of the Johnson-Lindenstrauss Lemma: Let $ \mathcal S \subset \mathbb R^N$ be a set of $ S$ points. Fix $ 0<\epsilon<1$ and $ \delta >0$. For $ M > M_0 = O(\epsilon^{-2}\log S)$, there exist a non-linear mapping $ \boldsymbol \psi:\mathbb R^N\to \mathbb (\delta Z)^M$ and two constants $ c,c’>0$ such that, for all pairs $ \boldsymbol u,\boldsymbol v\in \mathcal S$, $ (1 - \epsilon)\,\|\boldsymbol u - \boldsymbol v\|\,-\,c\,\delta\,\epsilon\ \leq\ \frac{c’}{M} \|\boldsymbol \psi(\boldsymbol u)-\boldsymbol \psi(\boldsymbol v)\|_1 \ \leq\ (1 + \epsilon)\|\boldsymbol u-\boldsymbol v\|\,+\,c\,\delta\,\epsilon.$ Moreover, this mapping $ \boldsymbol \psi$ can be randomly constructed by $ \boldsymbol \psi(\boldsymbol u) = \mathcal Q_{\delta}(\boldsymbol \Phi \boldsymbol u + \boldsymbol \xi),$ where $ \mathcal Q$ is a uniform quantization of bin width $ \delta>0$, $ \boldsymbol \Phi$ is a $ M \times N$ Gaussian random matrix and $ \boldsymbol \xi$ is a uniform random vector over $ [0, \delta]^M$. Except for the quantization, this construction is similar to the one introduced in [7] (for non-regular quantizers). Without entering into the details, the explanation of this result comes from the fact that the random projection $ \boldsymbol \Phi$ can be seen as a random rotation of $ \mathbb R^N$ followed by a random scaling of the vector amplitude. Therefore, conditionally to this amplitude, the equivalence with Buffon’s problem is recovered for a (scaled) needle determined by the vectors $ \boldsymbol u$ and $ \boldsymbol v$ above, the dithering $ \boldsymbol \xi$ playing the role of the random needle shift. Interestingly, compared to the common JL Lemma, the mapping is now “quasi-isometric": we observe both an additive and a multiplicative distortions on the embedded distances of $ \boldsymbol u, \boldsymbol v \in \mathcal S$. These two distortions, however, decay as $ O(\sqrt{\log S/M})$ when $ M$ increases! This kind additive distortion decay was already observed for “binary” (or one-bit) quantization procedure [2, 3, 4] applied on random projection of points (e.g., for 1-bit compressed sensing). Above, we still observe such a distortion for the (multi-bit) quantization above and, moreover, this distortion is combined with a multiplicative one while both decay when $ M$ increases. This fact is new, to the best of my knowledge. Moreover, for coarse quantization, i.e., for high $ \delta$ compared to the typical size of $ \mathcal S$, the distortion is mainly additive, while for small $ \delta$ we tend to a classical Lipschitz isometric embedding, as provided by the JL Lemma. Interested blog reader can have a look to my paper for a clearer (I hope) presentation of this informal summary. His summary is as follows:
“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 show that there exists ``almost’’ a quasi-isometric embedding of $ (\mathcal S, \ell_2)$ in $ ( (\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((\log S/M)^{1/4})$.”
Hoping there is no killing bug in my developments, any comments are also welcome. References: [1] J. D. Hey, T. M. Neugebauer, and C. M. Pasca, “Georges-Louis Leclerc de Buffons Essays on Moral Arithmetic,” in The Selten School of Behavioral Economics, pp. 245–282. Springer, 2010. [2] L. Jacques, J. N. Laska, P. T. Boufounos, and R. G. Baraniuk, “Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors,” IEEE Transactions on Information Theory, Vol. 59(4), pp. 2082-2102, 2013. [3] Y. Plan and R. Vershynin, “One-bit compressed sensing by linear programming,” Communications on Pure and Applied Mathematics, to appear. arXiv:1109.4299, 2011. [4] M. Goemans and D. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” Journ. ACM, vol. 42, no. 6, pp. 1145, 1995. [5] J. F. Ramaley, “Buffon’s noodle problem,” The American Mathematical Monthly, vol. 76, no. 8, pp. 916–918, 1969. [6] M. Ledoux and M. Talagrand, Probability in Banach Spaces: Isoperimetry and Processes, Springer, 1991. [7] P. T. Boufounos, “Universal rate-efficient scalar quantization.” Information Theory, IEEE Transactions on 58.3 (2012): 1861-1872. [8] G. C. Buffon, “Essai d’arithmetique morale,” Supplément à l’histoire naturelle, vol. 4, 1777. See also: [http://www. buffon.cnrs.fr](http://www. buffon.cnrs.fr)
