We consider the approximation of periodic functions belonging to Sobolev spaces of isotropic and dominating mixed smoothness. For the approximation of such a function f, a trigonometric polynomial with frequencies supported on an index set I is used. In general, this approximation causes an unavoidable error, the so-called truncation error.
Based on sampling values of the function f along a rank-1 lattice, we obtain such an approximation by a trigonometric polynomial p. Due to using sampling values, we observe an additional error in general. Our method constructs a suitable rank-1 lattice for a given frequency index set I using a component-by-component method and then performs a fast Fourier transform on the sampling values. The main advantage of our method is that it is based mainly on a single one-dimensional fast Fourier transform, and that the arithmetic complexity of computing the Fourier coefficients of the trigonometric polynomial p, which is used as approximation for the function f, depends only on the cardinality of the support of the trigonometric polynomial p in the frequency domain. Namely, the arithmetic complexity of the algorithm is O(|I|^2 \log |I| + d|I|).
We present upper bounds for the sampling error and achieve an optimal order of convergence when using suitable frequency index sets and rank-1 lattices. Numerical results are presented for up to 10 dimensions.
Moreover, we discuss the case when the frequency index set I is not given or unknown. For this, we present an approach which allows to approximately determine the largest Fourier coefficients of the function f and the corresponding frequency index set I.
This is joint work with Lutz Kämmerer and Daniel Potts.