NFFT - nonequispaced fast Fourier transform

For the sake of simplicity, we explain the ideas behind the NFFT for the one-dimensional case $d=1$ and the algorithm NFFT. The generalisation of the FFT is an approximative algorithm and has computational complexity ${\cal O}\left(N \log N + \log \left(1/\varepsilon\right) M\right)$ , where $\varepsilon$ denotes the desired accuracy. The main idea is to use standard FFTs and a window function $\varphi$ which is well localised in the time/spatial domain $\mathbb{R}$ and in the frequency domain $\mathbb{R}$ . Several window functions were proposed in [15,7,55,25,24].

The considered problem is the fast evaluation of

$$f\left(x\right) = \sum_{k\in I_N} \hat{f}_k {\rm e}^{-2\pi{\mbox{\scriptsize {i}}} k x}$$ (2.4)

at arbitrary nodes $x_j \in \ensuremath{\mathbb{T}},\;j=0,\hdots,M-1$ .