Further NFFT approaches

Several papers have described fast approximations for the NFFT. Common names for NFFT are non-uniform fast Fourier transform [24], generalised fast Fourier transform [15], unequally-spaced fast Fourier transform [7], fast approximate Fourier transforms for irregularly spaced data [57], non-equispaced fast Fourier transform [26] or gridding [53,30,42].

In various papers, different window functions were considered, e.g. Gaussian pulse tapered with a Hanning window in [14], Gaussian kernels combined with Sinc kernels in [42], and special optimised windows in [30,14].

A simple but nevertheless fast scheme for the computation of (2.3) in the univariate case $d=1$ is presented in [1]. This approach uses for each node $x_j \in [-\frac{1}{2},\frac{1}{2})$ a $m$ -th order Taylor expansion of the trigonometric polynomial in (2.1) about the nearest neighbouring point on the oversampled equispaced lattice $\{n^{-1} k - \frac{1}{2}\}_{k=0,\hdots,n-1}$ where again $n=\sigma N,\, \sigma\gg 1$ . Besides its simple structure and only ${\cal O}(N\log N+M)$ arithmetic operations, this algorithm utilises $m$ FFTs of size $n$ compared to only one in the NFFT approach, uses a medium amount of extra memory, and is not suited for highly accurate computations, see [36]. Furthermore, its extension to higher dimensions has not been considered so far.

Another approach for the univariate case $d=1$ is considered in [16] and based on a Lagrange interpolation technique. After taking a $N$ -point FFT of the vector $\ensuremath{\boldsymbol{\hat f}}$ in (2.3) one uses an exact polynomial interpolation scheme to obtain the values of the trigonometric polynomial $f$ at the nonequispaced nodes $x_j$ . Here, the time consuming part is the exact polynomial interpolation scheme which can however be realised fast in an approximate way by means of the fast multipole method. This approach is appealing since it allows also for the inverse transform. Nevertheless, numerical experiments in [16] showed that this approach is far more time consuming than Algorithm 1 and the inversion can only be computed in a stable way for almost equispaced nodes [16].

Furthermore, special approaches based on scaling vectors [40], based on minimising the Frobenius norm of certain error matrices [41] or based on min-max interpolation [24] are proposed. While these approaches gain some accuracy for the Gaussian or B-Spline windows, no reasonable improvement is obtained for the Kaiser-Bessel window function.

For comparison of different approaches, we refer to [57,41,24,36].