Random points are optimal for the approximation of Sobolev functions
share
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(Ω) on bounded convex domains Ω⊂ℝ^d in the L_q-norm if q<p. More generally, we characterize the quality of arbitrary sampling points P⊂Ω via the L_γ(Ω)-norm of the distance function dist(·,P), where γ=s(1/q-1/p)^-1 if q<p and γ=∞ if q≥ p. This improves upon previous characterizations based on the covering radius of P.
READ FULL TEXT