Computer Science/Discrete Mathematics Seminar I

The Fast Johnson-Lindenstrauss Transorm 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 talk I will show how to perform dimension reduction onto $kd^{1/3}$ and for $k=d^{o(1)}$. This is achieved using analysis of Rademacher series in Banach spaces (sums of vectors in Banach spaces with random signs) and a powerful measure concentration bound due to Talagrand. The set of vectors used is related to dual BCH codes. I will also discuss reduction onto $\ell_1$ space. Finally, I will show that certain reasonable assumptions on explicit construction of matrices based on codes with certain properties would extend our result to all $k