Direct inversion of the nonequispaced fast Fourier transform

DOI10.1016/J.LAA.2019.03.028MaRDI QIDQ6309641arXivWikidataFDO

Authors Melanie Kircheis, Daniel Potts

Publication date 13 November 2018

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.LAA.2019.03.028

Mathematics Subject Classification ID

General harmonic expansions, frames (42C15) Numerical methods in Fourier analysis (65Txx)

arXiv classification

math.NA

Abstract: 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 $mathcalO(NlogN)$ 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 $mathcalO(MlogM+N)$ arithmetic operations. Finally, we show that these approaches can also be explained by means of frame approximation.

This page was built for publication: Direct inversion of the nonequispaced fast Fourier transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6309641)