Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time

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 ${\ell }_2/{\ell }_2$ sparse recovery guarantees using Fourier measurements) using $O_d(k\log N\log \log N)$ samples of the signal in time domain that runs in time $O_d(k{\log }^{d+3}N)$, where $d\ge 1$ is the dimensionality of the Fourier transform. The sample complexity matches the lower bound of $\Omega (k\log (N/k))$ for non-adaptive algorithms due to \cite{DIPW} for any $k\le N^{1-\delta }$ for a constant $\delta >0$ up to an $O(\log \log N)$ factor. Prior to our work a result with comparable sample complexity $k\log N{\log }^{O(1)}\log N$ and sublinear runtime was known for the Fourier transform on the line \cite{IKP}, but for any dimension $d\ge 2$ previously known techniques either suffered from a polylogarithmic factor loss in sample complexity or required $\Omega (N)$ runtime.

References in corpus (1)

• Adaptive sub-linear Fourier algorithms

Cited by in corpus (1)

• Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle