Abstract
This is a follow-up paper of "Liberating the dimension for function approximation", where we studied approximation of infinitely variate functions by algorithms that use linear information consisting of finitely many linear functionals. In this paper, we study similar approximation problems, however, now the algorithms can only use standard information consisting of finitely many function values. We assume that the cost of one function value depends on the number of active variables. We focus on polynomial tractability, and occasionally also study weak tractability. We present non-constructive and constructive results. Non-constructive results are based on known relations between linear and standard information for finitely variate functions, whereas constructive results are based on Smolyak's construction generalized to the case of infinitely variate functions. Surprisingly, for many cases, the results for standard information are roughly the same as for linear information.
Original language | English |
---|---|
Pages (from-to) | 417-440 |
Number of pages | 24 |
Journal | Journal of Complexity |
Volume | 27 |
Issue number | 5 |
DOIs | |
State | Published - Oct 10 2011 |
Keywords
- Complexity
- Function approximation
- Standard information
- Tractability
ASJC Scopus subject areas
- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- General Mathematics
- Control and Optimization
- Applied Mathematics