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

作者：Jacques Laurent^*

来源：IEEE Transactions on Information Theory, 2015, 61(9): 5012-5027.

DOI：10.1109/TIT.2015.2453355

• Compressed sensing
• quantization
• Johnson Lindenstrauss lemma
• nonlinear dimensionality reduction
• random projections

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 paper, 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 S subset of 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 (S, l(2)) to (delta Z(M), l(1)) that approximately preserves the pairwise distances between the points of S. Interestingly, compared with 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 with 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 (S, l(2)) into (delta Z(M), l(2)). This one involves a non-linear distortion of the l(2)-distance in 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)).

• 出版日期2015-9