Low discrepancy sequences in high dimensions: how well are their projections distributed? (Q2479345): Difference between revisions

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.