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 -