Open internet project 1: Lattice rules for R^s

In this post I describe an approach for constructing lattice rules which might be useful for integration in \mathbb{R}^s. The aim is to use the main ideas from the construction of digital nets over \mathbb{R}^s, see here, and apply them to lattice rules. This is the first project mentioned here.

Lattice rule

Let us first briefly describe what a lattice rule is. Let N,s \in \mathbb{N} be natural numbers and let \boldsymbol{g} \in \{1,\ldots, N-1\}^s be an integer vector. For nonnegative real numbers x \in \mathbb{R}_+ we denote by \{x\} the fractional part of {}x, that is, we have \{x\} = x- \lfloor x \rfloor. Here \lfloor x \rfloor denotes the largest integer smaller or equal to {}x. For vectors we use this approach component-wise.

Lattice rule
Let N,s \in \mathbb{N} be natural numbers and let \boldsymbol{g} \in \{1,\ldots, N-1\}^s be an integer vector. Let f:[0,1]^s \to\mathbb{R} be a function. A lattice rule Q_N is a quadrature rule of the form

\displaystyle Q_N(f) = \frac{1}{N} \sum_{n=0}^{N-1} f\left(\left\{\frac{n \boldsymbol{g}}{N} \right\}\right).

A lattice rule is useful to approximate the integral \int_{[0,1]^s} f(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x}. Background on lattice rules can be found in Sloan & Joe, Lattice methods for multiple integration, Oxford, 1994 and Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, 1992.

Lattice rules for \mathbb{R}^s

In practice the integral one needs to approximate are usually defined on \mathbb{R}^s rather than [0,1]^s. One can use some transformation to transform an integral \int_{\mathbb{R}^s} f(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x} to an integral \int_{[0,1]^s} g(\boldsymbol{y}) \,\mathrm{d} \boldsymbol{y}. It is often not clear what transformation one should use and the quality of the approximation can depend a lot on a good choice of the transformation.

In order to avoid finding a transformation, we aim to find a `lattice rule type construction` which are constructed in \mathbb{R}^s. As for the digital net case, the final point set in \mathbb{R}^s is not a classical lattice anymore. We want the point set to have a local structure, i.e., in certain subintervals of \mathbb{R}^s we basically have a classical shifted lattice rule and at the same time the whole point set should have a global structure. The goal is then to approximate the integral \int_{\mathbb{R}^s} g(\boldsymbol{y}) \,\mathrm{d} \boldsymbol{y} by a quadrature rule of the form

\displaystyle \sum_{n=0}^{N-1} \lambda_n g(\boldsymbol{y}_n).

A first idea

The first approach to constructing lattice rules in \mathbb{R}^s would be analogous to the digital net case, see the post on Quasi-Monte Carlo rules on \mathbb{R}^s. This requires several steps:

  1. First we need to solve the one-dimensional problem. Let f:\mathbb{R}\to\mathbb{R} and let \widehat{f}:\mathbb{R}\to\mathbb{R} denote its Fourier transform. We need some assumptions on the integrand. The integrand {}f itself needs to go to zero fast enough as |x| \rightarrow \infty. Further, the Fourier transform needs to go to zero fast enough as |x| \to \infty. Finally, the derivative of the integrand {}f needs to go to zero as |x| \to \infty. These three assumptions should be used to give us some idea on how to construct the points in the one-dimensional case. Tilings of the phase plane are likely to be useful for this step (some useful ideas on tilings might be here or in the references in this paper).
  2. The first step should yield points z_{i,0},\ldots, z_{i,N-1} \in \mathbb{R} for each coordinate i=1,\ldots, s. Next we construct points in \mathbb{R}^s in the following way. Let \boldsymbol{g} = (g_1,\ldots, g_s) \in \{1,\ldots, N-1\}^s be the generating vector for a lattice rule. For each 0 \le n < N we define the point \boldsymbol{x}_n = (x_{n,1},\ldots, x_{n,s}) \in \mathbb{R}^s by

    \displaystyle x_{n,i} = z_{g_i n \pmod{N}, i} \quad \mbox{for } 1 \le i \le s.

    One question is then to ask what structure such a point set has. Are there cases where one obtains shifted lattice rules again in some subcubes of \mathbb{R}^s? This would be a useful property to have. The weights \lambda_n should then be chosen such that constant functions are integrated exactly in such subcubes.

  3. Find a criterion for the generating vector of the lattice rule and introduce a construction algorithm for such lattice rules. Alternatively one could just use a generating vector constructed for Korobov lattice rules.
  4. Prove error bounds for the integration error.

Whether this approach is feasible is currently not known. Any comments and suggestions are welcome.

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