Approximation of Functions of Few Variables in High Dimensions

By Ronald A. DeVore, Guergana Petrova, Przemyslaw Wojtaszczyk. 2011

74 citations recorded by the source corpus.

Let f be a continuous function defined on Ω:=[0,1]N which depends on only ℓ coordinate variables, $f(x_{1},\ldots,x_{N})=g(x_{i_{1}},\ldots,x_{i_{\ell}})$. 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 |g|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ℓ(log 2N) adaptively chosen point values of f, we can recover f in the uniform norm to accuracy |g|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.

Subfields: Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/5279ffde1b4a738ab2771ddaa503444602f974d9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Learning Sparse Additive Models with Interactions in High Dimensions (2016, methodology): “(5)Such sets were used in [5] for a more general problem involving functions that are intrinsically k variate.”
Faithful Variable Screening for High-Dimensional Convex Regression (2014, methodology): “An approximation theory approach to the same problem is presented in [8], using techniques based on hierarchical hashing schemes, similar to those used for “junta””