The power of random information for function approximation on manifolds

1 : RICAM Linz

2 : Institute of Mathematics and Scientific Computing, University of Graz

Suppose a function is sampled at a point set in order to reconstruct from the function values an approximant to the original function with the error being measured in an L q -norm. For this task, point sets with good covering properties are often used. We show that on a compact Riemannian manifold one may as well use uniform random points, provided that suitable conditions on the Sobolev space containing the function hold. For this purpose we present a criterion of (asymptotic) optimality of point sets for this problem. We also discuss the related approximation of the integral using uniform random points.