Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms

Karl Bringmann, Michael Kapralov, Mikhail Makarov +3

We consider the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier $k$-sparse vector $\hat{x}\in {\mathbb{C}}^{n^d}$ from…