Coresets for Kernel Density Estimates and the Implications

Yan Zheng

University of Utah

Abstract

Kernel density estimates are important for a broad variety of applications, for instance in dealing with spatial data and noise. They allow a discrete distribution with support on a point set P in R^d to be represented with a continuous distribution with support over all of R^d. In this talk we will study coresets where a large point set P is replaced with a much smaller "coreset" point set Q, and the associated kernel density estimates have bounded difference. We will highlight key combinatorial properties sufficient for this construction and describe randomized and deterministic algorithms with quality guarantees orders of magnitude more efficient than previous algorithms. Next, we describe how these coreset constructions for kernel density estimations are linked to more traditional combinatorial range spaces, and define and prove new properties related to eps-nets but extended to the