### Abstract

We introduce a new low-distortion embedding of l _{2} ^{d} into l _{p} ^{O(log n)} (p = 1, 2), called the Fast-Johnson-Lindenstrauss-Transform. 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, ie, 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 further speed up by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube.

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

Title of host publication | STOC'06 |

Subtitle of host publication | Proceedings of the 38th Annual ACM Symposium on Theory of Computing |

Pages | 557-563 |

Number of pages | 7 |

State | Published - Sep 5 2006 |

Event | 38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States Duration: May 21 2006 → May 23 2006 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | 2006 |

ISSN (Print) | 0737-8017 |

### Other

Other | 38th Annual ACM Symposium on Theory of Computing, STOC'06 |
---|---|

Country | United States |

City | Seattle, WA |

Period | 5/21/06 → 5/23/06 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Approximate nearest neighbor searching
- Fourier transform
- High-dimensional geometry
- Johnson-Lindenstrauss dimension reduction

## Fingerprint Dive into the research topics of 'Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform'. Together they form a unique fingerprint.

## Cite this

*STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing*(pp. 557-563). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 2006).