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.

Related paper are

• Kunis, S. and Potts, D.
  Stability Results for Scattered Data Interpolation by Trigonometric Polynomials.
  SIAM J. Sci. Comput., 29(4), 1403-1419,   (full paper ps, pdf)   2007
   
• Böttcher, A. and Potts, D.
  Probability against condition number and sampling of multivariate trigonometric random polynomials.
  Electron. Trans. Numer. Anal., Volume 26, pp. 178-189,   (full paper ps, pdf),   2007
   
• Böttcher, A., Potts, D. and Wenzel, D.
  A probability argument in favor of ignoring small singular values.
  Operators and Matrices, Volume 1, Number 1,   (full paper ps, pdf),   2007
   
• Kircheis, M. and Potts, D.
  Direct inversion of the nonequispaced fast Fourier transform
  Linear Algebra and its Applications 575 106-140,   (full paper pdf),   2019