Harmonic Analysis and Applications

June 4-8, 2018


"Multiple rank-1 lattice sampling and high-dimensional sparse FFT"

Volkmer, Toni

We consider the approximate reconstruction of a high-dimensional (e.g. d=10) periodic function from samples using trigonometric polynomials. As sampling schemes, we use so-called multiple rank-1 lattices. Assuming that we know the locations of the approximately largest Fourier coefficients of a function under consideration, we can efficiently construct a suitable multiple rank-1 lattice and compute approximants using few 1-dimensional fast Fourier transforms (FFTs). For functions from Sobolev Hilbert spaces of generalized mixed smoothness, error estimates are presented where the sampling rates are optimal up to an offset slightly larger than one half in the exponent. We present numerical results which confirm the theoretical estimates. These sampling errors are almost a factor of two better up to the mentioned offset compared to single rank-1 lattice sampling. For the case where we do not know the locations of important Fourier coefficients, we present a method which approximately reconstructs high-dimensional sparse periodic signals in a dimension-incremental way based on 1-dimensional FFTs. This is joint work with Lutz Kämmerer and Daniel Potts.

« back