On variants of the Johnson-Lindenstrauss lemma

The Johnson-Lindenstrauss lemma asserts that an n-point set in any Euclidean space can be mapped to a Euclidean space of dimension k = O(epsilon(-2) log n) so that all distances are preserved up to a multiplicative factor between 1 - epsilon and 1 + epsilon. Known proofs obtain such a mapping as a linear map R-n -> R-k with a suitable random matrix. We give a simple and self-contained proof of a version of the Johnson-Lindenstrauss lemma that subsumes a basic versions by Indyk and Motwani and a version more suitable for efficient computations due to Achlioptas. (Another proof of this result, slightly different but in a similar spirit, was given independently by Indyk and Naor.) An even more general result was established by Klartag and Mendelson using considerably heavier machinery. Recently, Ailon and Chazelle showed, roughly speaking, that a good mapping can also be obtained by composing a suitable Fourier transform with a linear mapping that has a sparse random matrix M; a mapping of this form can be evaluated very fast. In their result, the nonzero entries of At are normally distributed. We show that the nonzero entries can be chosen as random +/-1, which further speeds up the computation. We also discuss the case of embeddings into R-k with the l(1) norm. (C) 2008 Wiley Periodicals, Inc.