NFFT: Algorithm for irregular sampling

Akshay Gulati, Robert James Ferguson

The nonuniform discrete Fourier transform (NDFT), used in many processing schemes, can be computed using a fast algorithm known as the non uniform fast Fourier transform (NFFT). The NFFT is not a new algorithm, but it is an approximation scheme that can be use to calculate an approximate spectrum. In one dimension, computational complexity of the NFFT is O(NlogN) which is a dramatic improvement from the O(N2) complexity of the NDFT. This algorithm can be easily extended to higher dimensions.

The approximate spectrum is calculated using a simple algorithm scheme which involves convolution of an irregularly sampled signal with a truncated Gaussian in the spatial domain. A new empirical expression based on numerical experiment for the analytical Gaussian width is proposed. Synthetic data examples, some with analytical solutions, demonstrate the utility and validity of this approach. The approximate spectrum obtained can be use further in a reconstruction algorithm. This algorithm removes the bottle neck from forward process by replacing NDFT with NFFT in many conventional processing algorithms.