arXiv preprint ·
Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
A kernel $k(x,y)$ is LSHable if there exists a locality sensitive hashing scheme $H$ such that $k(x,y)=\Pr_{h\sim 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 \rVert_p)$ is LSHable in bounded regions for all $1<p\leq2$. 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry
Min-Max Uniform Circle Formation by Asynchronous Mobile Robots
Deterministic Distance Selection in $O(n^{4/3})$ Time
Peeling Half the Onion: Embedding $k$-Outerplanar Graphs into $\ell_1$ and Trees with a Polynomial Distortion (in $k$)
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.