Aliasing error of the exp$(\beta \sqrt{1-z^2})$ kernel in the nonuniform fast Fourier transform

Abstract

The most popular algorithm for the nonuniform fast Fourier transform (NUFFT) uses the dilation of a kernel $\varphi$ to spread (or interpolate) between given nonuniform points and a uniform upsampled grid, combined with an FFT and diagonal scaling (deconvolution) in frequency space. The high performance of the recent FINUFFT library is in part due to its use of a new "exponential of semicircle" kernel $\varphi (z)=e^{\beta \sqrt{1-z^2}}$, for $z\in [-1,1]$, zero otherwise, whose Fourier transform $\hat{\varphi }$ is unknown analytically. We place this kernel on a rigorous footing by proving an aliasing error estimate which bounds the error of the one-dimensional NUFFT of types 1 and 2 in exact arithmetic. Asymptotically in the kernel width measured in upsampled grid points, the error is shown to decrease with an exponential rate arbitrarily close to that of the popular Kaiser--Bessel kernel. This requires controlling a conditionally-convergent sum over the tails of $\hat{\varphi }$, using steepest descent, other classical estimates on contour integrals, and a phased sinc sum. We also draw new connections between the above kernel, Kaiser--Bessel, and prolate spheroidal wavefunctions of order zero, which all appear to share an optimal exponential convergence rate.

18 pages, 2 figures; in press at Appl. Comput. Harmon. Anal.; updated Rmk 4 in light of revised Potts-Tasche preprint

Cited by in corpus (5)

• Asteroids for $\mu$Hz gravitational-wave detection
• Continuous window functions for NFFT
• Electron ground state $g$ factor in embedded InGaAs quantum dots: An atomistic study
• Upper-body free-breathing Magnetic Resonance Fingerprinting applied to the quantification of water T1 and fat fraction
• Shaken, not stirred: Test particles in binary black hole mergers