Title
The Fast Johnson-Lindenstrauss Transform and Approximate Nearest Neighbors
Abstract
We introduce a new low-distortion embedding of $\ell_2^d$ into $\ell_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 $\ell_1$ and $\ell_2$. We consider the case of approximate nearest neighbors in $\ell_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.
Year
DOI
Venue
2009
10.1137/060673096
SIAM J. Comput.
Keywords
Field
DocType
new low-distortion,standard random projection,classical projection,randomized fourier,low-distortion embeddings,approximate nearest neighbor,sparse projection matrix,fast johnson-lindenstrauss transform,approximate nearest neighbors,sparse random projection,faster algorithm,heisenberg principle,random matrices,dimension reduction
Discrete mathematics,Combinatorics,Search algorithm,Embedding,Projection (linear algebra),Fourier transform,Duality (optimization),Mathematics,Sparse matrix,Hypercube,Johnson–Lindenstrauss lemma
Journal
Volume
Issue
ISSN
39
1
0097-5397
Citations 
PageRank 
References 
118
5.91
22
Authors
2
Search Limit
100118
Name
Order
Citations
PageRank
Nir Ailon1111470.74
Bernard Chazelle26848814.04