On polynomial-time property for a class of randomized quadratures
type: Item
instance of: scholarly article
title: On polynomial-time property for a class of randomized quadratures
zbMATH Open document ID: 1067.65007
published in: Journal of Complexity
publication date: 2004-11-23T00:00:00Z
review text: A class of randomized methods for the evaluation of multivariate integrals over the unit cube \([0,1]^s\) is considered. In distinction to the classical Monte Carlo method, the proposed methods use a special importance sampling, which allows to achieve remarkably smaller errors. Besides, for periodic functions these methods require less restrictive assumptions to enjoy polynomial-time and/or strong polynomial-time properties. The polynomial-time property means, roughly, that the errors are bounded from above by a polynomial in \(s\) and in \(1/n\), whereas for the strong polynomial-time property this bound is polynomial in \(1/n\) and independent of \(s\). Integrals of the form \[ I_s(f) = \int\limits_{[0,1]^s} f({\mathbf x}) d {\mathbf x} \] are considered, where \(f\) is a function of \(s\) variables, which belongs to reproducing kernel Hilbert space. Two types of kernels of a multiplicative form \({\mathcal K}_s({\mathbf x},{\mathbf y}) = \prod_{k=1}^s K_{{\gamma}_k,s}(x_k,y_k)\) are considered with \(K_{\gamma}(x,y)=1+ \gamma \, \min (x,y)\) and \(K_{\gamma}(x,y)=1+ \gamma \, ( \min (x,y) -xy)\). In the classical Monte Carlo method, the integral is approximated by a sum \(\frac{1}{n} \sum_{i=1}^n f \left( {\mathbf x}^i \right)\) with the sampling points \({\mathbf x}^i\) independently and randomly generated according to the uniform distribution on \([0,1]^s\). The actually proposed methods use the weighted sum \( \frac{1}{n} \sum_{i=1}^n f \left( {\mathbf x}^i \right) / \rho_s^{[\alpha]} \left( {\mathbf x}^i \right) \) instead with the sampling points \({\mathbf x}^i\) distributed independently, each with the probability corresponding to the probability distribution function \( \rho_s^{[\alpha]}({\mathbf x}) = { ({\mathcal K}_s({\mathbf x},{\mathbf y})) ^{\alpha}} / { \int_{[0,1]^s} ({\mathcal K}_s({\mathbf t},{\mathbf t}))^{\alpha} d {\mathbf t} } \;. \) The main result of the paper is the proof of certain error bounds for this approximation with the two kernel…
Mathematics Subject Classification ID: 65C05
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 2117864
zbMATH Keywords: multivariate integration
zbMATH Keywords: Monte Carlo methods
zbMATH Keywords: importance sampling
zbMATH Keywords: randomized methods
zbMATH Keywords: tractability
zbMATH Keywords: error bounds
zbMATH Keywords: reproducing kernel Hilbert space
author: Grzegorz W. Wasilkowski
reviewed by: J. Kaupužs
MaRDI profile type: Publication
full work available at URL: j.jco.2003.06.003
OpenAlex ID: W1983684402
cites work: Theory of Reproducing Kernels
cites work: Q4453500
cites work: Intractability results for integration and discrepancy
cites work: Q3311717
cites work: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
cites work: Q3996207
DOI: 10.1016/J.JCO.2003.06.003
description: scientific article; zbMATH DE number 2117864