Random points are optimal for the approximation of Sobolev functions

Abstract

We show that independent and uniformly distributed sampling points are as good as optimal sampling points for the approximation of functions from the Sobolev space $W_p^s(\Omega )$ on bounded convex domains $\Omega \subset {\mathbb{R}}^d$ in the $L_q$-norm if $q<p$. More generally, we characterize the quality of arbitrary sampling points $P\subset \Omega$ via the $L_{\gamma }(\Omega )$-norm of the distance function $\mathrm{dist}(\cdot ,\mathrm{P})$, where $\gamma =s(1/q-1/p{)}^{-1}$ if $q<p$ and $\gamma =\infty$ if $q\ge p$. This improves upon previous characterizations based on the covering radius of $P$.