NUFFT

NUFFT, or non-uniform fast Fourier transform, is a family of algorithms for efficiently computing the Fourier transform when data are sampled at non-uniform positions or when the desired frequency samples are non-uniform. Unlike the standard FFT, which assumes uniform sampling in either space or frequency, NUFFT aims to provide accurate results with nearly the same computational efficiency as FFT-based methods.

The core idea is to embed the non-uniform transform into a uniform grid via interpolation or convolution with a window function, then use a fast FFT to perform the bulk of the computation. After the FFT, a correction step accounts for the interpolation kernel to deliver the final non-uniform transform values. This approach reduces the complexity relative to a direct non-uniform sum and enables practical reconstruction in many applications.

There are several variants commonly referred to as Type I, II, and III. Type I computes the Fourier transform at a uniform grid of frequencies from non-uniformly spaced samples in space. Type II evaluates the transform at non-uniform frequencies from uniformly spaced spatial samples. Type III handles non-uniform samples in both space and frequency. Each type uses gridding or interpolation with a chosen window (for example Kaiser-Bessel or Gaussian) and an oversampling factor to control accuracy and aliasing.

Applications are widespread in signal processing and imaging. In magnetic resonance imaging, NUFFT enables reconstruction from non-Cartesian k-space trajectories (radial, spiral). It also appears in astronomy, spectroscopy, and other computational imaging problems where data are irregularly sampled.

Limitations include parameter selection for the interpolation kernel, potential approximation error, and implementation-dependent constants. Nevertheless, NUFFT remains a standard tool for efficient, accurate non-uniform Fourier transforms.