Finite-order weights imply tractability of linear multivariate problems

Greg W. Wasilkowski, H. Woźniakowski

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


We study the minimal number n (ε, d) of information evaluations needed to compute a worst case ε -approximation of a linear multivariate problem. This problem is defined over a weighted Hilbert space of functions f of d variables. One information evaluation of f is defined as the evaluation of a linear continuous functional or the value of f at a given point. Tractability means that n (ε, d) is bounded by a polynomial in both ε-1 and d. Strong Tractability means that n (ε, d) is bounded by a polynomial only in ε-1. We consider weighted reproducing kernel Hilbert spaces with finite-order weights. This means that each function of d variables is a sum of functions depending only on q* variables, where q* is independent of d. We prove that finite-order weights imply strong tractability or tractability of linear multivariate problems, depending on a certain condition on the reproducing kernel of the space. The proof is not constructive if one uses values of f.

Original languageEnglish
Pages (from-to)57-77
Number of pages21
JournalJournal of Approximation Theory
Issue number1
StatePublished - Sep 2004

Bibliographical note

Funding Information:
G.W. Wasilkowski and H. Woźniakowski were partially supported by the National Science Foundation under Grants CCR-0095709 and DMS-0308713, respectively. ∗Corresponding author. Fax: +1-859-323-1971. E-mail address: (G.W. Wasilkowski).


  • Approximation
  • Integration
  • Multivariate problems
  • Tractability

ASJC Scopus subject areas

  • Analysis
  • Numerical Analysis
  • Mathematics (all)
  • Applied Mathematics


Dive into the research topics of 'Finite-order weights imply tractability of linear multivariate problems'. Together they form a unique fingerprint.

Cite this