Direct inversion of the nonequispaced fast Fourier transform

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 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 means of a modified adjoint NFFT in O(M log M + N) arithmetic operations. Finally, we show that these approaches can also be explained by means of frame approximation. (C) 2019 Elsevier Inc. All rights reserved.