Publication at Faculty of Mathematics and Physics |
2008
Abstract
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 of R^n to 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.