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