\begin{abstract}
The Fast Johnson-Lindenstrauss Transform was recently discovered by
Ailon and Chazelle as a technique for performing fast dimension
reduction from $\ell_2^d$ to $\ell_2^k$ in time $O(\max\{d\log d,
k^3\})$, where $k$ is the target lower dimension. This beats the
naive $O(dk)$ achieved by multiplying by random dense matrices, as
noticed by several authors following the seminal result by Johnson
and Lindenstrauss from the mid 80's. In this work we show how to
perform a dimension reduction onto $k<d^{1/2-\delta}$ dimensions in
time $O(d\log k)$ for arbitrary small $\delta$. This beats Ailon et
al's algorithm for $k>d^{1/3}$ and for $k=d^{o(1)}$. In order to
achieve this, we analyze Rademacher series in Banach spaces (sums of
vectors in Banach spaces with random signs) using a powerful measure
concentration bound due to Talagrand. The set of vectors used is a
real embedding of dual BCH code vectors over $GF(2)$. We also
discuss reductions onto $\ell_1$ space.
\end{abstract}