Improved Fast Gauss Transform
View/ Open
Date
2003-08-01Author
Yang, Changjiang
Duraiswami, Ramani
Gumerov, Nail A.
Metadata
Show full item recordAbstract
The fast Gauss transform proposed by Greengard and Strain reduces the
computational complexity of the evaluation of the sum of $N$ Gaussians at
$M$ points in $d$ dimensions from $O(MN)$ to $O(M+N)$. However, the constant
factor in $O(M+N)$ grows exponentially with increasing dimensionality $d$,
which makes the algorithm impractical in higher dimensions. In this paper we
present an improved fast Gauss transform where the constant factor is
reduced to asymptotically polynomial order. The reduction is based on a new
multivariate Taylor expansion scheme combined with the space subdivision
using the $k$-center algorithm. The complexity analysis and error bound are
presented which helps to determine parameters automatically given a desired
precision to which the sum must be evaluated. We present numerical results
on the performance of our algorithm and provide numerical verification of
the corresponding error estimate.
(UMIACS-TR-2003-64)