Sparse Fourier Transforms on Rank-1 Lattices for the Rapid and Low-Memory Approximation of Functions of Many Variables
We consider fast, provably accurate algorithms for approximating functions on the d-dimensional torus, f: ๐ ^d โโ, that are sparse (or compressible) in the Fourier basis. In particular, suppose that the Fourier coefficients of f, {c_ k (f) }_ kโโค^d, are concentrated in a finite set I โโค^d so that min_ฮฉโ I s.t. |ฮฉ| =s f - โ_ kโฮฉ c_ k (f) e^ -2 ฯ i kยทโ_2 < ฯตf _2 holds for s โช |I| and ฯตโ (0,1). We aim to identify a near-minimizing subset ฮฉโ I and accurately approximate the associated Fourier coefficients { c_ k (f) }_ kโฮฉ 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(s d 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 ฮฉโ 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 โค^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.
READ FULL TEXT