Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes
The Fast Johnson-Lindenstrauss Transform (FJLT) was recently discovered by Ailon and Chazelle as a novel technique for performing fast dimension reduction with small distortion from l(2)(d) to l(2)(k) in time O(max{d log d, k(3)}). For k in [Omega(log d), O(d(1/2))], this beats time O(dk) achieved by naive multiplication by random dense matrices, an approach followed by several authors as a variant of the seminal result by Johnson and Lindenstrauss (JL) from the mid 1980s. In this work we show how to significantly improve the running time to O(d log k) for k = O(d(1/2-delta)), for any arbitrary small fixed d. This beats the better of FJLT and JL. Our analysis uses a powerful measure concentration bound due to Talagrand applied to Rademacher series in Banach spaces (sums of vectors in Banach spaces with random signs). The set of vectors used is a real embedding of dual BCH code vectors over GF(2). We also discuss the number of random bits used and reduction to l(1) space. The connection between geometry and discrete coding theory discussed here is interesting in its own right and may be useful in other algorithmic applications as well.
fast dimension reduction measure concentration probability in banach spaces error correcting codes