English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Sparse Fourier Transform by Traversing Cooley-Tukey FFT Computation Graphs

MPS-Authors
/persons/resource/persons44182

Bringmann,  Karl       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons251391

Nakos,  Vasileios
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons268335

Zandieh,  Amir
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2107.07347.pdf
(Preprint), 2MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bringmann, K., Kapralov, M., Makarov, M., Nakos, V., Yagudin, A., & Zandieh, A. (2021). Sparse Fourier Transform by Traversing Cooley-Tukey FFT Computation Graphs. Retrieved from https://arxiv.org/abs/2107.07347.


Cite as: https://hdl.handle.net/21.11116/0000-0009-B459-8
Abstract
Computing the dominant Fourier coefficients of a vector is a common task in
many fields, such as signal processing, learning theory, and computational
complexity. In the Sparse Fast Fourier Transform (Sparse FFT) problem, one is
given oracle access to a $d$-dimensional vector $x$ of size $N$, and is asked
to compute the best $k$-term approximation of its Discrete Fourier Transform,
quickly and using few samples of the input vector $x$. While the sample
complexity of this problem is quite well understood, all previous approaches
either suffer from an exponential dependence of 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$.
In this work, we introduce a new high-dimensional Sparse FFT toolkit and use
it to obtain new algorithms, both on the exact, as well as in the case of
bounded $\ell_2$ noise. This toolkit includes i) a new strategy for exploring a
pruned FFT computation tree that reduces the cost of filtering, ii) new
structural properties of adaptive aliasing filters recently introduced by
Kapralov, Velingker and Zandieh'SODA'19, and iii) a novel lazy estimation
argument, suited to reducing the cost of estimation in FFT tree-traversal
approaches. Our robust algorithm can be viewed as a highly optimized sparse,
stable extension of the Cooley-Tukey FFT algorithm.
Finally, we explain the barriers we have faced by proving a conditional
quadratic lower bound on the running time of the well-studied non-equispaced
Fourier transform problem. This resolves a natural and frequently asked
question in computational Fourier transforms. Lastly, we provide a preliminary
experimental evaluation comparing the runtime of our algorithm to FFTW and SFFT
2.0.