The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors

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.