Publications

"An Elementary Proof of the Johnson-Lindenstrauss Lemma"

S. Dasgupta and A. Gupta

ICSI Technical Report TR-99-006

March 1999

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 \pm \e)$. In this report, we prove this lemma using elementary probabilistic techniques and show that it is essentially tight.