Approximation of Functions of Few Variables in High Dimensions
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
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).