Publication Details

Title: An Elementary Proof of the Johnson-Lindenstrauss Lemma
Author: S. Dasgupta and A. Gupta
Bibliographic Information: ICSI Technical Report TR-99-006
Date: March 1999
Research Area: [Research Area not defined]
Type: Technical Reports
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1999/tr-99-006.pdf

Overview:
The Johnson-Lindenstrauss lemma shows that a set of n points in high dimensional Euclidean space can be mapped down into an O(log n/e^2) dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 ± e). In this report, we prove this lemma using elementary probabilistic techniques and show that it is essentially tight.

Bibliographic Reference:
S. Dasgupta and A. Gupta. An Elementary Proof of the Johnson-Lindenstrauss Lemma. ICSI Technical Report TR-99-006, March 1999