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.