Nonequispaced fast Fourier transform
iNFFT in 1D

# 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},\quad j = 1,...,M,$ where the nodes $$y_j\in[-\frac12,\frac12)$$ 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}, \quad k = -\frac N2,...,\frac N2-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 $\boldsymbol A \coloneqq \left(\mathrm e^{2\pi\mathrm i k y_j}\right)_{j=1,\, k=-\frac N2}^{M,\; \frac N2 -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 \neq 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 $$\boldsymbol A^* \boldsymbol A$$ is a Toeplitz matrix. Therefore, $$\boldsymbol A^*\boldsymbol 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