Low discrepancy sequences in high dimensions: how well are their projections distributed?
Low discrepancy sequencesmultivariate integrationorder-l, superposition and truncation discrepanciesQuasi-Monte Carlo methodsreproducing kernel weighted Hilbert spaces
Well-distributed sequences and other variations (11K36) Irregularities of distribution, discrepancy (11K38) Pseudo-random numbers; Monte Carlo methods (11K45) Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces) (46E22) Monte Carlo methods (65C05)
Quasi-Monte Carlo (QMC) methods have been successfully used to compute high-dimensional integrals arising in many applications. The present paper considers quantitative measures of point nets in high dimension to understand the success of QMC. In deciding which of the two point nets is the better one, the usual preference is for the one which has smaller discrepancy. Three new characteristics -- an order-\(l\) discrepancy, a superposition discrepancy and a truncation discrepancy -- are introduced and used as measures of the uniformity of the order-\textit{l} projections, all taken together. In Section 2 the notions of local discrepancy, the classical \(L_{\infty}\)-star and \(L_{2}\)-star discrepancies are reminded. Two kinds of weights, the so called product weights and order-dependent weights are defined and connected with the weighted \(L_{2}\)-star discrepancy which involves all coordinate projections of the points of the nets. In Definitions 1, 2 and 3, respectively, for an arbitrary \(s\)-dimensional \((s \geq 1)\) point net and \(l = 1, \dots, s\) the notions of the order-\textit{l } weighted \(L_{2}\)-star discrepancy, the superposition weighted \(L_{2}\)-star discrepancy and the truncation weighted \(L_{2}\)-star discrepancy are introduced. The details of the QMC integration in reproducing kernel Hilbert spaces (RKHS) are developed. In Theorem 1 the order-\textit{l }, superposition and truncation discrepancy are presented as worst-case error in RKHS with kernels, which are connected with successive projections of the original kernels. In Section 3 other ways of defining discrepancies are realized. Generalizations and tractability issues of the order-\textit{l }, superposition and truncation discrepancies are given. These generalizations are realized by a reproducing kernel approach. In Definition 4 the order-\textit{l }, superposition and truncation discrepancies with respect to general kernels are defined. The notion of normalized order-\textit{l } discrepancy in the terms of reproducing kernels is introduced. The concept of tractability of the order-\textit{l } discrepancy with respect to the normalized order-\textit{l } discrepancy is given. Theorem 2 studies the tractable properties of the order-\textit{l } discrepancy. In Theorem 3 the behavior with respect to \(s,\) \textit{l} and \(n\) of the order-\textit{l } discrepancy of the first \(n\) points of the Sobol' and Niederreiter sequences is shown. In Section 4 two concrete kernels given in an explicit form are used. For general weights the problem to compute the order-\textit{l }, superposition and truncation discrepancy is solved. In Theorem 4 formulae for truncation and order-\textit{l } discrepancies of an arbitrary \(s\)-dimensional net are given in both cases -- for product weights and order-dependent weights. In Section 5 the order-\textit{l }, superposition and truncation discrepancies of the Sobol' nets and Latin hypercube sampling (LHS) are investigated empirically. In Theorem 6 the expectation values of truncation and order-\textit{l } discrepancies of LHS are given in both cases -- for product weights and order-dependent weights. In Conclusions the new discrepancies for measuring the quality of point nets in high dimensions are compared with the classical discrepancy.
- A Comparison of Three Methods for Selecting Values of Input Variables in the Analysis of Output from a Computer Code
- A generalized discrepancy and quadrature error bound
- Average case complexity of multivariate integration
- Discrépance de suites associées à un système de numération (en dimension s)
- Efficient algorithms for computing the L₂-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 3590753 (Why is no real title available?)
- scientific article; zbMATH DE number 1103058 (Why is no real title available?)
- scientific article; zbMATH DE number 1894664 (Why is no real title available?)
- scientific article; zbMATH DE number 822320 (Why is no real title available?)
- scientific article; zbMATH DE number 914714 (Why is no real title available?)
- scientific article; zbMATH DE number 3393648 (Why is no real title available?)
- Liberating the weights
- Low-discrepancy sequences and global function fields with many rational places
- On the distribution of points in a cube and the approximate evaluation of integrals
- On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals
- On the mean square weighted L2discrepancy of randomized digital (t,m,s)-nets over Z2
- On the step-by-step construction of quasi--Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces
- Projections of digital nets and sequences
- Quasi-Random Sequences and Their Discrepancies
- Smoothness and dimension reduction in quasi-Monte Carlo methods
- Strong tractability of multivariate integration using quasi–Monte Carlo algorithms
- The effective dimension and quasi-Monte Carlo integration
- The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
- Theory of Reproducing Kernels
- Toward real-time pricing of complex financial derivatives
- Variance reduction via lattice rules
- When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
- Why Are High-Dimensional Finance Problems Often of Low Effective Dimension?
- The effective dimension and quasi-Monte Carlo integration
- Least squares polynomial chaos expansion: a review of sampling strategies
- Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets
- Are quasi-Monte Carlo algorithms efficient for two-stage stochastic programs?
- Effective discrepancy and numerical experiments
- Discrepancy, integration and tractability
- How do path generation methods affect the accuracy of quasi-Monte Carlo methods for problems in finance?
- The asymptotic efficiency of randomized nets for quadrature
- A spectral approach for the design of experiments: design, analysis and algorithms
- Primal-dual quasi-Monte Carlo simulation with dimension reduction for pricing American options
- Latin hypercube sampling and Fibonacci based lattice method comparison for computation of multidimensional integrals
- High-discrepancy sequences for high-dimensional numerical integration
- Handling Discontinuities in Financial Engineering: Good Path Simulation and Smoothing
- Error analysis of randomized quasi-Monte Carlo: non-asymptotic error bound, importance sampling and application to linear elliptic PDEs with lognormal coefficients
- Dimension reduction for quasi-Monte Carlo methods via quadratic regression
- A novel family of weighted-Newton optimal eighth order methods with dynamics
- Quasi-Monte Carlo methods with applications in finance
This page was built for publication: Low discrepancy sequences in high dimensions: how well are their projections distributed?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2479345)
