Tractability properties of the weighted star discrepancy
The well-distributed point sets are often used in quasi-Monte Carlo integration of functions over the \(s\)-dimensional unit cube \([0,1]^{s}.\) The well-known Koksma-Hlawka inequality presents the worst-case error of this integration in the terms of the discrepancy of the point sets used in the process of integration. The so-called weighted star discrepancy was introduced as a measure of the quality of the distribution of point sets in \([0,1]^{s}\) and a weighted version of the Koksma-Hlawka inequality was shown. The present paper considers the tractability properties of the weighted star discrepancy. The conditions which must satisfy the weights that guarantee the tractability of the weighted star discrepancy are obtained. In the Introduction the concepts of the classical star discrepancy and the weighted star discrepancy are presented. Two kinds of weights, the so-called product weights and finite-order weights are reminded. The notions of an inverse of the weighted star discrepancy, a tractability, a strong tractability of the weighted star discrepancy, an \(s\)-exponent and an \(\varepsilon\)-exponent of the tractability are given. The main results are exposed in Section 2. Using a technique for studying the classical star discrepancy, in Theorem 1 the existence of point sets in the \(s\)-dimensional unit cube, such that the weighted star discrepancy satisfies a certain upper bound is shown. From this Theorem the tractability results are deduced. In Corollary 1 a condition on the weights that the weighted star discrepancy is tractable with \(s\)-exponent zero and \(\varepsilon\)-exponent at most 2 is obtained. The constant of this result is unknown. In Theorem 2 the existence of a point set in the \(s\)-dimensional unit cube and an upper bound of the weighted star discrepancy with an explicit constant are realized. In Theorem 3 the condition which must satisfy the product weights that the weighted star discrepancy is strongly tractable with \(\varepsilon\)-exponent equal to one is presented. The aim of Section 3 is to show that the logarithmic factor in the dimension in the tractability results is indeed necessary for a large class of weights, that the star discrepancy is not strongly tractable for such weights. In Theorem 4, in the case that all weights of order 2 are bounded below by a positive constant, a lower bound of the weighted star discrepancy is given. The obtained result confirms that the weighted star discrepancy is not strongly tractable for such weights.
- Tractability results for the weighted star-discrepancy
- Tractability properties of the weighted star discrepancy of the Halton sequence
- On strong tractability of weighted multivariate integration
- Tractability properties of the weighted star discrepancy of regular grids
- A note on \((s,t)\)-weak tractability of the weighted star discrepancy of regular grids
- A constructive approach to strong tractability using quasi-Monte Carlo algorithms
- A note on the existence of sequences with small star discrepancy
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- Bounds for the weighted L^p discrepancy and tractability of integration
- Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
- Finite-order weights imply tractability of multivariate integration
- Good lattice rules in weighted Korobov spaces with general weights
- scientific article; zbMATH DE number 53679 (Why is no real title available?)
- scientific article; zbMATH DE number 3440485 (Why is no real title available?)
- Liberating the weights
- On the mean square weighted \(\mathcal {L}_2\) discrepancy of randomized digital nets in prime base
- On the mean square weighted L2discrepancy of randomized digital (t,m,s)-nets over Z2
- Sequences, discrepancies and applications
- Some open problems concerning the star-discrepancy
- Strong tractability of multivariate integration using quasi–Monte Carlo algorithms
- The inverse of the star-discrepancy depends linearly on the dimension
- Weighted star discrepancy of digital nets in prime bases
- When are integration and discrepancy tractable?
- When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
- Weighted discrepancy and high-dimensional numerical integration
- Tractability properties of the weighted star discrepancy of the Halton sequence
- Tractability properties of the weighted star discrepancy of regular grids
- A note on \((s,t)\)-weak tractability of the weighted star discrepancy of regular grids
- Tractability properties of the discrepancy in Orlicz norms
- Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions
- Tractability results for the weighted star-discrepancy
- Equivalence of weighted anchored and ANOVA spaces of functions with mixed smoothness of order one in \(L_p\)
- Low discrepancy sequences in high dimensions: how well are their projections distributed?
- Quasi-Monte Carlo methods for high-dimensional integration: the standard (weighted Hilbert space) setting and beyond
- A new randomized algorithm to approximate the star discrepancy based on threshold accepting
- The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
- On the Behavior of the Weighted Star Discrepancy Bounds for Shifted Lattice Rules
- The weighted star discrepancy of Korobov’s p-sets
- On strong tractability of weighted multivariate integration
- A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
- Discrepancy theory and quasi-Monte Carlo integration
- Entropy, Randomization, Derandomization, and Discrepancy
- Weighted star discrepancy of digital nets in prime bases
- Bounds for the weighted L^p discrepancy and tractability of integration
- Conditions for tractability of the weighted L_p-discrepancy and integration in non-homogeneous tensor product spaces
- The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension
- The star discrepancy of a union of randomly shifted Korobov lattice point sets depends polynomially on the dimension
This page was built for publication: Tractability properties of the weighted star discrepancy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2483202)
