Loading...
Please wait, while we are loading the content...
Similar Documents
Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss Transform (2006)
| Content Provider | CiteSeerX |
|---|---|
| Author | Ailon, Nir Chazelle, Bernard |
| Description | This content is published in/by STOC'06 |
| Abstract | We introduce a new low-distortion embedding of ℓ d 2 into O(log n) ℓp (p = 1, 2), called the Fast-Johnson-Lindenstrauss-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 lowdistortion 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 further speed up by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube. |
| File Format | |
| Publisher Date | 2006-01-01 |
| Access Restriction | Open |
| Subject Keyword | Approximate Nearest Neighbor Fast Johnson-lindenstrauss Transform Fourier Transform Local-global Duality Standard Random Projection Sparse Projection Matrix Classical Projection Heisenberg Principle New Low-distortion Embedding Sparse Random Projection Low-distortion Embeddings Search Algorithm Lowdistortion Embeddings |
| Content Type | Text |
| Resource Type | Conference Proceedings |
