Faster Gaussian summation: theory and experiment
Dongryeol Lee, Alexander Gray · 2006
We provide faster algorithms for the prob-lem of Gaussian summation, which occurs in many machine learning methods. We de-velop two new extensions- an O(Dp) Tay-lor expansion for the Gaussian kernel with rigorous error bounds and a new error con-trol scheme integrating any arbitrary approx-imation method- within the best discrete-algorithmic framework using adaptive hier-archical data structures. We rigorously eval-uate these techniques empirically in the con-text of optimal bandwidth selection in kernel density estimation, revealing the strengths and weaknesses of current state-of-the-art