Approximation of functions of few variables in high dimensions (Q623354)

Many high-dimensional computational problems depend in fact on much fewer variables than originally assumed. It is important for practical computations to reduce this high (say, \(N\)) dimensional problem to fewer variables (say, \(\ell\)), and this process is known as dimension reduction. The reason for this is the so-called curse of dimensionality which states that the higher the number of variables is, the more complicated (far more complicated, that is) becomes the problem. There are several approaches to solving this question, and one of the issues is the question whether we know which ones the smaller number of coordinates are or whether we do not know that. The former case is settled to some extend, in the sense that there are error estimates for the reduced problem as compared to the original problem which depend on the number of function values we have and on the \(Lip1\)-norm of the approximand. The latter alternative is addressed in this paper where a certain number of adaptively chosen function values have to be provided to get the same order of estimates as in the former case. This number is, of course, larger, typically by a \(O(\log N)\) factor (times a factor that depends on \(\ell\)). Algorithms are explicitly provided for the mentioned adaptive choice of function evaluations.