Techreport,
An elementary proof of the Johnson-Lindenstrauss Lemma
(1999)
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 NSF grant CCR-9505448. 1 Introduction Johnson and Lindenstrauss 6 proved a fundamental result, which said that any n point set in Euclidean space could be embedded in O(log n=ffl 2 ) dimensions without distorting the distances between any pair of points by more than a factor of (1 \Sigma ffl), for any 0 ! ffl ! 1. Recently, this lemma has found several applications, including Lipschitz embeddings of graphs into normed spaces 7 and searching for approximate nearest neighbours 5. The ori...
