5 papers
Sparse Fourier Transforms on Rank-1 Lattices for the Rapid and Low-Memory Approximation of Functions of Many Variables
Craig Gross, Mark Iwen, Lutz Kämmerer +1
We consider fast, provably accurate algorithms for approximating functions on the -dimensional torus, , that are sparse (or compressibl…
A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
Lutz Kämmerer, Felix Krahmer, Toni Volkmer
In this paper a sublinear time algorithm is presented for the reconstruction of functions that can be represented by just few out of a potentially large candidate set of Fourier ba…
A Deterministic Algorithm for Constructing Multiple Rank-1 Lattices of Near-Optimal Size
Craig Gross, Mark A. Iwen, Lutz Kämmerer +1
In this paper we present the first known deterministic algorithm for the construction of multiple rank-1 lattices for the approximation of periodic functions of many variables. The…
Worst-case recovery guarantees for least squares approximation using random samples
Lutz Kämmerer, Tino Ullrich, Toni Volkmer
We construct a least squares approximation method for the recovery of complex-valued functions from a reproducing kernel Hilbert space on . The nodes are dr…
Sparse Harmonic Transforms II: Best -Term Approximation Guarantees for Bounded Orthonormal Product Bases in Sublinear-Time
Bosu Choi, Mark Iwen, Toni Volkmer
In this paper, we develop a sublinear-time compressive sensing algorithm for approximating functions of many variables which are compressible in a given Bounded Orthonormal Product…