# Fast Gauss transforms

## Stefan Kunis

Discretising integrals of the form

e d |

where denotes some shape parameter leads to the so-called discrete Gauss transform, i.e., given complex coefficients and source nodes , our goal consists in the fast evaluation of the sum

e |

at target nodes , .

Applying the general fast summation scheme, developed by Potts and Steidl, we approximate the Gaussian kernel by a dilated trigonometric polynomial for nodes in a bounded domain of or by a finite series of spherical harmonics for nodes on the sphere . This particular degenerate kernel expansion yields a rank approximation of the matrix

where denotes a nonequispaced Fourier matrix to the nodes and a diagonal matrix with expansion coefficients of the Gaussian kernel. Using the Nonequispaced FFT or its spherical analogue, we obtain total computational costs of and , respectively. We establish explicit error bounds and provide numerical examples covering approximation quality, speed measurements, and a comparison of our particular matrix approximation with a truncated singular value decomposition.