Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness

Abstract

We consider the approximate recovery of multivariate periodic functions from a discrete set of function values taken on a rank-\(s\) integration lattice. The main result is the fact that any (non-)linear reconstruction algorithm taking function values on a rank-\(s\) lattice of size \(M\) has a dimension-independent lower bound of \(2^{-(\alpha+1)/2} M^{-\alpha/2}\) when considering the optimal worst-case error with respect to function spaces of (hybrid) mixed smoothness \(\alpha>0\) on the \(d\)-torus. We complement this lower bound with upper bounds that coincide up to logarithmic terms. These upper bounds are obtained by a detailed analysis of a rank-1 lattice sampling strategy, where the rank-1 lattices are constructed by a component-by-component (CBC) method. This improves on earlier results obtained in [25] and [27]. The lattice (group) structure allows for an efficient approximation of the underlying function from its sampled values using a single one-dimensional fast Fourier transform. This is one reason why these algorithms keep attracting significant interest. We compare our results to recent (almost) optimal methods based upon samples on sparse grids.