This is an announcement for the paper "On randomness reduction in the Johnson-Lindenstrauss lemma" by Pawel Wolff.
Abstract: A refinement of so-called fast Johnson-Lindenstrauss transform, due to Ailon and Chazelle (2006), and Matou\v{s}ek (2008), is proposed. While it preserves the time efficiency and simplicity of implementation of the original construction, it reduces randomness used to generate the random transformation. In the analysis of the construction two auxiliary results are established which might be of independent interest: a Bernstein-type inequality for a sum of a random sample from a family of independent random variables and a normal approximation result for such a sum.
Archive classification: math.PR math.FA
Mathematics Subject Classification: 60E15, 46B85
Submitted from: pawel.wolff@case.edu
The paper may be downloaded from the archive by web browser from URL
http://front.math.ucdavis.edu/1202.5500
or