New averaging technique for approximating weighted integrals

L. Plaskota; G. W. Wasilkowski; Y. Zhao

doi:10.1016/j.jco.2009.02.004

New averaging technique for approximating weighted integrals

L. Plaskota, G. W. Wasilkowski, Y. Zhao

Computer Science

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

We consider a new averaging technique for studying the complexity of weighted multivariate integration problems. While the standard averaging requires that ∫_D K (x, x) ρ (x) d x < ∞, our new technique works under a less restrictive condition ∫_D sqrt(K (x, x)) ρ (x) d x < ∞. It allows us to conclude the existence of algorithms with the worst case errors bounded by O (n^{- 1 / 2}) for a wider class of problems than the techniques used so far. It also leads to more refined sufficient conditions for tractability of the multivariate integration problems, as well as a new class of randomized algorithms with errors bounded by O (n^{- 1} sqrt(ln (ln (n)))).

Original language	English
Pages (from-to)	268-291
Number of pages	24
Journal	Journal of Complexity
Volume	25
Issue number	3
DOIs	https://doi.org/10.1016/j.jco.2009.02.004
State	Published - Jun 2009

Bibliographical note

Funding Information:
The first author was partially supported by the Polish Ministry of Science and Higher Education under Grant 1 P03A 039 28. The second author was partially supported by the National Science Foundation under Grant DMS-0609703.

Keywords

Multivariate weighted integration
Randomized setting
Tractability
Worst case setting

ASJC Scopus subject areas

Algebra and Number Theory
Statistics and Probability
Numerical Analysis
Mathematics (all)
Control and Optimization
Applied Mathematics

Access to Document

10.1016/j.jco.2009.02.004

Cite this

@article{5b0003126e9147a386f0338aa8d69503,

title = "New averaging technique for approximating weighted integrals",

abstract = "We consider a new averaging technique for studying the complexity of weighted multivariate integration problems. While the standard averaging requires that ∫D K (x, x) ρ (x) d x < ∞, our new technique works under a less restrictive condition ∫D sqrt(K (x, x)) ρ (x) d x < ∞. It allows us to conclude the existence of algorithms with the worst case errors bounded by O (n- 1 / 2) for a wider class of problems than the techniques used so far. It also leads to more refined sufficient conditions for tractability of the multivariate integration problems, as well as a new class of randomized algorithms with errors bounded by O (n- 1 sqrt(ln (ln (n)))).",

keywords = "Multivariate weighted integration, Randomized setting, Tractability, Worst case setting",

author = "L. Plaskota and Wasilkowski, {G. W.} and Y. Zhao",

note = "Funding Information: The first author was partially supported by the Polish Ministry of Science and Higher Education under Grant 1 P03A 039 28. The second author was partially supported by the National Science Foundation under Grant DMS-0609703. ",

year = "2009",

month = jun,

doi = "10.1016/j.jco.2009.02.004",

language = "English",

volume = "25",

pages = "268--291",

number = "3",

}

TY - JOUR

T1 - New averaging technique for approximating weighted integrals

AU - Plaskota, L.

AU - Wasilkowski, G. W.

AU - Zhao, Y.

N1 - Funding Information: The first author was partially supported by the Polish Ministry of Science and Higher Education under Grant 1 P03A 039 28. The second author was partially supported by the National Science Foundation under Grant DMS-0609703.

PY - 2009/6

Y1 - 2009/6

N2 - We consider a new averaging technique for studying the complexity of weighted multivariate integration problems. While the standard averaging requires that ∫D K (x, x) ρ (x) d x < ∞, our new technique works under a less restrictive condition ∫D sqrt(K (x, x)) ρ (x) d x < ∞. It allows us to conclude the existence of algorithms with the worst case errors bounded by O (n- 1 / 2) for a wider class of problems than the techniques used so far. It also leads to more refined sufficient conditions for tractability of the multivariate integration problems, as well as a new class of randomized algorithms with errors bounded by O (n- 1 sqrt(ln (ln (n)))).

AB - We consider a new averaging technique for studying the complexity of weighted multivariate integration problems. While the standard averaging requires that ∫D K (x, x) ρ (x) d x < ∞, our new technique works under a less restrictive condition ∫D sqrt(K (x, x)) ρ (x) d x < ∞. It allows us to conclude the existence of algorithms with the worst case errors bounded by O (n- 1 / 2) for a wider class of problems than the techniques used so far. It also leads to more refined sufficient conditions for tractability of the multivariate integration problems, as well as a new class of randomized algorithms with errors bounded by O (n- 1 sqrt(ln (ln (n)))).

KW - Multivariate weighted integration

KW - Randomized setting

KW - Tractability

KW - Worst case setting

UR - http://www.scopus.com/inward/record.url?scp=67349135282&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67349135282&partnerID=8YFLogxK

U2 - 10.1016/j.jco.2009.02.004

DO - 10.1016/j.jco.2009.02.004

M3 - Article

AN - SCOPUS:67349135282

VL - 25

SP - 268

EP - 291

IS - 3

ER -

New averaging technique for approximating weighted integrals

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this