English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the kernel density estimation (KDE) problem one is given a kernel $K(x,y)$ and a dataset $P$ of points in a Euclidean space, and must prepare a datastructure that can quickly answer density queries: given a point $q$, output a$(1+\epsilon)$-approximation to $\mu:=\frac1{|P|}\sum_{p\in P} K(p, q)$. Theclassical approach to KDE is the celebrated fast multipole method of [Greengardand Rokhlin]. The fast multipole method combines a basic space partitioningapproach with a multidimensional Taylor expansion, which yields a $\approx\log^d (n/\epsilon)$ query time (exponential in the dimension $d$). A recentline of work initiated by [Charikar and Siminelakis] achieved polynomialdependence on $d$ via a combination of random sampling and randomized spacepartitioning, with [Backurs et al.] giving an efficient data structure withquery time $\approx \mathrm{poly}{\log(1/\mu)}/\epsilon^2$ for smooth kernels.  Quadratic dependence on $\epsilon$, inherent to the sampling methods, isprohibitively expensive for small $\epsilon$. This issue is addressed byquasi-Monte Carlo methods in numerical analysis. The high level idea inquasi-Monte Carlo methods is to replace random sampling with a discrepancybased approach -- an idea recently applied to coresets for KDE by [Phillips andTai]. The work of Phillips and Tai gives a space efficient data structure withquery complexity $\approx 1/(\epsilon \mu)$. This is polynomially better in$1/\epsilon$, but exponentially worse in $1/\mu$. We achieve the best of both:a data structure with $\approx \mathrm{poly}{\log(1/\mu)}/\epsilon$ query timefor smooth kernel KDE. Our main insight is a new way to combine discrepancytheory with randomized space partitioning inspired by, but significantly moreefficient than, that of the fast multipole methods. We hope that our techniqueswill find further applications to linear algebra for kernel matrices.

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations