[theory-seminar] FOCS Practice talk Today 1:00pm - 1:30pm @ Gates 463A

[Paris Syminelakis]

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>