Average case complexity of multivariate integration
By Henryk Wozniakowski. 1991
We study the average case complexity of multivariate integration for the class of continuous functions of d variables equipped with the classical Wiener sheet measure. To derive the average case complexity one needs to obtain optimal sample points. We prove that optimal design is closely related to discrepancy theory which has been extensively studied for many years. This relation enables us to show that optimal sample points can be derived from Hammersley points. Extending the result of Roth and using the recent result of Wasilkowski, we conclude that the average case complexity is θ(e -1 (lne -1 ) (d-1)/2 )
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Christiane Lemieux
- Chandra R. Bhat
- Josef Dick
- Friedrich Pillichshammer
- Erich Novak
- Xiaoqun Wang
- Henryk Wozniakowski
- Russel E. Caflisch
Citations in the corpus
- A multi-level cross-classified model for discrete response variables (2000, background): “Niederreiter, 1992; Chapter 4). In the average case, however, Wozniakowski (1991) has shown”
- Monte Carlo and quasi-Monte Carlo methods (1998, background): “In 1990, Wozniakowski (Wozniakowski 1991) proved the following surprising result.”
- Monte Carlo and Quasi-Monte Carlo Sampling (2009, methodology): “Indeed, the L2-star discrepancy T ∗(Pn) can be shown to give the expected squared error for a certain class of functions, where the expectation is taken over a Brownian sheet measure over this set of functions [434].”
- Scrambled net variance for integrals of smooth functions (1997, result): “Some well-known results are Wozniakowski 1991 who´ shows that when f is drawn from a Brownian sheet measure, the best y1Ž .”
- Walsh Series Analysis of the L2-Discrepancyof Symmetrisized Point Sets (2001, result): “These results obtain special relevance by a theorem of Wozniakowski [ 20 ] on the average complexity of numerical integration by low-discrepancy sequences.”
- Randomized Halton sequences (2000, methodology): “We will use the following result due to Wozniakowski [24]: D 2(f1 xigNi=1) 2 = E 1 N N Xi=1 f(xi) I(f) 2; (18) where D 2(f1 xigNi=1) is the L2-star-discrepancy (see (5)) of the re ected point set ( 1 xi is interpreted componentwise), and the expectation in the right hand is taken 10”
- Quasi-Random Sequences and Their Discrepancies (1994, methodology): “The derivation of (6) in [26] was simply a calculation ofeach side of the equation.”
- Tractability of Multivariate Problems (2008, methodology): “The first such relation to the average case setting was presented in [346].”
- Quasi-random maximum simulated likelihood estimation of the mixed multinomial logit model (2001, background): “Also, the reader should note that the convergence result provided here is an upper bound; in the average case, Wozniakowski (1991) has shown a much faster convergence rate for QMC sequences.”