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

We are interested in the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier k-sparse domain vector x ∈ C n d from observing its time domain representation x. In the exact k-sparse case the best known dimension-independent algorithm runs in near cubic time in k and it is unclear whether a faster algorithm like in low dimensions is possible. Beyond that, all known approaches either suffer from an exponential dependence of their runtime on the dimension d or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT algorithm of Cooley and Tukey, which is stable and completely insensitive to the dimension of the input vector: its runtime is O(N log N ) in any dimension d for N = n d . Our work aims to address the above issues.

First, we provide a translation/reduction of the exactly k-sparse Sparse FT problem to a concrete tree exploration task which asks to recover k leaves in a full binary tree under certain exploration rules. Subsequently, we provide (a) an almost quadratic in k time algorithm for the latter task, and (b) evidence that obtaining a strongly subquadratic time for Sparse FT via this approach is likely to be impossible. We achieve the latter by proving a conditional quadratic time lower bound on sparse polynomial multipoint evaluation (the classical non-equispaced sparse Fourier transform problem) which is a core routine in the aforementioned translation. Thus, our results combined can be viewed as an almost complete understanding of this approach, which is the only known approach that yields sublinear time dimension-independent Sparse FT algorithms.

Subsequently, we provide a robustification of our algorithm, yielding a robust cubic time algorithm under bounded ℓ 2 noise. This requires proving new structural properties of the recently introduced adaptive aliasing filters combined with a variety of new techniques and ideas. Lastly, we provide a preliminary experimental evaluation comparing the runtime of our algorithm to FFTW and SFFT 2.0.