Main |
Principles |
Papers |
Glossary of Concepts |
For Authors |
Referencing

SAT 6 (2011), 2
#### 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.

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