Low-discrepancy point sets for non-uniform measures

Christoph Aistleitner, and Josef Dick. "Low-discrepancy point sets for non-uniform measures." Acta Arithmetica 163.4 (2014): 345-369. <http://eudml.org/doc/279496>.

@article{ChristophAistleitner2014,
abstract = {We prove several results concerning the existence of low-discrepancy point sets with respect to an arbitrary non-uniform measure μ on the d-dimensional unit cube. We improve a theorem of Beck, by showing that for any d ≥ 1, N ≥ 1, and any non-negative, normalized Borel measure μ on $[0,1]^d$ there exists a point set $x_1, ..., x_N ∈ [0,1]^d$ whose star-discrepancy with respect to μ is of order $D_N*(x_1, ..., x_N; μ ) ≪ ((log N)^\{(3d+1)/2\})/N$. For the proof we use a theorem of Banaszczyk concerning the balancing of vectors, which implies an upper bound for the linear discrepancy of hypergraphs. Furthermore, the theory of large deviation bounds for empirical processes indexed by sets is discussed, and we prove a numerically explicit upper bound for the inverse of the discrepancy for Vapnik-Chervonenkis classes. Finally, using a recent version of the Koksma-Hlawka inequality due to Brandolini, Colzani, Gigante and Travaglini, we show that our results imply the existence of cubature rules yielding fast convergence rates for the numerical integration of functions having discontinuities of a certain form.},
author = {Christoph Aistleitner, Josef Dick},
journal = {Acta Arithmetica},
keywords = {discrepancy; quasi-Monte Carlo method; Beck-Fiala theorem; inverse of discrepancy},
language = {eng},
number = {4},
pages = {345-369},
title = {Low-discrepancy point sets for non-uniform measures},
url = {http://eudml.org/doc/279496},
volume = {163},
year = {2014},
}

TY - JOUR
AU - Christoph Aistleitner
AU - Josef Dick
TI - Low-discrepancy point sets for non-uniform measures
JO - Acta Arithmetica
PY - 2014
VL - 163
IS - 4
SP - 345
EP - 369
AB - We prove several results concerning the existence of low-discrepancy point sets with respect to an arbitrary non-uniform measure μ on the d-dimensional unit cube. We improve a theorem of Beck, by showing that for any d ≥ 1, N ≥ 1, and any non-negative, normalized Borel measure μ on $[0,1]^d$ there exists a point set $x_1, ..., x_N ∈ [0,1]^d$ whose star-discrepancy with respect to μ is of order $D_N*(x_1, ..., x_N; μ ) ≪ ((log N)^{(3d+1)/2})/N$. For the proof we use a theorem of Banaszczyk concerning the balancing of vectors, which implies an upper bound for the linear discrepancy of hypergraphs. Furthermore, the theory of large deviation bounds for empirical processes indexed by sets is discussed, and we prove a numerically explicit upper bound for the inverse of the discrepancy for Vapnik-Chervonenkis classes. Finally, using a recent version of the Koksma-Hlawka inequality due to Brandolini, Colzani, Gigante and Travaglini, we show that our results imply the existence of cubature rules yielding fast convergence rates for the numerical integration of functions having discontinuities of a certain form.
LA - eng
KW - discrepancy; quasi-Monte Carlo method; Beck-Fiala theorem; inverse of discrepancy
UR - http://eudml.org/doc/279496
ER -