-- The constructions in the paper "Sparser Johnson-Lindenstrauss
Transforms" with Kane achieve better bounds. I recommend reading
that paper instead. (10/9/2011)
Version 3 changes:
-----------------
-- Added two items to the appendix: (1) alternative proof that the
optimal number of rows for JL is Theta(eps^{-2}*log(1/delta)),
and (2) derandomized JL family with seed length O(log d +
log(1/eps)*log(1/delta) + log(1/delta)*loglog(1/delta)). (12/7/2010)
-- Switched the proof for bounding the operator norm to an arguably
simpler one. (12/7/2010)
-----------------
Version 2 changes:
-----------------
-- Improved introduction and related work section, and fixed various
typos. (7/7/2010)
-- Added a warmup section, Section 4, which gives a short proof of the
Johnson-Lindenstrauss lemma. (7/8/2010)