Random points are optimal for the approximation of Sobolev functions

Abstract

Abstract We show that independent and uniformly distributed sampling points are asymptotically as good as optimal sampling points for the approximation of functions from Sobolev spaces $W_p^s(\varOmega )$ on bounded convex domains $\varOmega \subset{\mathbb{R}}^d$ in the $L_q$-norm if $q<p$. More generally, we characterize the quality of arbitrary sampling point sets $P\subset \varOmega $ via the $L_\gamma (\varOmega )$-norm of the distance function dist$ (\cdot ,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$.

Topics & Concepts