NDFT - nonequispaced discrete Fourier transform

The first problem to be addressed can be regarded as a matrix vector multiplication. For a finite number of given Fourier coefficients $\hat f_{\ensuremath{\boldsymbol{k}}} \in \ensuremath{\mathbb{C}}$ , $\ensuremath{\boldsymbol{k}}\in I_{\ensuremath{\boldsymbol{N}}}$ , we consider the evaluation of the trigonometric polynomial

$$f\left(\ensuremath{\boldsymbol{x}}\right) := \sum_{\ensuremath{\b... ...\mbox{\scriptsize {i}}} \ensuremath{\boldsymbol{k}}\ensuremath{\boldsymbol{x}}}$$ (2.1)

at given nonequispaced nodes $\ensuremath{\boldsymbol{x}}_j \in \ensuremath{\mathbb{T}}^d$ . Thus, our concern is the evaluation of

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

$j=0,\hdots,M-1$ . In matrix vector notation this reads

$$\ensuremath{\boldsymbol{f}}=\ensuremath{\boldsymbol{A}} \ensuremath{\boldsymbol{\hat f}}$$ (2.3)

where

$$\ensuremath{\boldsymbol{f}}:=\left(f_j\right)_{j=0,\hdots,M-1},\q... ...l{k}}}\right)_{\ensuremath{\boldsymbol{k}}\in I_{\ensuremath{\boldsymbol{N}}}}.$$

The straightforward algorithm for computing this matrix vector product, which is called NDFT, takes ${\cal O}(M \vert I_{\ensuremath{\boldsymbol{N}}}\vert)$ arithmetical operations.

A closely related matrix vector product is the adjoint NDFT

$$\ensuremath{\boldsymbol{\hat h}}=\ensuremath{\boldsymbol{A}}^{{\v... ...ox{\scriptsize {i}}} \ensuremath{\boldsymbol{k}}\ensuremath{\boldsymbol{x}}_j},$$

where $\ensuremath{\boldsymbol{A}}^{{\vdash \hspace*{-1.72mm} \dashv}}=\overline {\ensuremath{\boldsymbol{A}}}^{\top}$ denotes the conjugate transpose of the nonequispaced Fourier matrix $\ensuremath{\boldsymbol{A}}$ .