Direct inversion methods for the multivariate nonequispaced fast Fourier transform

1 : Chemnitz University of Technology

Various applications such as MRI, solution of PDEs, etc. need to perform an inverse nonequispaced fast Fourier transform (iNFFT), i. e., compute Fourier coefficients from given nonequispaced data. In contrast to iterative solvers we introduce a direct method for this inversion in the overdetermined setting. For this purpose, we use the matrix representation of the NFFT. Modifying one of the matrix factors leads to an optimization problem, which can be solved in a precomputational step using normal equations. Therefore, we are able to compute an inverse NFFT up to a certain accuracy by means of a modified adjoint NFFT and therefore preserve its arithmetic complexity.