Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2304.14786 · Advances in Computational Mathematics

Quasi-Monte Carlo methods for mixture distributions and approximated distributions via piecewise linear interpolation

Tiangang Cui, Josef Dick, Friedrich Pillichshammer

Published Feb 1, 2025• 6 citations
arXivHTMLPDF

Abstract

Abstract We study numerical integration over bounded regions in $$\mathbb {R}^s$$ R s , $$s \ge 1$$ s ≥ 1 , with respect to some probability measure. We replace random sampling with quasi-Monte Carlo methods, where the underlying point set is derived from deterministic constructions which aim to fill the space more evenly than random points. Ordinarily, such quasi-Monte Carlo point sets are designed for the uniform measure, and the theory only works for product measures when a coordinate-wise transformation is applied. Going beyond this setting, we first consider the case where the target density is a mixture distribution where each term in the mixture comes from a product distribution. Next, we consider target densities which can be approximated with such mixture distributions. In order to be able to use an approximation of the target density, we require the approximation to be a sum of coordinate-wise products and that the approximation is positive everywhere (so that they can be re-scaled to probability density functions). We use tensor product hat function approximations for this purpose here, since a hat function approximation of a positive function is itself positive. We also study more complex algorithms, where we first approximate the target density with a general Gaussian mixture distribution and approximate this mixture distribution with an adaptive hat function approximation on rotated intervals. The Gaussian mixture approximation allows us (at least to some degree) to locate the essential parts of the target density, whereas the adaptive hat function approximation allows us to approximate the finer structure of the target density. We prove convergence rates for each of the integration techniques based on quasi-Monte Carlo sampling for integrands with bounded partial mixed derivatives. The employed algorithms are based on digital (t, s)-sequences over the finite field $$\mathbb {F}_2$$ F 2 and an inversion method. Numerical examples illustrate the performance of the algorithms for some target densities and integrands.

DOI
10.1007/s10444-025-10223-1

Related papers

Advanced Quasi-Monte Carlo Algorithms for High-dimensional Integration and Approximation

Gowri Suryanarayana

The aim of this research is to develop algorithms to approximate the solutions of problems defined on spaces of d-variate functions, where d can be arbitrarily large. We study quasi-Monte Carlo methods, which in contrast to Monte Carlo methods, use deterministic point sets. These methods converge significantly faster with well chosen points that minimize deterministic error bounds. Additionally, we require that the computational hardness of these methods has only a moderate or no dependence on d. We study this using the information complexity n(d, epsilon), the minimal number of information operations required to achieve an approximation with an error of epsilon or less. If n(d, epsilon) grows exponentially in d, the problem is said to have the 'curse of dimension' and the goal is to vanquish this curse. Our research resulted in several contributions. We studied multivariate integration for a Hilbert space of functions that are invariant under permutations of the variables; this is inspired from the symmetry constraints induced on solutions of the Schrödinger equation for indistinguishable particles. We showed that there exist quasi-Monte Carlo methods that achieve a convergence rate of O(n^−1/2) with the implied constant depending only polynomially on d and under some conditions independent of d (and that shifted rank-1 lattice rules can attain the same). We then provided a construction algorithm for a shifted rank-1 lattice that obtains the (almost) optimal rate of convergence. Next, we extended the use of rank-1 lattice points, traditionally used for the cubature and approximation of periodic functions, to the non-periodic setting. We did this in the cosine space setting, where we extensively studied the use of tent-transformed lattice points for cubature and approximation of nonperiodic functions. We were able to reuse algorithms from the periodic setting by establishing relations between the cosine space and the Korobov space of periodic functions. Finally we studied some special cases of approximation in two dimensions. We derived explicit expressions for various degrees of exactness for the Fibonacci lattice points. We end the thesis with an insight on the Lebesgue constant of trigonometric interpolation using lattice points as interpolation nodes.

•May 27, 2016•0 citations

Quasi-Monte Carlo integration over Rs based on digital nets

Josef Dick, Friedrich Pillichshammer

