TY - GEN

T1 - Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform

AU - Ailon, Nir

AU - Chazelle, Bernard

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - Approximate nearest neighbor searching

KW - Fourier transform

KW - High-dimensional geometry

KW - Johnson-Lindenstrauss dimension reduction

UR - http://www.scopus.com/inward/record.url?scp=33748109164&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748109164&partnerID=8YFLogxK

U2 - 10.1145/1132516.1132597

DO - 10.1145/1132516.1132597

M3 - Conference contribution

AN - SCOPUS:33748109164

SN - 1595931341

SN - 9781595931344

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 557

EP - 563

BT - STOC'06

PB - Association for Computing Machinery

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

Y2 - 21 May 2006 through 23 May 2006

ER -