Fast Cross-Polytope Locality-Sensitive Hashing

Chris of Rachel's lab let me know of the following interesting result:

Hello Igor,

Your readers may be interested in our recent paper that develops a variant of cross-polytope lsh which is both provably optimal in query time and has fast hash computations.  Here is a link to the paper:

http://arxiv.org/abs/1602.06922

Thanks,
Chris Kennedy

 Thanks Chris !





 


Fast Cross-Polytope Locality-Sensitive Hashing by Christopher Kennedy, Rachel Ward

We provide a variant of cross-polytope locality sensitive hashing with respect to angular distance which is both optimal in asymptotic sensitivity and provably fast. Precisely, we substitute the random rotation in the standard cross-polytope scheme for a fast Johnson-Lindenstrauss transform followed by lifted rotation to reduce the number of hash computations from O(d2) to O(dlnd). This builds on a recent result in (Andoni, Indyk, Laarhoven, Razenshteyn, Schmidt, 2015) by providing an LSH scheme for angular distance which is not only optimal in asymptotic sensitivity, but also fast. Finally, we present a discretized version of the scheme which reduces the number of random bits to O(d) while still retaining asymptotic optimality and efficient hash computations.

 
 
 
 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.