Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation

A kernel k(x,y) is LSHable if there exists a locality sensitive hashing scheme H such that k(x,y)=Prh~ H[h(x)=h(y)] for all x,y. This notion plays a key role in efficient kernel methods in high dimensions. In this work, we show that the p-exponential kernel k(x,y)=exp(-lVert x-y rVertp) is LSHable in bounded regions for all 1<p≤2. Previously, this was known only for p=1. Our new "mosaic LSH" scheme is based on a Poisson hyperplane process with hyperplanes sampled as ℓ1-biased p-stable vectors, for which we develop efficient sampling procedures. As applications, our results yield new and efficient density estimation methods based on LSHability for those p-exponential kernels.