Tractability of Linear Multivariate Problems in the Average Case Setting

Fred Hickernell (), Greg Wasilkowski () and Henryk Woźniakowski ()
Additional contact information
Fred Hickernell: Illinois Institute of Technology, Department of Applied Mathematics
Greg Wasilkowski: University of Kentucky, Department of Computer Science
Henryk Woźniakowski: Columbia University, Department of Computer Science

A chapter in Monte Carlo and Quasi-Monte Carlo Methods 2006, 2008, pp 461-493 from Springer

Abstract: Summary We study the average case setting for linear multivariate problems defined over a separable Banach space of functions f of d variables. The Banach space is equipped with a Gaussian measure. We approximate linear multivariate problems by computing finitely many information evaluations. An information evaluation is defined as an evaluation of a continuous linear functional from a given class Λ. We consider two classes of information evaluations; the first class Λ all consists of all continuous linear functionals, and the second class Λ std consists of function evaluations. We investigate the minimal number n(ε, d,Λ) of information evaluations needed to reduce the initial average case error by a factor ε. The initial average case error is defined as the minimal error that can be achieved without any information evaluations. We study tractability of linear multivariate problems in the average case setting. Tractability means that n(ε, d,Λ) is bounded by a polynomial in both ε −1 and d, and strong tractability means that n(ε, d,Λ) is bounded by a polynomial only in ε −1. For the class Λ all, we provide necessary and sufficient conditions for tractability and strong tractability in terms of the eigenvalues of the covariance operator of a Gaussian measure on the space of solution elements. These conditions are simplified under additional assumptions on the measure. In particular, we consider measures with finite-order weights and product weights. For finite-order weights, we prove that linear multivariate problems are always tractable.

Keywords: Covariance Operator; Average Case; Information Evaluation; Gaussian Measure; Separable Banach Space (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-74496-2_27

Ordering information: This item can be ordered from
http://www.springer.com/9783540744962

DOI: 10.1007/978-3-540-74496-2_27

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().