New averaging technique for approximating weighted integrals
type: Item
instance of: scholarly article
title: New averaging technique for approximating weighted integrals
zbMATH Open document ID: 1180.65032
author: Grzegorz W. Wasilkowski
author: Yaxi Zhao
author: Leszek Plaskota
published in: Journal of Complexity
publication date: 2009-06-11T00:00:00Z
review text: The authors consider the problem of approximating weighted integrals \[ I_{\rho}(f)=\int_D f(x) \rho(x) \,dx, \] where \(D \subset \mathbb{R}^d,\) \(\rho\) is a given probability density function, and \(f \in H(K)\) where \(K\) is the kernel of the reproducing kernel Hilbert space \(H(K)\). Standard averaging techniques require \(\int_DK(x,x)\rho(x)\,dx < \infty\); the authors discuss a new technique that requires only \(\int_D\sqrt{K(x,x)}\rho(x)\,dx < \infty\). As a consequence, there exist algorithms with worst case errors bounded by \(O(n^{-0.5})\) where \(n\) is the number of points in which \(f\) is evaluated, for a wider class of problems than known so far. The authors also obtain a new class of randomized algorithms with errors bounded by \(O(n^{-1}\sqrt{\ln(\ln(n))}).\)
Mathematics Subject Classification ID: 65D32
Mathematics Subject Classification ID: 41A55
Mathematics Subject Classification ID: 41A63
Mathematics Subject Classification ID: 46E22
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 5564223
zbMATH Keywords: multivariate weighted integration
zbMATH Keywords: randomized setting
zbMATH Keywords: probability density function
zbMATH Keywords: reproducing kernel Hilbert space
zbMATH Keywords: algorithms
zbMATH Keywords: worst case errors
reviewed by: Willy J. F. Govaerts
MaRDI profile type: Publication
full work available at URL: j.jco.2009.02.004
OpenAlex ID: W2016084178
cites work: Theory of Reproducing Kernels
cites work: Q4074205
cites work: Q3504234
cites work: Integration and approximation in arbitrary dimensions
cites work: Linear information versus function evaluations for \(L_2\)-approximation
cites work: On the power of standard information for multivariate approximation in the worst case setting
cites work: On Some Problems Concerning Brownian Motion in Lévy’s Sense
cites work: Deterministic and stochastic error bounds in numerical analysis
cites work: When are integration and discrepancy tractable?
cites work: Q4389411
cites work: Average case complexity of weighted approximation and integration over \(\mathbb R_{+}\)
cites work: Average-case analysis of numerical problems
cites work: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
cites work: Q4453524
cites work: Q3993279
cites work: Q3883494
cites work: Q3996207
cites work: Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure
cites work: On polynomial-time property for a class of randomized quadratures
cites work: Complexity of weighted approximation over \(\mathbb{R}\)
cites work: The power of standard information for multivariate approximation in the randomized setting
cites work: Q4000361
cites work: Average case complexity of multivariate integration
DOI: 10.1016/J.JCO.2009.02.004
description: scientific article; zbMATH DE number 5564223