Dimension-independent Sparse Fourier Transform

DOI10.1137/1.9781611975482.168zbMATH Open1435.94073arXiv1902.10633OpenAlexW2951713942MaRDI QIDQ5236359

Michael Kapralov, Ameya Velingker, Amir Zandieh

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: 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. One remarkable feature of FFT is the fact that its runtime depends only on the size $N$ of the input vector, but not on the dimensionality of the input domain: FFT runs in time $O(NlogN)$ irrespective of whether the DFT in question is on $mathbb{Z}_N$ or $mathbb{Z}_n^d$ for some $d>1$, where $N=n^d$. The state of the art for Sparse FFT, i.e. the problem of computing the DFT of a signal that has at most $k$ nonzeros in Fourier domain, is very different: all current techniques for sublinear time computation of Sparse FFT incur an exponential dependence on the dimension $d$ in the runtime. In this paper we give the first algorithm that computes the DFT of a $k$-sparse signal in time $extpoly(k,logN)$ in any dimension $d$, avoiding the curse of dimensionality inherent in all previously known techniques. Our main tool is a new class of filters that we refer to as adaptive aliasing filters: these filters allow isolating frequencies of a $k$-Fourier sparse signal using $O(k)$ samples in time domain and $O(klogN)$ runtime per frequency, in any dimension $d$. We also investigate natural average case models of the input signal: (1) worst case support in Fourier domain with randomized coefficients and (2) random locations in Fourier domain with worst case coefficients. Our techniques lead to an $widetildeO(k^2)$ time algorithm for the former and an $widetildeO(k)$ time algorithm for the latter.

Full work available at URL: https://arxiv.org/abs/1902.10633

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Numerical methods for discrete and fast Fourier transforms (65T50)

This page was built for publication: Dimension-independent Sparse Fourier Transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236359)