Liberating the dimension for function approximation: Standard information

G. W. Wasilkowski, H. Woźniakowski

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

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 languageEnglish
Pages (from-to)417-440
Number of pages24
JournalJournal of Complexity
Volume27
Issue number5
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Liberating the dimension for function approximation: Standard information'. Together they form a unique fingerprint.

Cite this