Approximation of Functions of Few Variables in High Dimensions Academic Article uri icon


  • Let f be a continuous function defined on :=[0,1]N which depends on only coordinate variables, f(x1,...,xN) = g(xi1,...,xi). We assume that we are given m and are allowed to ask for the values of f at m points in . If g is in Lip1 and the coordinates i1,...,i are known to us, then by asking for the values of f at m=L uniformly spaced points, we could recover f to the accuracy {pipe}g{pipe}Lip1L-1 in the norm of C(). This paper studies whether we can obtain similar results when the coordinates i1,...,i are not known to us. A prototypical result of this paper is that by asking for C()L(log2 N) adaptively chosen point values of f, we can recover f in the uniform norm to accuracy {pipe}g{pipe}Lip1L-1 when gLip1. Similar results are proven for more general smoothness conditions on g. Results are also proven under the assumption that f can be approximated to some tolerance (which is not known) by functions of variables. 2010 The Author(s).

published proceedings

  • Constructive Approximation

author list (cited authors)

  • DeVore, R., Petrova, G., & Wojtaszczyk, P.

citation count

  • 40

complete list of authors

  • DeVore, Ronald||Petrova, Guergana||Wojtaszczyk, Przemyslaw

publication date

  • February 2011