Fast and Stable Multivariate Kernel Density Estimation by Fast Sum Updating
本文提出一种基于快速求和更新的精确方法，将核密度估计从单变量扩展到多变量，支持多种核函数和快速近似带宽，在保持精度的同时大幅提升计算速度。
Kernel density estimation and kernel regression are powerful but computationally expensive techniques: a direct evaluation of kernel density estimates at M evaluation points given N input sample points requires a quadratic O(MN) operations, which is prohibitive for large scale problems. For this reason, approximate methods such as binning with fast Fourier transform or the fast Gauss transform have been proposed to speed up kernel density estimation. Among these fast methods, the fast sum updating approach is an attractive alternative, as it is an exact method and its speed is independent of the input sample and the bandwidth. Unfortunately, this method, based on data sorting, has for the most part been limited to the univariate case. In this article, we revisit the fast sum updating approach and extend it in several ways. Our main contribution is to extend it to the general multivariate case for general input data and rectilinear evaluation grid. Other contributions include its extension to a wider class of kernels, including the triangular, cosine, and Silverman kernels, its combination with parsimonious additive multivariate kernels, and its combination with a fast approximate k-nearest-neighbors bandwidth for multivariate datasets. Our numerical tests confirm the speed, accuracy, and stability of the method.