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/ϵ2)‐dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 ± ϵ). In this note, we prove this theorem using elementary probabilistic techniques. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 22: 60–65, 2002