Abstract:
\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 $kd^{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}