NSFFT - nonequispaced sparse fast Fourier transform

We consider the fast evaluation of trigonometric polynomials from so-called hyperbolic crosses. In multivariate approximation one has to deal with the so called `curse of dimensionality', i.e., the number of degrees of freedom for representing an approximation of a function with a prescribed accuracy depends exponentially on the dimensionality of the considered problem. This obstacle can be circumvented to some extend by the interpolation on sparse grids and the related approximation on hyperbolic cross points in the Fourier domain, see, e.g., [58,54,9].

Instead of approximating a Fourier series on the standard tensor product grid $I_{\ensuremath{\boldsymbol{(}}N,\hdots,N)}$ with ${\cal O}(N^d)$ degrees of freedom, it can be approximated with only ${\cal O}(N \log^{d-1} N)$ degrees of freedom from the hyperbolic cross

$$H_N^d := \bigcup_{\ensuremath{\boldsymbol{N}}\in\ensuremath{\math... ... \vert I_{\ensuremath{\boldsymbol{N}}}\vert=N} I_{\ensuremath{\boldsymbol{N}}},$$

where $N=2^{J+2},\;J\in\ensuremath{\mathbb{N}_{0}}$ and we allow $N_t=1$ in the $t$ -th coordinate in the definition of $I_{\ensuremath{\boldsymbol{N}}}$ . The approximation error in a suitable norm (dominated mixed smoothness) can be shown to deteriorate only by a factor of $\log^{d-1} N$ , cf. [54].

Figure 3.1: Hyperbolic cross points for $d=2$ and $J=0,\ldots ,3$ .

The nonequispaced sparse discrete Fourier transform (NSDFT) is the evaluation of

$$f\left(\ensuremath{\boldsymbol{x}}_j\right) = \sum_{\ensuremath{\... ...ox{\scriptsize {i}}} \ensuremath{\boldsymbol{k}} \ensuremath{\boldsymbol{x}}_j}$$

for given Fourier coefficients $\hat f_{\ensuremath{\boldsymbol{k}}} \in \ensuremath{\mathbb{C}}$ and nodes $\ensuremath{\boldsymbol{x}}_j \in \ensuremath{\mathbb{T}}^d$ . The number of used arithmetical operations is ${\cal O}(M N\log^{d-1}N)$ . This is reduced by our fast schemes to ${\cal O}(N\log^2 N+M)$ for $d=2$ and ${\cal O}(N^{3/2} \log N+M)$ for $d=3$ , see [20] for details.