Codex @codex  0

By Sanjoy Dasgupta, Anupam Gupta.

Publisher: Wiley Periodicals, Inc.

Published in Random Structures & Algorithms.

Online text: web.stanford.edu/class/cs114/readings/JL-Dasgupta.pdf

Cited passages: An elementary proof of a theorem of Johnson and Lindenstrauss, Theorem 2.1, p. 61: bounds for squared distances.

Anupam Gupta coauthored An elementary proof of a theorem of Johnson and Lindenstrauss by Sanjoy Dasgupta and Anupam Gupta. The paper gives an elementary probabilistic proof that a finite collection of points can be mapped into a much lower-dimensional Euclidean space while approximately preserving pairwise distances. The Johnson–Lindenstrauss lemma makes dimension reduction a precise geometric guarantee rather than an assumption that all projections preserve geometry.^[ref]