Available window functions and evaluation techniques

Again, only the case $d=1$ is presented. To keep the aliasing error and the truncation error small, several functions $\varphi$ with good localisation in time and frequency domain were proposed, e.g. the (dilated) Gaussian [15,55,14]

$$\varphi\left(x\right) = \left(\pi b\right)^{-1/2} \, {\rm e}^{-\frac{\left(nx\right)^2}{b}} \qquad \left(b := \frac{2\sigma}{2 \sigma -1} \frac{m}{\pi} \right),$$ (2.9)

$$\hat \varphi \left(k\right) = \frac{1}{n} \, {\rm e}^{-b\left(\frac{\pi k}{n}\right)^2} ,$$

(dilated) cardinal central $B$ -splines [7,55]

$$\varphi\left(x\right) = M_{2m}\left(n x\right),$$ (2.10)

$$\hat \varphi \left(k\right) = \frac{1}{n} {\rm sinc}^{2m} \left( k \pi/n\right),$$

where $M_{2m}$ denotes the centred cardinal $B$ -Spline of order $2m$ ,
(dilated) Sinc functions [45]

$$\varphi\left(x\right) = \frac{N\left(2\sigma-1\right)}{2m} {\rm sinc}^{2m} \left(\frac{\left(\pi N x \left(2\sigma-1\right)\right)}{2m} \right),$$ (2.11)

$$\hat \varphi \left(k\right) = M_{2m}\left(\frac{2mk}{\left(2\sigma-1\right)N}\right)$$

and (dilated) Kaiser-Bessel functions [30,25]

$$\varphi\left(x\right) = \frac{1}{\pi} \left\{ \displaystyle \begin{array}{ll} \displaysty... ...2 x^2 - m^2}\right)}{\sqrt{n^2 x^2-m^2}} & \mbox{otherwise}, \end{array}\right.$$ (2.12)

$$\hat \varphi \left(k\right) = \frac{1}{n} \left\{ \displaystyle \begin{array}{cl} \, I_0 \left(... ...s, n \left(1-\frac{1}{2\sigma}\right),\\ 0&{\rm otherwise}, \end{array}\right.$$

where $I_0$ denotes the modified zero-order Bessel function. For these functions $\varphi$ it has been proven that

$$\vert f\left(\ensuremath{\boldsymbol{x}}_j\right) - s\left(\ensur... ...\vert \le C\left(\sigma,m\right) \Vert\ensuremath{\boldsymbol{\hat f}}\Vert _1$$

where

$$% latex2html id marker 8860C\left(\sigma,m\right) := \left... ...} & {\rm for} \; \left(\ref{kaiser}\right). \end{array}\right.$$

Thus, for fixed $\sigma >1$ , the approximation error introduced by the NFFT decays exponentially with the number $m$ of summands in (2.8). Using the tensor product approach the above error estimates can be generalised for the multivariate setting [18]. On the other hand, the complexity of the NFFT increases with $m$ .

In the following, we suggest different methods for the compressed storage and application of the matrix $\ensuremath{\boldsymbol{B}}$ which are all available within our NFFT library by choosing particular flags in a simple way during the initialisation phase. These methods do not yield a different asymptotic performance but rather yield a lower constant in the amount of computation.