19.11.2018 14:00 Toni Volkmer:
High-dimensional approximation and sparse FFT using (multiple) rank-1 latticesMI 02.10.011 (Boltzmannstr. 3, 85748 Garching)

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 rank-1 lattices, which can be constructed by a component-by-component approach when the locations of the approximately largest Fourier coefficients are known. With the help of a single one-dimensional fast Fourier transform (FFT), we are able to compute the Fourier coefficients, also in the high-dimensional case. For functions from Sobolev Hilbert spaces of generalized mixed smoothness, error estimates are presented where the sampling rates are best possible up to logarithmic factors. We give numerical results which confirm our theoretical estimates. Additionally, we discuss an approach where we use multiple instances of rank-1 lattices. This allows for efficient construction algorithms and we obtain improved error estimates where the sampling rates are optimal up to a small constant offset in the exponent. In particular, we consider the case where we do not know the locations of important Fourier coefficients. Here, we present a method which approximately reconstructs high-dimensional sparse periodic signals in a dimension-incremental way based on projections. The sampling nodes are adaptively chosen (multiple) rank-1 lattices and we use 1-dimensional FFTs for the computations. This is based on joint work with Glenn Byrenheid, Lutz Kämmerer, Daniel Potts, and Tino Ullrich.