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

We consider the approximate recovery of multivariate periodic functions from a discrete set of function values taken on a rank-1 lattice. Moreover, the main result is the fact that any (non-)linear reconstruction algorithm taking function values on any integration lattice of size M has a dimension-independent lower bound of 2-(α+1)/2M-α/2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{-(\alpha +1)/2} M^{-\alpha /2}$$\end{document} when considering the optimal worst-case error with respect to function spaces of (hybrid) mixed smoothness α>0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha >0$$\end{document} 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 method. 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.