An elementary proof of a theorem of Johnson and Lindenstrauss

A result of Johnson and Lindenstrauss [13] shows that a set of n points in high dimensional Euclidean space can be mapped into an O(log n/epsilon(2))-dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 +/- epsilon). In this note, we prove this theorem using elementary probabilistic techniques. (C) 2002 Wiley Periodicals. Inc.