Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-070 | 11th June 2007 00:00

Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes


Authors: Nir Ailon, Edo Liberty
Publication: 1st August 2007 08:16
Downloads: 3422


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.

ISSN 1433-8092 | Imprint