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 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nir Ailon | 1 | 1114 | 70.74 |
Bernard Chazelle | 2 | 6848 | 814.04 |