Solver - inverse transforms

In the following, we describe the inversion of the NFFT, i.e., the computation of Fourier coefficients from given samples $(\ensuremath{\boldsymbol{x}}_j,y_j) \in \ensuremath{\mathbb{T}}^d\times \ensuremath{\mathbb{C}}$ , $j=0,\ldots,M-1$ . In matrix vector notation, we aim to solve the linear system of equations

$$\ensuremath{\boldsymbol{A}} \ensuremath{\boldsymbol{\hat f}} \approx \ensuremath{\boldsymbol{y}}$$ (3.2)

for the vector $\ensuremath{\boldsymbol{\hat f}}\in\ensuremath{\mathbb{C}}^{\vert I_{\ensuremath{\boldsymbol{N}}\vert}}$ . Note however that the nonequispaced Fourier matrix $\ensuremath{\boldsymbol{A}}$ can be replaced by any other Fourier matrix from Section 3.

Typically, the number of samples $M$ and the dimension of the space of the polynomials $\vert I_{\ensuremath{\boldsymbol{N}}}\vert$ do not coincide, i.e., the matrix $\ensuremath{\boldsymbol{A}}$ is rectangular. There are no simple inverses to nonequispaced Fourier matrices in general and we search for some pseudoinverse solution $\ensuremath{\boldsymbol{\hat f}}^{\dagger}$ , see e.g. [8, p. 15]. However, we conclude from eigenvalue estimates in [19,4,35] that the matrix $\ensuremath{\boldsymbol{A}}$ has full rank if

$$\max_{0\le t<d} N_t < c_d \delta^{-1}\,, \qquad \delta:=2\max_{\e... ...infty}\left(\ensuremath{\boldsymbol{x}}_j,\ensuremath{\boldsymbol{x}}_l\right),$$

or

$$\min_{0\le t<d} N_t>C_d q^{-1}\,, \qquad q:=\min_{0\le j<l<M} {\r... ...infty}\left(\ensuremath{\boldsymbol{x}}_j,\ensuremath{\boldsymbol{x}}_l\right).$$

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 $\ensuremath{\boldsymbol{A}}$ and $\ensuremath{\boldsymbol{A}}^{{\vdash \hspace*{-1.72mm} \dashv}}$ , respectively.