Search Mailing List Archives
[theory-seminar] FOCS Practice talk Today 1:00pm - 1:30pm @ Gates 463A
Paris Syminelakis
psimin at stanford.edu
Fri Oct 13 12:07:01 PDT 2017
Hi all,
I am going to be giving a FOCS practice talk today between 1:00pm - 1:30pm at Gates 463A and would be great to get some feedback. Everyone is welcome! Abstract follows.
--Paris
Title: Hashing-Based-Estimators for Kernel Density in High Dimensions.
Abstract: Given a set of points $P\subset \R^{d}$ and a kernel $k$, the Kernel Density Estimate at a point $x\in\R^{d}$ is defined as $\mathrm{KDE}_{P}(x)=\frac{1}{|P|}\sum_{y\in P} k(x,y)$. We study the problem of designing a data structure that given a data set $P$ and a kernel function, returns \emph{approximations to the kernel density} of a query point in \emph{sublinear time}. We introduce a class of unbiased estimators for kernel density implemented through locality-sensitive hashing, and give general theorems bounding the variance of such estimators.
These estimators give rise to efficient data structures for estimating the kernel density in high dimensions for a variety of commonly used kernels. Our work is the first to provide data-structures with theoretical guarantees that improve upon simple random sampling in high dimensions.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20171013/47f7694a/attachment.html>
More information about the theory-seminar
mailing list