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 g∈Lip1. 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).

author list (cited authors)

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

citation count

  • 25

publication date

  • June 2010