An elementary proof of a theorem of Johnson and Lindenstrauss

Abstract 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