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

DOI10.1109/TIT.2015.2453355zbMATH Open1359.81065arXiv1309.1507OpenAlexW2963673760WikidataQ124821727 ScholiaQ124821727MaRDI QIDQ2977299FDOQ2977299

Authors: Laurent Jacques 

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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 $mathcalSsubsetmathbb{R}^N$ of $S$ points and a distortion level $epsilon>0$, as soon as $M>M_0=O(epsilo{n}^{-2}logS)$, we can (randomly) construct a mapping from $(mathcalS,el{l}_2)$ to $(deltamathbb{Z}^M,el{l}_1)$ that approximately preserves the pairwise distances between the points of $mathcalS$. 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(logS)/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 $(mathcalS,el{l}_2)$ into $(deltamathbb{Z}^M,el{l}_2)$. This one involves a non-linear distortion of the $el{l}_2$-distance in $mathcalS$ that vanishes for distant points in this set. Noticeably, the additive distortion in this case is slower, and decays as $O(sqrt[4](logS)/M)$.

Full work available at URL: https://arxiv.org/abs/1309.1507

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Cited In (9)

• On variants of the Johnson–Lindenstrauss lemma
• \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\)
• Fast Metric Embedding into the Hamming Cube
• Binary vectors for fast distance and similarity estimation
• Quantization and compressive sensing
• Quantized compressed sensing: a survey
• Representation and coding of signal geometry
• Time for dithering: fast and quantized random embeddings via the restricted isometry property
• Endpoint results for Fourier integral operators on noncompact symmetric spaces

This page was built for publication: A Quantized Johnson–Lindenstrauss Lemma: The Finding of Buffon’s Needle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977299)