Inverse NFFT in 1D

This module computes an inverse nonequispaced fast Fourier transform (iNFFT), i.e., approximates the Fourier coefficients ${\hat{f}}_k$ in sums of the form $$f(y_j)=\sum _{k=-N/2}^{N/2-1}{\hat{f}}_k{\mathrm{e}}^{2\pi \mathrm{i}k{y}_j},j=1,...,M,$$ where the nodes $y_j\in [-\frac{1}{2},\frac{1}{2})$ and function values $f(y_j)\in \mathbb{C}$ are given as well as an inverse adjoint nonequispaced fast Fourier transform (adjoint iNFFT), i.e., approximates the function values $f_j$ in sums of the form $${\hat{f}}_k=\sum _{j=1}^M{f}_j{\mathrm{e}}^{-2\pi \mathrm{i}k{y}_j},k=-\frac{N}{2},...,\frac{N}{2}-1,$$ where the nodes $y_j$ and the Fourier coefficients ${\hat{f}}_k\in \mathbb{C}$ are given.

For this purpose new direct methods are incorporated, which differ depending on the relation between the number $M$ of nodes and the number $N$ of unknown Fourier coefficients. In general, the number $M$ of nodes $y_j$ is independent from the number $N$ of Fourier coefficients ${\hat{f}}_k$ and therefore the nonequispaced Fourier matrix $$\mathit{A}\text{coloneqq}{\left({\mathrm{e}}^{2\pi \mathrm{i}k{y}_j}\right)}_{j=1,k=-\frac{N}{2}}^{M,\frac{N}{2}-1}\in {\mathbb{C}}^{M\times N},$$ which we would have to invert, is rectangular in most cases.

Quadratic setting $M=N$: The computation of an iNFFT is reduced to the computation of some needed coefficients and the application of an FFT afterwards. The fast iNFFT algorithm of complexity $\mathcal{O}(N\log N)$ utilizes Lagrange interpolation and the fast summation.

Rectangular setting $M\ne N$: An iNFFT is obtained by performing only one adjoint NFFT with a specific optimized matrix. This optimization is done in a precomputational step according to the given nodes $y_j$. All in all, we have precomputational algorithms of complexity $\mathcal{O}(M^2)$ and $\mathcal{O}(N^2)$ for the overdetermined and underdetermined case, respectively, whereas the algorithms for the inversion require only $\mathcal{O}(N\log N+M)$ arithmetic operations.

Additional approach for the setting $M\ge N$: An iNFFT is obtained by exactly solving the normal equations. This is possible since ${\mathit{A}}^{\ast }\mathit{A}$ is a Toeplitz matrix. Therefore, ${\mathit{A}}^{\ast }\mathit{A}$ can be inverted exactly by means of the Gohberg-Semencul formula.

It must be pointed out that the algorithms only work in the one-dimensional setting.

The Matlab algorithms are implemented by Melanie Kircheis in ./matlab/infft1d. For more details, see

• Melanie Kircheis and Daniel Potts
  Direct inversion of the nonequispaced fast Fourier transform
  Linear Algebra and its Applications 575 (2019) 106-140. doi:10.1016/j.laa.2019.03.028
  arXiv:1811.05335 (pdf)