Calculation of discrepancy measures and applications
From MaRDI portal
Abstract: In this book chapter we survey known approaches and algorithms to compute discrepancy measures of point sets. After providing an introduction which puts the calculation of discrepancy measures in a more general context, we focus on the geometric discrepancy measures for which computation algorithms have been designed. In particular, we explain methods to determine -discrepancies and approaches to tackle the inherently difficult problem to calculate the star discrepancy of given sample sets. We also discuss in more detail three applications of algorithms to approximate discrepancies.
Recommendations
- Applications of geometric discrepancy in numerical analysis and statistics
- Calculation of the discrepancy of a finite set of points in the unit n -cube
- An algorithm to compute bounds for the star discrepancy
- Efficient algorithms for computing the L₂-discrepancy
- Geometric discrepancy. An illustrated guide
Cites work
- \(L_2\) discrepancy and multivariate integration
- A (slightly) faster algorithm for Klee's measure problem
- A generalized discrepancy and quadrature error bound
- A genetic algorithm approach to estimate lower bounds of the star discrepancy
- A method for exact calculation of the discrepancy of low-dimensional finite point sets. I
- A method for exact calculation of the stardiscrepancy of plane sets applied to the sequences of Hammersley
- A new randomized algorithm to approximate the star discrepancy based on threshold accepting
- A note on E. Thiémard's algorithm to compute bounds for the star discrepancy
- A note on optimal point distributions in \([0,1)^{s}\)
- Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
- An algorithm to compute bounds for the star discrepancy
- An improved low-discrepancy sequence for multidimensional quasi-Monte Carlo integration
- An intermediate bound on the star discrepancy
- Application of Threshold-Accepting to the Evaluation of the Discrepancy of a Set of Points
- Asymptotic behavior of average L_p-discrepancies
- Average case complexity of multivariate integration
- Average case complexity of multivariate integration for smooth functions
- Bases in function spaces, sampling, discrepancy, numerical integration
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- Bounds for the average \(L^p\)-extreme and the \(L^\infty\)-extreme discrepancy
- Bounds for the weighted L^p discrepancy and tractability of integration
- Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
- Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?
- Component-by-component construction of good lattice rules
- Component-by-component construction of low-discrepancy point sets of small size
- Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces
- Computational geometry. Algorithms and applications.
- Computing bounds for the star discrepancy
- Computing discrepancies of Smolyak quadrature rules
- Constructing Sobol Sequences with Better Two-Dimensional Projections
- Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding
- Construction of minimal bracketing covers for rectangles
- Convergence rates for the isotrope discrepancy
- Discrépance de suites associées à un système de numération (en dimension s)
- Discrépances de suites associées à un système de numération (en dimension un)
- Discrepancy and convex programming
- Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming
- Discrepancy of generalized Hammersley type point sets in Besov spaces of dominating mixed smoothness
- Discrepancy with respect to convex polygons
- Discrepancy, integration and tractability
- Dyadic diaphony
- Efficient algorithms for computing the L₂-discrepancy
- Entropy, Randomization, Derandomization, and Discrepancy
- Error reduction techniques in quasi-Monte Carlo integration.
- Evolutionary optimization of low-discrepancy sequences
- Explicit cost bounds of algorithms for multivariate tensor product problems
- Exponential Squared Integrability of the Discrepancy Function in Two Dimensions
- Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
- Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
- Generalized Halton sequences in 2008: a comparative study
- Generating Randomized Roundings with Cardinality Constraints and Derandomizations
- Geometric discrepancy. An illustrated guide
- Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators
- Good permutations for deterministic scrambled Halton sequences in terms of L₂-discrepancy
- Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
- High dimensional integration of smooth functions over cubes
- scientific article; zbMATH DE number 5797591 (Why is no real title available?)
- scientific article; zbMATH DE number 3887061 (Why is no real title available?)
- scientific article; zbMATH DE number 53679 (Why is no real title available?)
- scientific article; zbMATH DE number 3497315 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3555292 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1099195 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 1528185 (Why is no real title available?)
- scientific article; zbMATH DE number 4000052 (Why is no real title available?)
- scientific article; zbMATH DE number 3440485 (Why is no real title available?)
- scientific article; zbMATH DE number 781100 (Why is no real title available?)
- scientific article; zbMATH DE number 914714 (Why is no real title available?)
- scientific article; zbMATH DE number 3210137 (Why is no real title available?)
- scientific article; zbMATH DE number 3226359 (Why is no real title available?)
- scientific article; zbMATH DE number 3321507 (Why is no real title available?)
- scientific article; zbMATH DE number 3393648 (Why is no real title available?)
- scientific article; zbMATH DE number 3392565 (Why is no real title available?)
- scientific article; zbMATH DE number 2233281 (Why is no real title available?)
- Implementation of a component-by-component algorithm to generate small low-discrepancy samples
- Introduction to algorithms.
- Irregularities for distribution IX
- La discrépance isotrope et l'intégration numérique
- Liberating the weights
- Minimizing the \(L_{2}\) and \(L_{\infty}\) star discrepancies of a single point in the unit hypercube
- Monte Carlo and quasi-Monte Carlo sampling
- MONTE CARLO METHODS FOR SOLVING MULTIVARIABLE PROBLEMS
- New Upper Bounds in Klee’s Measure Problem
- Numerical integration using sparse grids
- On G-discrepancy and mixed Monte Carlo and quasi-Monte Carlo sequences
- ON A WAY OF OBTAINING LOWER ESTIMATES FOR THE ERRORS OF QUADRATURE FORMULAS
- On Computing the Lattice Rule Criterion R
- On optimal extreme-discrepancy point sets in the square
- On the \(L_2\)-discrepancy for anchored boxes
- On the complexity of k-SAT
- On the complexity of computing the measure of ∪[a i ,b i ]
- On the discrepancy of convex plane sets
- On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals
- On the optimal Halton sequence
- On the step-by-step construction of quasi--Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces
- On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}
- Optimal volume subintervals with \(k\) points and star discrepancy via integer programming
- Optimization by simulated annealing
- Optimized U-type designs on flexible regions
- Parametrized complexity theory.
- Quadrature rules and distribution of points on manifolds
- Quasi-Monte Carlo methods for integration of functions with dominating mixed smoothness in arbitrary dimension
- Quasi-Random Sequences and Their Discrepancies
- Random and deterministic digit permutations of the Halton sequence
- Random and quasi-random point sets
- Randomized Halton sequences
- Randomized Rounding in the Presence of a Cardinality Constraint
- Scenario reduction in stochastic programming with respect to discrepancy distances
- Scenario Reduction Techniques in Stochastic Programming
- Sequences, discrepancies and applications
- Some applications of multidimensional integration by parts
- Some upper bounds in the theory of irregularities of distribution
- Strong computational lower bounds via parameterized complexity
- The asymptotic behavior of the average L^p-discrepancies and a randomized discrepancy
- The dispersion of the Hammersley sequence in the unit square
- The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
- The extreme and L^2 discrepancies of some plane sets
- The inverse of the star-discrepancy depends linearly on the dimension
- Tight lower bounds for certain parameterized NP-hard problems
- Tractability of multivariate problems. Volume I: Linear information
- Tractability of multivariate problems. Volume II: Standard information for functionals.
- Uniform design over general input domains with applications to target region estimation in computer experiments
- Uniform Design: Theory and Application
- Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces
- When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
- Which problems have strongly exponential complexity?
Cited in
(32)- Secure pseudorandom bit generators and point sets with low star-discrepancy
- Discrepancy of stratified samples from partitions of the unit cube
- New approach to greedy vector quantization
- A random walk algorithm to estimate a lower bound of the star discrepancy
- Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions
- Deterministic constructions of high-dimensional sets with small dispersion
- Physics-informed distribution transformers via molecular dynamics and deep neural networks
- An enumerative formula for the spherical cap discrepancy
- Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
- Extremal distributions of discrepancy functions
- A nonlocal functional promoting low-discrepancy point sets
- Octagonal symmetry in low-discrepancy -manganese
- Applications of geometric discrepancy in numerical analysis and statistics
- Discrepancy-based additive bounding procedures
- A new randomized algorithm to approximate the star discrepancy based on threshold accepting
- Some results on the complexity of numerical integration
- A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
- A Strong Law of Large Numbers for Scrambled Net Integration
- Fast variable density 3-D node generation
- Discrepancy estimates based on Haar functions
- On the discrepancy of jittered sampling
- A Metropolis random walk algorithm to estimate a lower bound of the star discrepancy
- On density extrema for digital discs
- On the expected \(\mathcal{L}_2\)-discrepancy of jittered sampling
- Measuring Disagreement with Interpolants
- Heuristic approaches to obtain low-discrepancy point sets via subset selection
- Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy
- On the discrepancy of low-dimensional probability measures
- Constructing optimal star discrepancy sets
- New bounds for the extreme and the star discrepancy of double-infinite matrices
- Generation of soft-random numbers by multi-focus approximation
- On the distribution of local extrema in quantum chaos
This page was built for publication: Calculation of discrepancy measures and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5264200)
