A nonuniform fast Fourier transform based on low rank approximation
This work provides a simpler and more efficient algorithm for computing NUDFTs, which are fundamental in signal processing and scientific computing, with quasi-optimal extensions to inverse and 2D transforms.
The authors propose a fast, stable algorithm for the nonuniform discrete Fourier transform (NUDFT) with complexity O(N log N log(1/ε)/log log(1/ε)), based on low-rank approximation of the entrywise ratio between NUDFT and DFT matrices. The algorithm is competitive with state-of-the-art methods and automatically adapts to working precision.
By viewing the nonuniform discrete Fourier transform (NUDFT) as a perturbed version of a uniform discrete Fourier transform, we propose a fast, stable, and simple algorithm for computing the NUDFT that costs $\mathcal{O}(N\log N\log(1/ε)/\log\!\log(1/ε))$ operations based on the fast Fourier transform, where $N$ is the size of the transform and $0<ε<1$ is a working precision. Our key observation is that a 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.