This paper discusses φ -weighted integration of functions over the s -dimensional Euclidean space using quasi-Monte Carlo (QMC) rules combined with an inversion method, where the probability density function (PDF) φ is of product form, i.e., a product of uni-variate PDFs φ i for each coordinate i in { 1 , … , s } . The space of integrands is specified by means of a γ -weighted p -norm, p ≥ 1 , which involves coordinate weights γ , the partial derivatives of order up to one of the integrands as well as additional weight functions ψ i and the PDFs φ i . The coordinate weights γ model the importance of different coordinates or groups of coordinates in the sense of Sloan and Woźniakowski, and the weight functions ψ i are additional parameters of the space which describe the decay of the partial derivatives of the integrands. Fast decaying weights ψ i ( x ) for x → ± ∞ enlarge the space of functions with finite norm, but decrease the convergence rate of the worst-case error of the proposed algorithms. Our algorithms for integration use digitally shifted digital nets in combination with an inversion method. We study the (root) mean squared worst-case error with respect to random digital shifts. The obtained error bounds depend on the choice of weight functions ψ i and coordinate weights γ . Under certain conditions on γ , these bounds hold uniformly for all dimensions s . Numerical experiments demonstrate the effectiveness of the proposed algorithms.

Journal of Computational and Applied Mathematics•Dec 24, 2024•2 citations

Quasi-Monte Carlo integration over non-cubical domains

Nilofar Mortazavi

Monte Carlo (MQ) method is a powerful tool to approximate high dimensional integrals. The disadvantage of ordinary MQ is the slow convergence rate by cause of the essential randomness of this method. Computations of this convergence can lead to pure time consuming. Quasi-Monte Carlo (QMC) method yields considerably better results since this method is a deterministic alternative which uses Low-Discrepancy sequences instead of random samples . There are a multiplicity of big open problems in QMC-methods, problems partly arising from applications and partly arising from theory. QMC are developed to integrate over unite cube, where it has much more accuracy than MC for integrands of bounded variation. Integration over more general spaces such as triangles, disks and Cartesian products of such spaces is more challenging for QMC. Nevertheless in real-world applications various problems are defined over such spaces. The aim of this thesis is to provide a survey of a solution of such problems of numerical integration defined over non-cubical spaces. We present QMC and randomised QMC (RQMC) constructions in the triangle with a vanishing discrepancy based on the recent work of Basu 2016. The QMC construction is a version of the Van der Corput-Halton sequences specially made to the unit triangle. The attraction of scrambled net is replication based error estimation for QMC with slightly the same accuracy as QMC, and for smooth enough integrands.

•Jan 1, 2017•0 citations

A Universal Median Quasi-Monte Carlo Integration

Takashi Goda, Kosuke Suzuki, Makoto Matsumoto

Abstract. We study quasi-Monte Carlo (QMC) integration over the multidimensional unit cube in several weighted function spaces with different smoothness classes. We consider approximating the integral of a function by the median of several integral estimates under independent and random choices of the underlying QMC point sets (either linearly scrambled digital nets or infinite-precision polynomial lattice point sets). Even though our approach does not require any information on the smoothness and weights of a target function space as an input, we can prove a probabilistic upper bound on the worst-case error for the respective weighted function space, where the failure probability converges to 0 exponentially fast as the number of estimates increases. Our obtained rates of convergence are nearly optimal for function spaces with finite smoothness, and we can attain a dimension-independent super-polynomial convergence for a class of infinitely differentiable functions. This implies that our median-based QMC rule is universal in the sense that it does not need to be adjusted to the smoothness and the weights of the function spaces and yet exhibits the nearly optimal rate of convergence. Numerical experiments support our theoretical results.

arXiv:2209.13186•SIAM Journal on Numerical Analysis•Feb 16, 2024•16 citations

When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?

Ian H. Sloan, Henryk Woźniakowski

Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.

Journal of Complexity•Mar 1, 1998•613 citations

Weighted integration over a cube based on digital nets and sequences

Josef Dick, Friedrich Pillichshammer

