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)