arXiv (Cornell University) · 2011 · 56 citations · 9 references
ComputingComputer ScienceMachine LearningScientific ComputingStatistical LearningDensity EstimationDimensionality ReductionKernel Density EstimationKernel MethodsNumerical AnalysisApproximation TheoryBandwidthFast Kernel Density EstimationFinite Difference ApproximationKernel LearningMultivariate Density EstimationMultivariate Kernel Density EstimationRecursion
Kernel density estimation (KDE) is a popular statistical technique for estimating the underlying density distribution with minimal assumptions. Although they can be shown to achieve asymptotic estimation optimality for any input distribution, cross-validating for an optimal parameter requires significant computation dominated by kernel summations. In this paper we present an improvement to the dual-tree algorithm, the first practical kernel summation algorithm for general dimension. Our extension is based on the series-expansion for the Gaussian kernel used by fast Gauss transform. First, we derive two additional analytical machinery for extending the original algorithm to utilize a hierarchical data structure, demonstrating the first truly hierarchical fast Gauss transform. Second, we show how to integrate the series-expansion approximation within the dual-tree approach to compute kernel summations with a user-controllable relative error bound. We evaluate our algorithm on real-world datasets in the context of optimal bandwidth selection in kernel density estimation. Our results demonstrate that our new algorithm is the only one that guarantees a hard relative error bound and offers fast performance across a wide range of bandwidths evaluated in cross validation procedures.
9
A fast algorithm for particle simulations
Leslie Greengard, Vladimir Rokhlin · Journal of Computational Physics · 1987 · 4.9K citations
Leslie Greengard, John Strain · SIAM Journal on Scientific and Statistical Computing · 1991 · 504 citations · Full text
Improved fast gauss transform and efficient kernel density estimation
Yang, Duraiswami, Gumerov et al. · 2003 · 404 citations