Sampling recovery in $L_2$ and other norms

Abstract

We study the recovery of functions in various norms, including $L_p$ with $1\le p\le \infty$, based on function evaluations. We obtain worst case error bounds for general classes of functions in terms of the best $L_2$-approximation from a given nested sequence of subspaces and the Christoffel function of these subspaces. In the case $p=\infty$, our results imply that linear sampling algorithms are optimal up to a constant factor for many reproducing kernel Hilbert spaces.

References in corpus (6)

• On the worst-case error of least squares algorithms for $L_2$-approximation with high probability
• A note on sampling recovery of multivariate functions in the uniform norm
• Exponential tractability of $L_2$-approximation with function values
• New lower bounds for the integration of periodic functions
• On the power of iid information for linear approximation
• Sampling projections in the uniform norm

Cited by in corpus (1)

• Approximation of Functions: Optimal Sampling and Complexity