Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time

DOI10.1145/2897518.2897650MaRDI QIDQ5361835zbMATH OpenOpenAlexFDO

Authors Michael Kapralov

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

sparse Fourier transformsublinear algorithms

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We consider the problem of computing a $k$-sparse approximation to the Fourier transform of a length $N$ signal. Our main result is a randomized algorithm for computing such an approximation (i.e. achieving the $el{l}_2/el{l}_2$ sparse recovery guarantees using Fourier measurements) using $O_d(klogNloglogN)$ samples of the signal in time domain that runs in time $O_d(klo{g}^{d+3}N)$, where $dgeq1$ is the dimensionality of the Fourier transform. The sample complexity matches the lower bound of $Omega(klog(N/k))$ for non-adaptive algorithms due to cite{DIPW} for any $kleq{N}^{1-delta}$ for a constant $delta>0$ up to an $O(loglogN)$ factor. Prior to our work a result with comparable sample complexity $klogNlo{g}^{O(1)}logN$ and sublinear runtime was known for the Fourier transform on the line cite{IKP}, but for any dimension $dgeq2$ previously known techniques either suffered from a polylogarithmic factor loss in sample complexity or required $Omega(N)$ runtime.

Recommendations

• (Nearly) sample-optimal sparse Fourier transform
• Nearly optimal sparse Fourier transform
• Dimension-independent sparse Fourier transform
• Improved approximation guarantees for sublinear-time Fourier algorithms
• Combinatorial sublinear-time Fourier algorithms

Cited in

(18)

• High-dimensional sparse Fourier algorithms
• Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
• Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
• Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables
• Multiscale high-dimensional sparse Fourier algorithms for noisy data
• A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
• Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis
• An adaptive sublinear-time block sparse Fourier transform
• A note on the high-dimensional sparse Fourier transform in the continuous setting
• Dimension-independent sparse Fourier transform
• (Nearly) sample-optimal sparse Fourier transform
• Nearly optimal sparse Fourier transform
• scientific article; zbMATH DE number 7053345 (Why is no real title available?)
• Deterministic sparse Fourier transform with an _ guarantee
• Sparse recovery for orthogonal polynomial transforms
• Optimal Extrapolation Bounds for Sparse Fourier Sums
• What's the frequency, Kenneth?: sublinear Fourier sampling off the grid
• A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing

This page was built for publication: Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time

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