Recently I submitted the paper titled Quasi-Monte Carlo numerical integration over : digital nets and worst-case error. I will give some heuristic explanation of the results in this paper. Interesting in this context is also the sparse grid approach from the PhD thesis of Markus Holtz (supervised by Prof. Michael Griebel).
Therein I aim to develop a theory on quasi-Monte Carlo integration over . The idea is to transform a digital net from to such that in elementary intervals of the form one has a digitally shifted digital net, and at the same time, globally one has a given (discretized) distribution.
1. Tilings of the Walsh phase plane
The analysis is based on tilings of the Walsh phase plane. We restrict ourselves to the case where the dimension and the base .
First we define Walsh functions
where the nonnegative integer and for some integer and . Here denotes the characteristic function of the interval .
We define translations and dilations of by
for with . The support of is . To each function we associate a so-called tile, this is simply a rectangle in , where , of area given by
The first interval is simply the support of , whereas the second interval corresponds to the frequency of . Hence one can think of the first coordinate of the half plane as the location of and the second coordinate as the phase (or frequency) of .
Tiles are useful in the following way:
1. Two functions are orthogonal if and only if do not intersect.
Orthogonal means that the inner product
If the support of the two functions does not intersect then the corresponding tiles do also not intersect. If the support does intersect but the frequency differs then the functions are still orthogonal (as usual for Walsh functions). In this case the tiles do not intersect as well. The second property concerns the completeness, namely, roughly speaking,
2. if one takes a set of functions of the form such that the corresponding tiles are disjoint and cover then the set of functions is a complete orthonormal system in .
This is now useful in the sense that we are flexible in choosing an orthonormal system in .
2. Three types of smoothness
Again we consider only dimension . Let the Walsh coefficient be given by
Assume we write in each tile the value . Then, roughly speaking, the values of decay in three directions as shown in the following picture.
Direction 1 is when the frequency increases, Direction 2 is when the location changes by moving further away from the origin, that is, increases, and Direction 3 is when both frequency and location change simultaneously, that is, and increase simultaneously.
Roughly speaking, this decay follows from the bounds
where is a constant which depends only on and
Those three types of smoothness are needed because of the following:
- Direction 1: When the frequency increases the Walsh coefficients decay according to the smoothness of the function . This is needed since we want the Walsh series to converge.
- Direction 2: We need , hence we want as . Hence also the Walsh coefficients should decay as one moves away from the origin.
- Direction 3: Roughly speaking, if , then as . In this case we also have a decay of the Walsh coefficients in direction 3.
Why a decay in Direction 3 is usefull will be explained in the following section.
3. Numerical integration
Still consider . We now construct point sets which integrate certain exactly.
For example one could aim at integrating all functions for which the tiles are in a certain area exactly. To integrate tiles for which the second coordinate is large, we need a large number of points. Hence, if we have a decay of the Walsh coefficients in Direction 3, then the further we go away from the origin, the less points are needed in these regions.
If there is no decay of the Walsh coefficients in Direction 3, then this means that the red lines in the picture above should form a rectangle. Hence the number of points in this case is large (and increases exponentially with the number of dimensions). This makes the problem infeasible.
Thus, for the method we consider here, to integrate functions we need to look at the distribution of the Walsh coefficients of .
4. Construction of points
In one dimension, the construction of points is relatively simple. For each elementary interval (corresponding to the support of , we put equally spaced points such that the first point is on the left side of the elementary interval and the distance between the points is as shown in the picture below.
For dimension we use digital nets. For this case, in each coordinate we introduce a numbering of the points like in the picture below.
Then we construct a point set in the following way. Let be the generating matrices of a digital -net over . Let
Then instead of mapping the vector onto we define a number
Then the point in our numbering as in the picture which was assigned yields the th coordinate of the th point.
An example of a point set in (i.e. ) constructed this way may look the following way.
The inner four rectangles all contain digitally shifted digital nets with points and the outer rectangles contain digitally shifted digital nets with points. (Notice that the rectangles are considered to be closed on the left and bottom and open on the right and top, so that points on the boundary of two rectangles always belong to the one which is on the right or at the top.)
Notice that the number of points decreases as we go away from the origin since we assume a decay of the Walsh coefficients in Direction 3. In terms of the construction of the points this means that the number of points decreases as we move away from the origin. Furthermore, if we move away from the origin in both coordinates simultaneously, then we need even less points, since we now have a decay of the Walsh coefficients in both coordinates. Hence we only need to use points which are in a hyperbolic cross in as shown in the picture below.
Since the points are in some hyperbolic cross shape, we can control the number of points needed as the dimension grows, since the area we need to cover also does not grow too fast as the dimension increases. Again, this is connected with the decrease of the Walsh coefficients in the three directions.
In the paper we show that points constructed this way yield the optimal rate of convergence of the worst-case integration error.