An elementary proof of the Johnson-Lindenstrauss Lemma

@techreport{citeulike:1280964, 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=ffl 2 ) dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 \Sigma ffl). In this note, we prove this lemma using elementary probabilistic techniques. Computer Science Division, UC Berkeley. Email: dasgupta@cs.berkeley.edu. y Computer Science Division, UC Berkeley. Email: angup@cs.berkeley.edu. Supported by...}, address = {Berkeley, CA}, author = {Dasgupta, Sanjoy and Gupta, Anupam }, citeulike-article-id = {1280964}, keywords = {johnson, lemma, lindenstrauss}, number = {TR-99-006}, posted-at = {2007-12-17 06:16:19}, priority = {0}, title = {An elementary proof of the Johnson-Lindenstrauss Lemma}, url = {http://citeseer.ist.psu.edu/dasgupta99elementary.html}, year = {1999} }

TY - RPRT ID - citeulike:1280964 L3 - citeulike-article-id:1280964 TI - An elementary proof of the Johnson-Lindenstrauss Lemma IS - TR-99-006 AD - Berkeley, CA N2 - 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=ffl 2 ) dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 \Sigma ffl). In this note, we prove this lemma using elementary probabilistic techniques. Computer Science Division, UC Berkeley. Email: dasgupta@cs.berkeley.edu. y Computer Science Division, UC Berkeley. Email: angup@cs.berkeley.edu. Supported by... KW - johnson KW - lemma KW - lindenstrauss AU - Dasgupta, Sanjoy AU - Gupta, Anupam PY - 1999/// UR - http://citeseer.ist.psu.edu/dasgupta99elementary.html ER -