A Quantized Johnson Lindenstrauss Lemma The Finding Of Buffons Needle
Jacques Laurent. Arxiv 2013
[Paper]
ARXIV
Quantisation
Unsupervised
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 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 . In particular, given a finite set of points and a distortion level , as soon as , we can (randomly) construct a mapping from
to that approximately
preserves the pairwise distances between the points of .
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 when increases. Moreover, for coarse quantization, i.e., for high
compared to the set radius, the distortion is mainly additive, while
for small we tend to a Lipschitz isometric embedding. Finally, we
prove the existence of a “nearly” quasi-isometric embedding of into . This one involves a non-linear
distortion of the -distance in that vanishes for distant
points in this set. Noticeably, the additive distortion in this case is slower,
and decays as .
Similar Work
