An Elementary Proof of the Johnson-Lindenstrauss Lemma

TitleAn Elementary Proof of the Johnson-Lindenstrauss Lemma
Publication TypeTechnical Report
Year of Publication1999
AuthorsDasgupta, S., & Gupta A.
Other Numbers1162
Abstract

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.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1999/tr-99-006.pdf
Bibliographic Notes

ICSI Technical Report TR-99-006

Abbreviated Authors

S. Dasgupta and Anupam Gupta

ICSI Publication Type

Technical Report