Abstract

We consider the problem of approximating an unknown bounded function f based on a finite number of function values. The function is defined on an arbitrary set and the error is measured in the uniform norm.   We show that for any n-dimensional space Vn of bounded functions, the knowledge of 2n function values suffices to compute an approximation of f within Vn whose error exceeds the error of best approximation of f within Vn by a factor of order at most n1/2. Previously, it was known that n function values can give the optimal approximation up to a factor n and 9n function values can give the optimal approximation up to a constant factor. The new result counterbalances the oversampling and the error.   The problem is related to the discretization of the uniform norm on Vn.   This is joint work with Kateryna Pozharska, Mario Ullrich, and Tino Ullrich.