## Abstract

We introduce a new low-distortion embedding of l _{2} ^{d} l _{p} ^{O}(log n (p = 1, 2) called the fast Johnson-Lindenstrauss transform (FJLT). The FJLT is faster than standard random projections and just as easy to implement. It is based upon the preconditioning of a sparse projection matrix with a randomized Fourier transform. Sparse random projections are unsuitable for low-distortion embeddings. We overcome this handicap by exploiting the "Heisenberg principle" of the Fourier transform, i.e., its local-global duality. The FJLT can be used to speed up search algorithms based on low-distortion embeddings in l _{1} and l _{2}. We consider the case of approximate nearest neighbors in l _{2} ^{d}. We provide a faster algorithm using classical projections, which we then speed up further by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube.

Original language | English (US) |
---|---|

Pages (from-to) | 302-322 |

Number of pages | 21 |

Journal | SIAM Journal on Computing |

Volume | 39 |

Issue number | 1 |

DOIs | |

State | Published - 2009 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics

## Keywords

- Approximate nearest neighbors
- Dimension reduction
- Random matrices