ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-070 | 11th June 2007 00:00

Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes

RSS-Feed




TR07-070
Authors: Nir Ailon, Edo Liberty
Publication: 1st August 2007 08:16
Downloads: 794
Keywords: 


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 $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}



ISSN 1433-8092 | Imprint