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 n dimensions to O(log(1 delta) epsilon^2) dimensions with error probability at most delta, and distortion at most epsilon. In particular, for delta = 1 poly(n) and fixed epsilon, we use O(log n loglog n) random bits. Previous constructions required at least O(log^2 n) random bits to get polynomially small error.
Independently, Kane and Nelson @cite_12 obtained a construction that is similar in spirit to ours and achieves a slightly better seed-length of @math . Note that for the important case of @math polynomially small, our seed-length is the same as theirs.
@cite_12
2114773674
Recent work of [Dasgupta-Kumar-Sarlos, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in our proof is improved. The main ingredient in our proof is a spectral moment bound for quadratic forms that was recently used in [Diakonikolas-Kane-Nelson, FOCS 2010].