Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes

COMPUTER SCIENCE/DISCRETE MATH I
Topic:	Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes
Speaker:	Nir Ailon
Affiliation:	Princeton University
Date:	Tuesday, June 5
Time/Room:	10:30am - 12:30pm/S-101

---

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 $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)}$. 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<d^{1-\delta}$.

Joint work with Edo Liberty.