Surveys in Approximation Theory (SAT)

Surveys in Approximation Theory, 6 (2011), 1-23.

On the Power of Function Values for the Approximation Problem in Various Settings

Erich Novak and Henryk Woźniakowski

Abstract. This is an expository paper on approximating functions from general Hilbert or Banach spaces in the worst case, average case and randomized settings with error measured in the L_p sense. We define the power function as the ratio between the best rate of convergence of algorithms that use function values over the best rate of convergence of algorithms that use arbitrary linear functionals for a worst possible Hilbert or Banach space for which the problem of approximating functions is well defined. Obviously, the power function takes values at most one. If these values are one or close to one than the power of function values is the same or almost the same as the power of arbitrary linear functionals. We summarize and supply a few new estimates on the power function. We also indicate eight open problems related to the power function since this function has not yet been studied in many cases. We believe that the open problems will be of interest to a general audience of mathematicians.

E-print: arXiv:1011.3682

Published: 2 June 2011.

PDF file

Erich Novak
Mathematisches Institut
Universität Jena
Ernst-Abbe-Platz 2, 07740 Jena, Germany
E-mail: novak@mathematik.uni-jena.de
Homepage: http://users.minet.uni-jena/~novak

Henryk Woźniakowski
Department of Computer Science, Columbia University
New York, NY 10027, USA, and
Institute of Applied Mathematics, University of Warsaw
ul. Banacha 2, 02-097 Warszawa, Poland
E-mail: henryk@cs.columbia.edu
Homepage: http://www.cs.columbia.edu/~henryk