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