Sparse Fourier Transforms on Rank-1 Lattices for the Rapid and Low-Memory Approximation of Functions of Many Variables

Abstract

We consider fast, provably accurate algorithms for approximating functions on the $d$-dimensional torus, $f:{\mathbb{T}}^d\to \mathbb{C}$, that are sparse (or compressible) in the Fourier basis. In particular, suppose that the Fourier coefficients of $f$, $\{c_{\mathbf{k}}(f){\}}_{\mathbf{k}\in {\mathbb{Z}}^d}$, are concentrated in a finite set $I\subset {\mathbb{Z}}^d$ so that $$\underset{\Omega \subset Is.t.|\Omega |=s}{\min }{\Vert f-\sum _{\mathbf{k}\in \Omega }{c}_{\mathbf{k}}(f)e^{-2\pi i\mathbf{k}\cdot \circ }\Vert }_2<\epsilon \Vert f{\Vert }_2$$ holds for $s\ll |I|$ and $\epsilon \in (0,1)$. We aim to identify a near-minimizing subset $\Omega \subset I$ and accurately approximate the associated Fourier coefficients $\{c_{\mathbf{k}}(f){\}}_{\mathbf{k}\in \Omega }$ as rapidly as possible. We present both deterministic as well as randomized algorithms using $O(s^{2}d{\log }^c(|I|))$-time/memory and $O(sd{\log }^c(|I|))$-time/memory, respectively. Most crucially, all of the methods proposed herein achieve these runtimes while satisfying theoretical best $s$-term approximation guarantees which guarantee their numerical accuracy and robustness to noise for general functions. These are achieved by modifying several one-dimensional Sparse Fourier Transform (SFT) methods to subsample a function along a reconstructing rank-1 lattice for the given frequency set $I$ to rapidly identify a near-minimizing subset $\Omega \subset I$ without using anything about the lattice beyond its generating vector. This requires new fast and low-memory frequency identification techniques capable of rapidly recovering vector-valued frequencies in ${\mathbb{Z}}^d$ as opposed to simple integer frequencies in the univariate setting. Two different strategies are proposed and analyzed, each with different accuracy versus computational speed and memory tradeoffs.