Article ID Journal Published Year Pages File Type
4608978 Journal of Complexity 2010 10 Pages PDF
Abstract

We consider optimal importance sampling for approximating integrals I(f)=∫Df(x)ϱ(x)dx of functions ff in a reproducing kernel Hilbert space H⊂L1(ϱ)H⊂L1(ϱ) where ϱϱ is a given probability density on D⊆RdD⊆Rd. We show that there exists another density ωω such that the worst case error of importance sampling with density function ωω is of order n−1/2n−1/2.As a result, for multivariate problems generated from nonnegative kernels we prove strong polynomial tractability of the integration problem in the randomized setting.The density function ωω is obtained from the application of change of density results used in the geometry of Banach spaces in connection with a theorem of Grothendieck concerning 2-summing operators.

Related Topics
Physical Sciences and Engineering Mathematics Analysis
Authors
,