The fast johnson-lindenstrauss transform and approximate nearest neighbors

Nir Ailon, Bernard Chazelle

Research output: Contribution to journalArticle

181 Scopus citations

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 languageEnglish (US)
Pages (from-to)302-322
Number of pages21
JournalSIAM Journal on Computing
Volume39
Issue number1
DOIs
StatePublished - Jul 15 2009

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Approximate nearest neighbors
  • Dimension reduction
  • Random matrices

Fingerprint Dive into the research topics of 'The fast johnson-lindenstrauss transform and approximate nearest neighbors'. Together they form a unique fingerprint.

  • Cite this