Notation, the NDFT, and the NFFT

This section summarises the mathematical theory and ideas behind the NFFT. Let the torus

$$\ensuremath{\mathbb{T}}^d := \left\{ \ensuremath{\boldsymbol{x}}=... ...h{\mathbb{R}}^d: - \frac{1}{2} \le x_t < \frac{1}{2},\; t=0,\hdots,d-1 \right\}$$

of dimension $d\in\ensuremath{\mathbb{N}}$ be given. It will serve as domain from which the nonequispaced nodes $\ensuremath{\boldsymbol{x}}$ are taken. Thus, the sampling set is given by ${\cal X}:=\{\ensuremath{\boldsymbol{x}}_j \in \ensuremath{\mathbb{T}}^d:\,j=0,\hdots,M-1\}$ .

Possible frequencies $\ensuremath{\boldsymbol{k}}\in\ensuremath{\mathbb{Z}}^d$ are collected in the multi-index set

$$I_{\ensuremath{\boldsymbol{N}}} := \left\{ \ensuremath{\boldsymbo... ...athbb{Z}}^d: - \frac{N_t}{2} \le k_t < \frac{N_t}{2} ,\;t=0,\hdots,d-1\right\},$$

where $\ensuremath{\boldsymbol{N}}=\left(N_t\right)_{t=0,\hdots,d-1}$ is the EVEN multibandlimit, i.e., $N_t\in 2\ensuremath{\mathbb{N}}$ . To keep notation simple, the multi-index $\ensuremath{\boldsymbol{k}}$ addresses elements of vectors and matrices as well, i.e., the plain index $\tilde k:=\sum_{t=0}^{d-1} (k_t+\frac{N_t}{2}) \prod_{t'=t+1}^{d-1} N_{t'}$ is not used here. The inner product between the frequency index $\ensuremath{\boldsymbol{k}}$ and the time/spatial node $\ensuremath{\boldsymbol{x}}$ is defined in the usual way by $\ensuremath{\boldsymbol{k}} \ensuremath{\boldsymbol{x}}:=k_0 x_0 + k_1 x_1 +\hdots+ k_{d-1} x_{d-1}$ . Furthermore, two vectors may be combined by the component-wise product $\ensuremath{\boldsymbol{\sigma}} \odot \ensuremath{\boldsymbol{N}}:=\left(\sigma_0 N_0, \sigma_1 N_1, \hdots, \sigma_{d-1} N_{d-1}, \right)^{\top}$ with its inverse $\ensuremath{\boldsymbol{N}}^{-1}:=\left(\frac{1}{N_0}, \frac{1}{N_1}, \hdots, \frac{1}{N_{d-1}} \right)^{\top}$ .

The space of all $d$ -variate, one-periodic functions $f: \ensuremath{\mathbb{T}}^d \rightarrow \ensuremath{\mathbb{C}}$ is restricted to the space of $d$ -variate trigonometric polynomials

$$T_{\ensuremath{\boldsymbol{N}}}:={\rm span}\left({\rm e}^{-2\pi{\... ...dot}}}:\,\ensuremath{\boldsymbol{k}} \in I_{\ensuremath{\boldsymbol{N}}}\right)$$

with degree $N_t\; (t=0,\hdots,d-1)$ in the $t$ -th dimension. The dimension $\dim T_{N}$ of the space of $d$ -variate trigonometric polynomials $T_{N}$ is given by $\dim T_{N} = \vert I_{\ensuremath{\boldsymbol{N}}}\vert = \prod\limits_{t=0}^{d-1} N_t$ .