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 $\mathcal{H}$ such that $k(x,y)={\mathrm{Pr}}_{h\sim \mathcal{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 (-\Vert x-y{\Vert }_p)$ is LSHable in bounded regions for all $1<p\le 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 ${\ell }_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.