A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations

In the kernel density estimation (KDE) problem one is given a kernel K(x, y) and a dataset P of points in a high dimensional Euclidean space, and must prepare a small space data structure that can quickly answer density queries: given a point q, output a (1 + ɛ)-approximation to . The classical approach to KDE (and the more general problem of matrix vector multiplication for kernel matrices) is the celebrated fast multipole method of Greengard and Rokhlin [1983]. The fast multipole method combines a basic space partitioning approach with a multidimensional Taylor expansion, which yields a ≈ logd(n/ɛ) query time (exponential in the dimension d). A recent line of work initiated by Charikar and Siminelakis [2017] achieved polynomial dependence on d via a combination of random sampling and randomized space partitioning, with Backurs et al. [2018] giving an efficient data structure with query time ≈ polylog(1/µ)/ɛ2 for smooth kernels.