The connection between the logarithmic Walsh degree of exactness, the t value of digital nets and an idea for future research

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 m \ge 1 be an integer and let C_1,\ldots, C_s \in \mathbb{Z}_b^{m\times m} be the generating matrices of a digital (t,m,s)-net (see here, page 161, for an introduction to digital (t,m,s)-nets). Here \mathbb{Z}_b denotes the finite field of prime order b. Let

\displaystyle C_i = \left(\begin{array}{c} c_1^{(i)} \\ c_2^{(i)} \\ \vdots \\ c_m^{(i)} \end{array}\right),

where c_k^{(i)} \in\mathbb{Z}_b^m denotes the kth row of C_i. Then the digital (t,m,s)-net property asserts that for all d_1,\ldots, d_s\ge 0 with d_1+\cdots + d_s\le m-t, the vectors

\displaystyle c_{1}^{(1)},\ldots, c_{d_1}^{(1)},\ldots, c_{1}^{(s)},\ldots, c_{d_s}^{(s)}

are linearly independent over \mathbb{Z}_b. If {}t is the smallest value with this property, then the point set is called a strict digital (t,m,s)-net. Hence the t-value provides information about the number of linearly independent vectors composed of rows from the generating matrices C_1,\ldots, C_s.

The logarithmic Walsh degree of exactness

The t-value also appears in another context. Let P=\{\boldsymbol{x}_0,\ldots, \boldsymbol{x}_{N-1}\} \subset [0,1)^s. Let \mathrm{wal}_{\boldsymbol{k}}(\boldsymbol{x}) = \prod_{i=1}^s \mathrm{wal}_{k_i}(x_i), where \boldsymbol{k}=(k_1,\ldots,k_s) and \boldsymbol{x}=(x_1,\ldots,x_s), denote the Walsh function in base {}b (see here or my blog entry for background information on Walsh functions (only b=2 is considered there)).

Let k\in\mathbb{N} have base {}b representation k=\kappa_0+\kappa_1 b + \cdots + \kappa_{a-1} b^{a-1}, where a\ge 1, \kappa_0,\ldots, \kappa_{a-1}\in\{0,\ldots,b-1\} and \kappa_{a-1}\neq 0. For k=0 we set a=0. Then we define

\displaystyle \mu(k)=a.

For vectors \boldsymbol{k}=(k_1,\ldots, k_s) \in\mathbb{N}_0^s we set

\displaystyle \mu(\boldsymbol{k})=\mu(k_1)+\cdots + \mu(k_s).

Let E\subset \mathbb{N}_0^s be a finite set. We define Walsh polynomials w_E (in base {}b) by

\displaystyle w_E=\sum_{\boldsymbol{k}\in E} \widehat{w}(\boldsymbol{k}) \mathrm{wal}_{\boldsymbol{k}},

where \widehat{w}(\boldsymbol{k})\in \mathbb{R}\setminus \{\boldsymbol{0}\} and the Walsh functions \mathrm{wal} are in base {}b. Further we define

\displaystyle  \mu(E) = \max_{\boldsymbol{k}\in E} \mu(\boldsymbol{k}).

We can now define the logarithmic Walsh degree of exactness.

Definition
Let P=\{\boldsymbol{x}_0,\ldots,\boldsymbol{x}_{N-1}\}\subset [0,1)^s be a point set.

Then the logarithmic Walsh degree of exactness \delta(P) is the largest nonnegative integer such that for all finite subsets E\subset \mathbb{N}_0^s with \mu(E)\le \delta(P) 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}.

(More generally, one can also consider sums of the form \sum_{n=0}^{N-1} \lambda_n w_E(\boldsymbol{x}_n) 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 b be a prime and let \{\boldsymbol{x}_0,\ldots,\boldsymbol{x}_{b^m -1}\} be a digital (t,m,s)-net over \mathbb{Z}_b generated by the m \times m matrices C_1,\ldots ,C_s over \mathbb{Z}_b. Then for a \boldsymbol{k}=(k_1,\ldots ,k_s) \in \{0,\ldots ,b^{m}-1\}^s we have

\displaystyle \sum_{h=0}^{b^m -1} \mathrm{wal}_{\boldsymbol{k}}(\boldsymbol{x}_h)= \left\{\begin{array}{ll} b^m & \mbox{ if } C_1^{\top} \mathbf{k}_1+\cdots +C_s^{\top} \mathbf{k}_s=\mathbf{0}, \\  0 & \mbox{ otherwise}, \end{array}\right.

where for k \in \{0,\ldots ,b^{m}-1\} we denote by \mathbf{k} the m-dimensional column vector of {}b-adic digits of {}k, i.e., \mathbf{k} \in (\mathbb{Z}_b^m)^{\top}, and \mathbf{0} denotes the zero-vector in (\mathbb{Z}_b^m)^{\top}.

Let \boldsymbol{k}\in\mathbb{N}_0^s \setminus \{\boldsymbol{0}\} and for 1\le i \le s set d_i=\mu(k_i). Then C_1^{\top} \mathbf{k}_1+\cdots +C_s^{\top} \mathbf{k}_s=\mathbf{0} if and only if the row vectors c_1^{(1)},\ldots, c_{d_1}^{(1)},\ldots, c_1^{(s)},\ldots, c_{d_s}^{(s)} are linearly dependent. Conversely, if c_1^{(1)},\ldots, c_{d_1}^{(1)},\ldots, c_1^{(s)},\ldots, c_{d_s}^{(s)} are linearly independent, then

\displaystyle \frac{1}{b^m} \sum_{n=0}^{b^m-1} \mathrm{wal}_{\boldsymbol{k}}(\boldsymbol{x}_n) = 0.

Since \boldsymbol{x}_0,\ldots, \boldsymbol{x}_{b^m-1} is a digital (t,m,s)-net, it follows that c_1^{(1)},\ldots, c_{d_1}^{(1)},\ldots, c_1^{(s)},\ldots, c_{d_s}^{(s)} are linearly independent if d_1+\cdots + d_s \le m-t. 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}

if \mu(\boldsymbol{k}) \le m-t.

From these results it follows that if P=\{ \boldsymbol{x}_0,\ldots, \boldsymbol{x}_{b^m-1} \} is a strict digital (t,m,s)-net, then

\displaystyle m-t=\delta(P).

An Ansatz for future research

We have seen that the {}t-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 {}t-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

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

where \boldsymbol{g} \in \{1,\ldots, N-1\}^s. Here \{x\} denotes the fractional part of a rational number {}x. For instance, if x=3.1415926535, then \{x\}=0.1415926535.

Let E\subset \mathbb{Z}^s be a finite set. A trigonometric polynomial is a function of the form T(\boldsymbol{x})= \sum_{\boldsymbol{k}\in E} \widehat{T}(\boldsymbol{k}) \mathrm{e}^{2\pi \mathrm{i} \boldsymbol{k} \cdot \boldsymbol{x}}, where \widehat{T}(\boldsymbol{k}) \in \mathbb{R}^s\setminus \{\boldsymbol{0}\} and the degree of {}T is the maximum of |k_1|+\cdots + |k_s| taken over all \boldsymbol{k} =(k_1,\ldots, k_s) \in E. 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 (t,m,s)-nets) with small {}t-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:

(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 {}t-value.

Advertisements

2 responses to “The connection between the logarithmic Walsh degree of exactness, the t value of digital nets and an idea for future research

  1. 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?

  2. 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.

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