Almost Optimal Explicit Johnson-Lindenstrauss Families

Abstract

The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms. Constructions of linear embeddings satisfying the Johnson Lindenstrauss property necessarily involve randomness and much attention has been given to obtain explicit constructions minimizing the number of random bits used. In this work we give explicit constructions with an almost optimal use of randomness: For 0 < ε, δ < 1/2, we obtain explicit generators G : {0, 1} r → R s×d for s = O(log(1/δ)/ε2) such that for all d-dimensional vectors w of Euclidean norm 1, Pry∈u{0,1}r [ |kG(y)wk 2 − 1| > ε ] ≤ δ, with seed-length r = O log d + log(1/δ) · loglog(1/δ)ε. In particular, for δ = 1/ poly(d) and fixed ε > 0, we obtain seed-length O((log d)(log log d)). Previous constructions required Ω(log2d) random bits to obtain polynomially small error. We also give a new elementary proof of the optimality of the JL lemma showing a lower bound of Ω(log(1/δ)/ε2) on the embedding dimension. Previously, Jayram and Woodruff [9] used communication complexity techniques to show a similar bound.