# Fast Computation of Sums of Gaussians in High Dimensions

 dc.contributor.author Raykar, Vikas Chandrakant dc.contributor.author Yang, Changjaing dc.contributor.author Duraiswami, Ramani dc.contributor.author Gumerov, Nail dc.date.accessioned 2005-11-15T19:27:37Z dc.date.available 2005-11-15T19:27:37Z dc.date.issued 2005-11-15T19:27:37Z dc.identifier.uri http://hdl.handle.net/1903/3020 dc.description.abstract Evaluating sums of multivariate Gaussian kernels is a key computational task in many problems in computational statistics and en machine learning. The computational cost of the direct evaluation of such sums scales as the product of the number of kernel functions and the evaluation points. The fast Gauss transform proposed by Greengard and Strain (1991) is a $\epsilon$-exact approximation algorithm that reduces the computational complexity of the evaluation of the sum of $N$ Gaussians at $M$ points in $d$ dimensions from $\mathcal{O}(MN)$ to $\mathcal{O}(M+N)$. However, the constant factor in $\mathcal{O}(M+N)$ grows exponentially with increasing dimensionality $d$, which makes the algorithm impractical for dimensions greater than three. In this paper we present a new algorithm where the constant factor is reduced to asymptotically polynomial order. The reduction is based on a new multivariate Taylor's series expansion (which can act both as a local as well as a far field expansion) scheme combined with the efficient space subdivision using the $k$-center algorithm. The proposed method differs from the original fast Gauss transform in terms of a different factorization, efficient space subdivision, and the use of point-wise error bounds. Algorithm details, error bounds, procedure to choose the parameters and numerical experiments are presented. As an example we shows how the proposed method can be used for very fast $\epsilon$-exact multivariate kernel density estimation. dc.format.extent 2413407 bytes dc.format.mimetype application/pdf dc.language.iso en_US en dc.relation.ispartofseries UM Computer Science Department en dc.relation.ispartofseries CS-TR-4767 en dc.relation.ispartofseries UMIACS-TR-2005-69 en dc.title Fast Computation of Sums of Gaussians in High Dimensions en dc.type Technical Report en
﻿