Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform

Nir Ailon, Bernard Chazelle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

198 Scopus citations

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 languageEnglish (US)
Title of host publicationSTOC'06
Subtitle of host publicationProceedings of the 38th Annual ACM Symposium on Theory of Computing
Pages557-563
Number of pages7
StatePublished - Sep 5 2006
Event38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States
Duration: May 21 2006May 23 2006

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume2006
ISSN (Print)0737-8017

Other

Other38th Annual ACM Symposium on Theory of Computing, STOC'06
CountryUnited States
CitySeattle, WA
Period5/21/065/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

    Ailon, N., & Chazelle, B. (2006). Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. In 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).