Dimension-independent Sparse Fourier Transform

Michael Kapralov, Ameya Velingker, Amir Zandieh

The Discrete Fourier Transform (DFT) is a fundamental computational primitive, and the fastest known algorithm for computing the DFT is the FFT (Fast Fourier Transform) algorithm.…