In the following, we describe the inversion of the NFFT, i.e., the computation of Fourier coefficients from given samples , . In matrix vector notation, we aim to solve the linear system of equations
Typically, the number of samples and the dimension of the space of the polynomials do not coincide, i.e., the matrix is rectangular. There are no simple inverses to nonequispaced Fourier matrices in general and we search for some pseudoinverse solution , see e.g. [8, p. 15]. However, we conclude from eigenvalue estimates in [19,4,35] that the matrix has full rank if
In what follows, we consider a weighted least squares solution for the over-determined case and an optimal interpolation for the consistent underdetermined case. Both cases are solved by means of iterative algorithms where Algorithm 1 and 2 are used for the matrix vector multiplication with and , respectively.