Inversion

The inverse NFFT (iNFFT) solves \[ \sum_{\boldsymbol k\in \boldsymbol{I_{N}}} \hat f_{\boldsymbol k}\, \mathrm e^{-2\pi\mathrm i \boldsymbol k \boldsymbol x_j} \approx f_j \qquad (j=0,\dots,M-1) \] for \(\hat f\) on arbitrary sampling sets \( {\mathcal X}:=\left\{\boldsymbol{x}_j:\,j=0,\dots,M-1\right\}\subset \mathbb{T}^d\).

The NFFT package provides fast iNFFT algorithms in one dimension in the infft1d module for Matlab. Furthermore, the solver module computes an iNFFT based on least squares or interpolation.

References

• Kunis, S. and Potts, D.
  Stability results for scattered data interpolation by trigonometric polynomials.
  SIAM J. Sci. Comput. 29(4), 1403–1419, 2007. doi pdf ps
• Böttcher, A. and Potts, D.
  Probability against condition number and sampling of multivariate trigonometric random polynomials.
  Electron. Trans. Numer. Anal. 26, 178–189, 2007. pdf ps
• Böttcher, A., Potts, D., and Wenzel, D.
  A probability argument in favor of ignoring small singular values.
  Operators and Matrices 1(1), 2007. doi pdf ps
• Kircheis, M. and Potts, D.
  Direct inversion of the nonequispaced fast Fourier transform.
  Linear Algebra Appl. 575, 106–140, 2019. doi pdf