Abstract: By viewing the nonuniform discrete Fourier transform (NUDFT) as a perturbed version of a uniform discrete Fourier transform, we propose a fast and quasi-optimal algorithm for computing the NUDFT based on the fast Fourier transform (FFT). Our key observation is that an NUDFT and DFT matrix divided entry by entry is often well approximated by a low rank matrix, allowing us to express a NUDFT matrix as a sum of diagonally scaled DFT matrices. Our algorithm is simple to implement, automatically adapts to any working precision, and is competitive with state-of-the-art algorithms. In the fully uniform case, our algorithm is essentially the FFT. We also describe quasi-optimal algorithms for the inverse NUDFT and two-dimensional NUDFTs.

Authorship

Download reference