Faster Gaussian Summation: Theory and Experiment
  We provide faster algorithms for the problem of Gaussian summation, which
occurs in many machine learning methods. We develop two new extensions - an
O(Dp) Taylor expansion for the Gaussian kernel with rigorous error bounds and a
new error control scheme integrating any arbitrary approximation method -
within the best discretealgorithmic framework using adaptive hierarchical data
structures. We rigorously evaluate these techniques empirically in the context
of optimal bandwidth selection in kernel density estimation, revealing the
strengths and weaknesses of current state-of-the-art approaches for the first
time. Our results demonstrate that the new error control scheme yields improved
performance, whereas the series expansion approach is only effective in low
dimensions (five or less).
