Fast Nearest Neighbor Preserving Embeddings

Johan Sivertsen

We show an analog to the Fast Johnson-Lindenstrauss Transform for Nearest Neighbor Preserving Embeddings in ${\ell }_2$. These are sparse, randomized embeddings that preserve the (app…