Improved Fast Gauss Transform
Improved Fast Gauss Transform
No Thumbnail Available
Files
Publication or External Link
Date
2003-08-01
Authors
Yang, Changjiang
Duraiswami, Ramani
Gumerov, Nail A.
Advisor
Citation
DRUM DOI
Abstract
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)