Non-uniform discrete Fourier transform

Summary

The non-uniform discrete Fourier transform (NUDFT) is a variant of the discrete Fourier transform. In it the sample points, the frequencies, or both are not equally spaced. It evaluates finite sums $\sum_n x_n e^{-2\pi i p_n f_k}$ with arbitrary real $p_n$ and $f_k$. Such data arise in medical imaging, astronomy and spectral methods, where measurements are not taken on a regular grid. Fast approximate algorithms for it are called non-uniform FFTs.