Loading...
Please wait, while we are loading the content...
Similar Documents
The fast Johnson-Lindenstrauss transform and approximate nearest neighbors (2009)
| Content Provider | CiteSeerX |
|---|---|
| Author | Ailon, Nir Chazelle, Bernard |
| Abstract | We introduce a new low-distortion embedding of ℓd n) 2 into ℓO(log p (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 ℓ1 and ℓ2. We consider the case of approximate nearest neighbors in ℓd 2. 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. |
| File Format | |
| Journal | SIAM J. Comput |
| Publisher Date | 2009-01-01 |
| Access Restriction | Open |
| Subject Keyword | Local-global Duality Classical Projection Sparse Random Projection Low-distortion Embeddings Sparse Projection Matrix Heisenberg Principle Fast Johnson-lindenstrauss Transform New Low-distortion Embedding Fourier Transform Search Algorithm Standard Random Projection Johnson Lindenstrauss Transform |
| Content Type | Text |
