Stefan Kunis
Fast Gauss transforms
Discretising integrals of the form
where
denotes some shape parameter leads to the socalled
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.