Direct inversion of the nonequispaced fast Fourier transform
This work provides efficient direct inversion algorithms for the NFFT, benefiting applications like MRI and PDE solving that require fast Fourier inversion on nonuniform grids.
The paper introduces direct methods for inverting the nonequispaced fast Fourier transform (NFFT), achieving O(N log N) complexity for the square case and O(M log M + N) for under/overdetermined cases, enabling accurate inversion via modified adjoint NFFT.
Various applications such as MRI, solution of PDEs, etc. need to perform an inverse nonequispaced fast Fourier transform (NFFT), i. e., compute $M$ Fourier coefficients from given $N$ nonequispaced data. In the present paper we consider direct methods for the inversion of the NFFT. We introduce algorithms for the setting $M=N$ as well as for the underdetermined and overdetermined cases. For the setting $M=N$ a direct method of complexity $\mathcal O(N\log N)$ is presented which utilizes Lagrange interpolation and the fast summation. For the remaining cases, we use the matrix representation of the NFFT to deduce our algorithms. Thereby, we are able to compute an inverse NFFT up to a certain accuracy by dint of a modified adjoint NFFT in $\mathcal O(M\log M+N)$ arithmetic operations. Finally, we show that these approaches can also be explained by means of frame approximation.