In this entry we show how the Walsh degree of a digital net is connected to its t value. This can lead to future research by using ideas developed for finding lattice rules with large trigonometric degree.
Notice that we assume some prior knowledge here, which can be found in the book (Chapters 4 and 10).
Let 
be an integer and let 
be the generating matrices of a digital 
-net (see here, page 161, for an introduction to digital -nets). Here 
denotes the finite field of prime order 
Let
where 
denotes the 
th row of 
Then the digital -net property asserts that for all 
with 
, the vectors
are linearly independent over 
If 
is the smallest value with this property, then the point set is called a strict digital -net. Hence the 
-value provides information about the number of linearly independent vectors composed of rows from the generating matrices 
The logarithmic Walsh degree of exactness
The -value also appears in another context. Let 
Let 
where 
and 
denote the Walsh function in base 
(see here or my blog entry for background information on Walsh functions (only 
is considered there)).
Let 
have base representation 
where 
and 
For 
we set 
Then we define
For vectors 
we set
Let 
be a finite set. We define Walsh polynomials 
(in base ) by
where 
and the Walsh functions 
are in base 
Further we define
We can now define the logarithmic Walsh degree of exactness.
Definition
Let 
be a point set.
Then the logarithmic Walsh degree of exactness 
is the largest nonnegative integer such that for all finite subsets with 
we have
![\displaystyle \frac{1}{N} \sum_{n=0}^{N-1} w_E(\boldsymbol{x}_n) = \int_{[0,1]^s} w_E(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x}.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cfrac%7B1%7D%7BN%7D+%5Csum_%7Bn%3D0%7D%5E%7BN-1%7D+w_E%28%5Cboldsymbol%7Bx%7D_n%29+%3D+%5Cint_%7B%5B0%2C1%5D%5Es%7D+w_E%28%5Cboldsymbol%7Bx%7D%29+%5C%2C%5Cmathrm%7Bd%7D+%5Cboldsymbol%7Bx%7D.+&bg=ffffff&fg=333333&s=0 "\displaystyle \frac{1}{N} \sum_{n=0}^{N-1} w_E(\boldsymbol{x}_n) = \int_{[0,1]^s} w_E(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x}.")
(More generally, one can also consider sums of the form 
in the definition above; but this is not pursued here.)
The logarithmic Walsh degree of exactness of digital nets
Lemma 4.75 in the book (page 182) states the following result.
Lemma
Let 
be a prime and let 
be a digital -net over generated by the 
matrices 
over Then for a 
we have
where for 
we denote by 
the 
-dimensional column vector of -adic digits of 
, i.e., 
, and 
denotes the zero-vector in 
Let 
and for 
set 
Then 
if and only if the row vectors 
are linearly dependent. Conversely, if are linearly independent, then
Since 
is a digital -net, it follows that are linearly independent if 
Therefore we have
![\displaystyle \frac{1}{b^m} \sum_{n=0}^{b^m-1} \mathrm{wal}_{\boldsymbol{k}}(\boldsymbol{x}_n) = \int_{[0,1]^s} \mathrm{wal}_{\boldsymbol{k}}(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cfrac%7B1%7D%7Bb%5Em%7D+%5Csum_%7Bn%3D0%7D%5E%7Bb%5Em-1%7D+%5Cmathrm%7Bwal%7D_%7B%5Cboldsymbol%7Bk%7D%7D%28%5Cboldsymbol%7Bx%7D_n%29+%3D+%5Cint_%7B%5B0%2C1%5D%5Es%7D+%5Cmathrm%7Bwal%7D_%7B%5Cboldsymbol%7Bk%7D%7D%28%5Cboldsymbol%7Bx%7D%29+%5C%2C%5Cmathrm%7Bd%7D+%5Cboldsymbol%7Bx%7D+&bg=ffffff&fg=333333&s=0 "\displaystyle \frac{1}{b^m} \sum_{n=0}^{b^m-1} \mathrm{wal}_{\boldsymbol{k}}(\boldsymbol{x}_n) = \int_{[0,1]^s} \mathrm{wal}_{\boldsymbol{k}}(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x}")
if 
From these results it follows that if 
is a strict digital -net, then
An Ansatz for future research
We have seen that the -value is connected to the logarithmic Walsh degree of exactness. We now give some ideas how this could be used to find constructions of polynomial lattices with small -value.
The idea is to use the analogy between polynomial lattice rules and the logarithmic degree of exactness on the one hand, and lattice rules and the trigonometric degree of exactness on the other hand.
A lattice rule is a quadrature rule given by
where 
Here 
denotes the fractional part of a rational number 
For instance, if 
then 
Let 
be a finite set. A trigonometric polynomial is a function of the form 
where 
and the degree of 
is the maximum of 
taken over all 
The trigonometric degree of exactness is defined analogously as the Walsh degree of exactness with the appropriate changes.
There are several papers which introduce methods to find lattice rules with large trigonometric degree. By the analogy explained above, those methods could also be employed to find polynomial lattices (which are a special class of digital -nets) with small -value (which corresponds to a large logarithmic Walsh degree of exactness). For some ideas used for the construction of lattice rules with small trigonometric degree, see for instance:
- Cools, Ronald; Lyness, James N. Three- and four-dimensional
-optimal lattice rules of moderate trigonometric degree. Math. Comp. 70 (2001), no. 236, 1549–1567.
- Lyness, J. N.; Sørevik, Tor Five-dimensional -optimal lattice rules. Math. Comp. 75 (2006), no. 255, 1467–1480.
- Lyness, J. N.; Sørevik, T. Four-dimensional lattice rules generated by skew-circulant matrices. Math. Comp. 73 (2004), no. 245, 279–295.
(This is not a comprehensive list nor is it the most relevant list of papers. Further papers can be found by following the citations in these papers and papers which cite this papers.)
The new ansatz is now to use the ideas for finding lattice rules with large trigonometric degree to find search algorithms for polynomial lattice rules with small -value.
Like this:
Like Loading...
Related
I think this looks very interesting. Maybe the concept of a degree of exactness could be used to design point sets which perform well when used for approximation? This would be analogous to Gauss-quadrature rules, which are designed based on degree of exactness for polynomials?
Yes, that’s right, though the basis functions used for approximation are usually not orthogonal. Sparse grids for instance use interpolets – these are functions where the coefficients can be calculated exactly using a few function values. Trigonometric functions and Walsh functions seem not to be suited so well for approximation since the Fourier- and Walsh coefficients themselves need to be approximated first. The papers using this approach fail to get the best possible rate of convergence for dimensions bigger than one.