Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform

Nir Ailon, Bernard Chazelle

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

205 Scopus citations

Abstract

We introduce a new low-distortion embedding of l2d into lpO(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 l1 and l 2. We consider the case of approximate nearest neighbors in l 2d. 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
PublisherAssociation for Computing Machinery
Pages557-563
Number of pages7
ISBN (Print)1595931341, 9781595931344
DOIs
StatePublished - 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