An Elementary Proof of the Johnson-Lindenstrauss Lemma
Title | An Elementary Proof of the Johnson-Lindenstrauss Lemma |
Publication Type | Technical Report |
Year of Publication | 1999 |
Authors | Dasgupta, S., & Gupta A. |
Other Numbers | 1162 |
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. |
URL | http://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 |