Dimension-independent sparse Fourier transform

DOI10.1137/1.9781611975482.168MaRDI QIDQ5236359zbMATH OpenOpenAlexFDO

Authors 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)

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

Mathematics Subject Classification ID

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

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.

Recommendations

• Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
• Nearly optimal sparse Fourier transform
• (Nearly) sample-optimal sparse Fourier transform
• High-dimensional sparse Fourier algorithms
• scientific article; zbMATH DE number 7053345

Cited in

(15)

• High-dimensional sparse Fourier algorithms
• Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
• Sparse Fourier Transform via Butterfly Algorithm
• Sparse Discrete Fractional Fourier Transform and Its Applications
• Optimized Spectrum Permutation for the Multidimensional Sparse FFT
• A note on the high-dimensional sparse Fourier transform in the continuous setting
• Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
• scientific article; zbMATH DE number 6796498 (Why is no real title available?)
• Nearly optimal sparse Fourier transform
• scientific article; zbMATH DE number 7053345 (Why is no real title available?)
• Performance of the multiscale sparse fast Fourier transform algorithm
• A time splitting method for the three-dimensional linear Pauli equation
• Deterministic sparse Fourier transform with an _ guarantee
• Sparse recovery for orthogonal polynomial transforms
• Sparse generalized Fourier transforms

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)