Quasi-Monte Carlo (QMC) methods are equal weight quadrature rules to approximate integrals over the unit cube with respect to the uniform measure. In this paper we discuss QMC integration with respect to general product measures defined on an arbitrary cube. We only require that the cumulative distribution function is invertible. We develop a worst-case error bound and study the dependence of the error on the number of points and the dimension for digital nets and sequences as well as polynomial lattice point sets, which are mapped to the domain using the inverse cumulative distribution function. We do not require any smoothness properties of the probability density function and the worst-case error does not depend on the particular choice of density function and its smoothness. The component-by-component construction of polynomial lattice rules is based on a criterion which depends only on the size of the cube but is otherwise independent of the product measure.

arXiv:2009.06993•Sep 15, 2020•0 citations
Abstract We study numerical integration over bounded regions in Rs\mathbb {R}^sRs R s , s≥1s \ge 1s≥1 s ≥ 1 , with respect to some probability measure. We replace random sampling with quasi-Monte Carlo methods, where the underlying point set is derived from deterministic constructions which aim to fill the space more evenly than random points. Ordinarily, such quasi-Monte Carlo point sets are designed for the uniform measure, and the theory only works for product measures when a coordinate-wise transformation is applied. Going beyond this setting, we first consider the case where the target density is a mixture distribution where each term in the mixture comes from a product distribution. Next, we consider target densities which can be approximated with such mixture distributions. In order to be able to use an approximation of the target density, we require the approximation to be a sum of coordinate-wise products and that the approximation is positive everywhere (so that they can be re-scaled to probability density functions). We use tensor product hat function approximations for this purpose here, since a hat function approximation of a positive function is itself positive. We also study more complex algorithms, where we first approximate the target density with a general Gaussian mixture distribution and approximate this mixture distribution with an adaptive hat function approximation on rotated intervals. The Gaussian mixture approximation allows us (at least to some degree) to locate the essential parts of the target density, whereas the adaptive hat function approximation allows us to approximate the finer structure of the target density. We prove convergence rates for each of the integration techniques based on quasi-Monte Carlo sampling for integrands with bounded partial mixed derivatives. The employed algorithms are based on digital (t, s)-sequences over the finite field F2\mathbb {F}_2F2​ F 2 and an inversion method. Numerical examples illustrate the performance of the algorithms for some target densities and integrands.
The aim of this research is to develop algorithms to approximate the solutions of problems defined on spaces of d-variate functions, where d can be arbitrarily large. We study quasi-Monte Carlo methods, which in contrast to Monte Carlo methods, use deterministic point sets. These methods converge significantly faster with well chosen points that minimize deterministic error bounds. Additionally, we require that the computational hardness of these methods has only a moderate or no dependence on d. We study this using the information complexity n(d, epsilon), the minimal number of information operations required to achieve an approximation with an error of epsilon or less. If n(d, epsilon) grows exponentially in d, the problem is said to have the 'curse of dimension' and the goal is to vanquish this curse. Our research resulted in several contributions. We studied multivariate integration for a Hilbert space of functions that are invariant under permutations of the variables; this is inspired from the symmetry constraints induced on solutions of the Schrödinger equation for indistinguishable particles. We showed that there exist quasi-Monte Carlo methods that achieve a convergence rate of O(n^−1/2) with the implied constant depending only polynomially on d and under some conditions independent of d (and that shifted rank-1 lattice rules can attain the same). We then provided a construction algorithm for a shifted rank-1 lattice that obtains the (almost) optimal rate of convergence. Next, we extended the use of rank-1 lattice points, traditionally used for the cubature and approximation of periodic functions, to the non-periodic setting. We did this in the cosine space setting, where we extensively studied the use of tent-transformed lattice points for cubature and approximation of nonperiodic functions. We were able to reuse algorithms from the periodic setting by establishing relations between the cosine space and the Korobov space of periodic functions. Finally we studied some special cases of approximation in two dimensions. We derived explicit expressions for various degrees of exactness for the Fibonacci lattice points. We end the thesis with an insight on the Lebesgue constant of trigonometric interpolation using lattice points as interpolation nodes.
This paper discusses φ -weighted integration of functions over the s -dimensional Euclidean space using quasi-Monte Carlo (QMC) rules combined with an inversion method, where the probability density function (PDF) φ is of product form, i.e., a product of uni-variate PDFs φ i for each coordinate i in { 1 , … , s } . The space of integrands is specified by means of a γ -weighted p -norm, p ≥ 1 , which involves coordinate weights γ , the partial derivatives of order up to one of the integrands as well as additional weight functions ψ i and the PDFs φ i . The coordinate weights γ model the importance of different coordinates or groups of coordinates in the sense of Sloan and Woźniakowski, and the weight functions ψ i are additional parameters of the space which describe the decay of the partial derivatives of the integrands. Fast decaying weights ψ i ( x ) for x → ± ∞ enlarge the space of functions with finite norm, but decrease the convergence rate of the worst-case error of the proposed algorithms. Our algorithms for integration use digitally shifted digital nets in combination with an inversion method. We study the (root) mean squared worst-case error with respect to random digital shifts. The obtained error bounds depend on the choice of weight functions ψ i and coordinate weights γ . Under certain conditions on γ , these bounds hold uniformly for all dimensions s . Numerical experiments demonstrate the effectiveness of the proposed algorithms.
Monte Carlo (MQ) method is a powerful tool to approximate high dimensional integrals. The disadvantage of ordinary MQ is the slow convergence rate by cause of the essential randomness of this method. Computations of this convergence can lead to pure time consuming. Quasi-Monte Carlo (QMC) method yields considerably better results since this method is a deterministic alternative which uses Low-Discrepancy sequences instead of random samples . There are a multiplicity of big open problems in QMC-methods, problems partly arising from applications and partly arising from theory. QMC are developed to integrate over unite cube, where it has much more accuracy than MC for integrands of bounded variation. Integration over more general spaces such as triangles, disks and Cartesian products of such spaces is more challenging for QMC. Nevertheless in real-world applications various problems are defined over such spaces. The aim of this thesis is to provide a survey of a solution of such problems of numerical integration defined over non-cubical spaces. We present QMC and randomised QMC (RQMC) constructions in the triangle with a vanishing discrepancy based on the recent work of Basu 2016. The QMC construction is a version of the Van der Corput-Halton sequences specially made to the unit triangle. The attraction of scrambled net is replication based error estimation for QMC with slightly the same accuracy as QMC, and for smooth enough integrands.
Abstract. We study quasi-Monte Carlo (QMC) integration over the multidimensional unit cube in several weighted function spaces with different smoothness classes. We consider approximating the integral of a function by the median of several integral estimates under independent and random choices of the underlying QMC point sets (either linearly scrambled digital nets or infinite-precision polynomial lattice point sets). Even though our approach does not require any information on the smoothness and weights of a target function space as an input, we can prove a probabilistic upper bound on the worst-case error for the respective weighted function space, where the failure probability converges to 0 exponentially fast as the number of estimates increases. Our obtained rates of convergence are nearly optimal for function spaces with finite smoothness, and we can attain a dimension-independent super-polynomial convergence for a class of infinitely differentiable functions. This implies that our median-based QMC rule is universal in the sense that it does not need to be adjusted to the smoothness and the weights of the function spaces and yet exhibits the nearly optimal rate of convergence. Numerical experiments support our theoretical results.
Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.
Quasi-Monte Carlo (QMC) methods are equal weight quadrature rules to approximate integrals over the unit cube with respect to the uniform measure. In this paper we discuss QMC integration with respect to general product measures defined on an arbitrary cube. We only require that the cumulative distribution function is invertible. We develop a worst-case error bound and study the dependence of the error on the number of points and the dimension for digital nets and sequences as well as polynomial lattice point sets, which are mapped to the domain using the inverse cumulative distribution function. We do not require any smoothness properties of the probability density function and the worst-case error does not depend on the particular choice of density function and its smoothness. The component-by-component construction of polynomial lattice rules is based on a criterion which depends only on the size of the cube but is otherwise independent of the product measure.