Diameter-Free Pointwise Gaussian KDE in Near-Additive Query Time
Vasek Rozhon·Adrian Zámečník
Abstract
For a nonempty finite set X in R^d, consider the Gaussian kernel-density estimate K_X(y), the average over x in X of exp(-||x-y||_2^2 / sigma^2). We construct a randomized data structure which, for every fixed query y in R^d, returns an additive-epsilon approximation to K_X(y) with probability greater than 1 - delta. Its query time is O((d + epsilon^-2) log(d+1) log(2/delta)) and its stored representation has O((d + epsilon^-2) log(2/delta)) real coordinates. No bounded-domain or effective-diameter parameter occurs. The feature map is built from independent blocks W = D H G H B, where D is the next power of two at least d, H is the normalized Walsh–Hadamard matrix, G is diagonal Gaussian, and B is diagonal Rademacher. Although the rows within one block are correlated, Gaussian damping and an exact signed Walsh-autocorrelation identity give a norm-uniform bound on the variance for every fixed displacement z. This estimate lifts to an arbitrary KDE average without independence across data points. The guarantee is pointwise in the query; fixed finite query batches follow by a union bound, whereas uniform or adaptive queries require different control.Discussion
Sign in to join the discussion.