A Construction of Polynomial Lattice Rules with Small Gain Coefficients

Recently J. Baldeaux and myself submitted the manuscript titled A Construction of Polynomial Lattice Rules with Small Gain Coefficients.

In this paper we construct polynomial lattice rules which have, in some sense, small gain coefficients using a component-by-component approach. The gain coefficients, as introduced by Art Owen, indicate to what degree the method improves upon Monte Carlo. We show that the variance of an estimator based on a scrambled polynomial lattice rule constructed component-by-component decays at a rate of N^{-(2\alpha + 1) +\delta}, for all \delta >0, assuming that the function under consideration bounded fractional variation of order \alpha and where N denotes the number of quadrature points. We give some further comments on the paper.

Let

\displaystyle \widehat{I}(f) = \frac{1}{b^m} \sum_{n=0}^{b^m-1} f(\boldsymbol{x}_n),

where \boldsymbol{x}_0, \ldots, \boldsymbol{x}_{b^m-1} are a randomly scrambled polynomial lattice point set. Since random scrambling yields an unbiased estimator one has

\displaystyle \mathbb{E}[\widehat{I}(f)] = \int_{[0,1]^s} f(\boldsymbol{x}) \, \mathrm{d} \boldsymbol{x}.

Hence one considers the variance of the estimator

\displaystyle \mathrm{Var}[\widehat{I}(f)] = \mathbb{E}[(\widehat{I}(f) - \mathbb{E}[\widehat{I}(f)])^2].

It is known that

\displaystyle \mathrm{Var}(\widehat{I}(f)) = \sum_{\emptyset \neq u \subseteq [s]} \frac{b^{|u|}}{(b-1)^{|u|}} \sum_{\boldsymbol{l}_u \in \mathbb{N}^{|u|}} \frac{\sigma^2_{(\boldsymbol{l}_u,\boldsymbol{0})}(f)}{b^{|\boldsymbol{l}_u|_1}} |L_u((\boldsymbol{l}_u,\boldsymbol{0})) \cap \mathcal{D}_p(\boldsymbol{q})|  \hspace{1cm} (1)

The term \sigma_{(\boldsymbol{l}_u,\boldsymbol{0})}(f) depends only on the function f, whereas the term |L_u((\boldsymbol{l}_u,\boldsymbol{0})) \cap \mathcal{D}_p(\boldsymbol{q})| depends only on the polynomial lattice (here \mathcal{D}_p(\boldsymbol{q}) is the dual lattice which has generating vector \boldsymbol{q} and modulus p). We define the function norm

\displaystyle \|f\|_\alpha = \max_{u \subseteq [s]} \gamma^{-1/2}_u \sup_{\boldsymbol{l}_u \in \mathbb{N}^{|u|}} b^{\alpha |\boldsymbol{l}_u|_1} \sigma_{(\boldsymbol{l}_u,\boldsymbol{0})}(f).

(We also show that if f has bounded fractional variation of order \alpha then \|f\|_\alpha < \infty.) Hence one can estimate

\displaystyle \sigma_{(\boldsymbol{l}_u,\boldsymbol{0})}(f) \le \gamma_u^{1/2} b^{-\alpha |\boldsymbol{l}_u|_1}.

Using this bound in Equation (1) one obtains

\displaystyle \mathrm{Var}[\widehat{I}(f)] \le \|f\|_\alpha \sum_{\emptyset \neq u \subseteq [s]} \frac{b^{|u|}}{(b-1)^{|u|}} \sum_{\boldsymbol{l}_u \in \mathbb{N}^{|u|}} \frac{1}{b^{(2\alpha + 1) |\boldsymbol{l}_u|_1}} |L_{(\boldsymbol{l}_u, \boldsymbol{0})} \cap \mathcal{D}_p(\boldsymbol{q}). \hspace{1cm} (2)

We show that

\displaystyle B(\boldsymbol{q}, \alpha, \boldsymbol{\gamma}) := \sum_{\emptyset \neq u \subseteq [s]} \frac{b^{|u|}}{(b-1)^{|u|}} \sum_{\boldsymbol{l}_u \in \mathbb{N}^{|u|}} \frac{1}{b^{(2\alpha + 1) |\boldsymbol{l}_u|_1}} |L_{(\boldsymbol{l}_u, \boldsymbol{0})} \cap \mathcal{D}_p(\boldsymbol{q})

can be used as quality criterion in a component-by-component construction of polynomial lattices. We need to assume that 0 < \alpha \le 1, as for $\alpha = 0$ one has B(\boldsymbol{q}, 0, \boldsymbol{\gamma}) = \infty. We show that we obtain optimal upper bounds on the variance with this approach. Further, if one constructs a polynomial lattice rule for some 0 < \alpha \le 1, then this polynomial lattice rule will also be optimal if the function f has smoothness \alpha^\prime with \alpha \le \alpha^\prime \le 1. Unfortunately our method can only be used for \alpha > 0 and hence the boundary case \alpha = 0 is excluded.

It would be interesting to also obtain a result for \alpha = 0. One may proceed in the following way. To obtain Equation (2) from Equation (1) we used Hölder's inequality. Hence using Hölder's inequality with different parameters one can obtain a r function norm and bound B(\boldsymbol{q}, \alpha, \boldsymbol{\gamma}) in norm 1 - 1/r. Indeed, if one uses the 1-norm for f and the \infty-norm for B(\boldsymbol{q}, \alpha, \boldsymbol{\gamma}) one obtains a function B(\boldsymbol{q}, \alpha, \boldsymbol{\gamma}) which is also finite for \alpha = 0. One could then use this bound as quality criterion in a component-by-component approach. Although interesting, we did not find a closed form expression for this bound and hence we were not able to use the component-by-component approach. In fact, the only case where we could find a closed form expression for B(\boldsymbol{q}, \alpha, \boldsymbol{\gamma}) which we used in the paper and which we outlined above.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s