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. In particular, for the important case of polynomially small error and constant distortion, we give a generator with seed-length O((log d)(log log d)). Previous constructions required $\Omega(log^2 d)$ 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 $\Omega(\log(1/\delta)/\epsilon^2)$ on the
embedding dimension. Previously, Jayram and Woodruff [JW11] used communication complexity techniques to show a similar
bound.
Merger of two works - has two different constructions. Fixes a mistake in the use of samplers from previous version.
The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known constructions of linear embeddings that satisfy the Johnson-Lindenstrauss property involve randomness. We address the question of explicitly constructing such embedding families and provide a construction with an almost optimal use of randomness: we use $O(\log(n/\delta) \log(\log(n/\delta)/\epsilon))$ random bits for embedding $\ell_2^n$ into $\ell_2^s$ with error probability $\delta$, and distortion at most $\epsilon$, where $s = O(\log(1/\delta)/\epsilon^2)$.
In particular, for $\delta = 1/poly(n)$ and fixed $\epsilon > 0$, our construction uses $O(\log n \log \log n)$ random bits. Previous constructions required at least $O(\log^2 n)$ random bits to get polynomially small error.
The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known constructions of linear embeddings that satisfy the Johnson-Lindenstrauss property involve randomness. We address the question of explicitly constructing such embedding families and provide a construction with an almost optimal use of randomness: we use $O(\log(n/\delta) \log(\log(n/\delta)/\epsilon))$ random bits for embedding $\ell_2^n$ into $\ell_2^s$ with error probability $\delta$, and distortion at most $\epsilon$, where $s = O(\log(1/\delta)/\epsilon^2)$.
In particular, for $\delta = 1/poly(n)$ and fixed $\epsilon > 0$, our construction uses $O(\log n \log \log n)$ random bits. Previous constructions required at least $O(\log^2 n)$ random bits to get polynomially small error.
