-- 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)