approximate nearest neighbors and the fast johnson-lindenstrauss transform
We introduce a new low-distortion embedding of l 2 d into l p O(log n) (p=1,2), called the Fast-Johnson-Linden-strauss-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 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 further speed up by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube.
approximation nearest neighbor transformation embedding standardization randomization project fourier transform search algorithm algorithm case hypercube log approximate nearest neighbor searching high-dimensional geometry locality global