Fast Gauss transforms

Stefan Kunis

Discretising integrals of the form

e d    

where $ \sigma \in \mathbb{C}$ denotes some shape parameter leads to the so-called discrete Gauss transform, i.e., given complex coefficients $ \alpha_l \in \mathbb{C}$ and source nodes $ \ensuremath{\boldsymbol{y}}_l\in\mathbb{R}^d,\;l=0,\hdots,L-1$ , our goal consists in the fast evaluation of the sum

$\displaystyle g\left(\ensuremath{\boldsymbol{x}}\right) =\sum_{l=0}^{L-1} \alpha_l \,$e$\displaystyle ^{-\sigma\Vert\ensuremath{\boldsymbol{x}}-\ensuremath{\boldsymbol{y}}_l\Vert^2_2}$    

at target nodes $ \ensuremath{\boldsymbol{x}}_j \in \mathbb{R}^d$ , $ j=0,\hdots,M-1$ .

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 $ \mathbb{R}^d$ or by a finite series of spherical harmonics for nodes on the sphere $ \mathbb{S}^2$ . This particular degenerate kernel expansion yields a rank $ n$ approximation of the matrix

$\displaystyle \left(\mbox{\rm {e}}^{-\sigma\Vert\ensuremath{\boldsymbol{x}}_j-\... ...ol{D}} \ensuremath{\boldsymbol{A}}_{\cal Y}^{{\vdash \hspace*{-1.72mm} \dashv}}$    

where $ \ensuremath{\boldsymbol{A}}_{\cal X}\in\mathbb{C}^{M\times n}$ denotes a nonequispaced Fourier matrix to the nodes $ \ensuremath{\boldsymbol{x}}_j$ and $ \ensuremath{\boldsymbol{D}}\in\mathbb{C}^{n\times n}$ a diagonal matrix with expansion coefficients of the Gaussian kernel. Using the Nonequispaced FFT or its spherical analogue, we obtain total computational costs of $ {\cal O}(n \log n + L + M)$ and $ {\cal O}(n\log^2 n +L +M)$ , 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.