Walsh functions I. Orthonormality and completeness

In this post I summarize some useful properties of Walsh functions. These functions were introduced by Joseph Walsh in

  1. J. L. Walsh, A closed set of normal orthogonal functions. Amer. J. Math., 45, 5-24, 1923.

Another paper where many ideas can be found is by Nathan Fine

  1. N. J. Fine, On the Walsh functions. Trans. Amer. Math. Soc., 65, 372-414, 1949.

In this exposition here we only concentrate on the simplest case of base b = 2 and dimension s = 1.

We write \mathbb{N} for the set of natural numbers 1,2,3, \ldots and \mathbb{N}_0 for the set of nonnegative integers 0,1,2,\ldots.

A table of contents for the posts on Walsh functions can be found here.

Definition of Walsh functions

Definition (Walsh function)
Let {}k be a nonnegative integer and x \in [0,1) be a real number. Let the binary representation of {}k and {}x be given by

\displaystyle \begin{array}{rcl} k &= & \kappa_0 + \kappa_1 2 + \cdots + \kappa_{a-1} 2^{a-1}, \\ && \\ x & = & \frac{x_0}{2} + \frac{x_1}{2} + \cdots, \end{array}

where \kappa_0, \kappa_1, \ldots, \kappa_{a-1}, x_1, x_2, \ldots \in \{0,1\}. Then the {}kth Walsh function

\displaystyle \mathrm{wal}_k:[0,1) \to \{1,-1\}

is given by

\displaystyle {\rm wal}_k(x) = (-1)^{\kappa_0 x_1 + \kappa_1 x_2 + \cdots + \kappa_{a-1} x_a}

and further {\rm wal}_0(x)  = 1.

The following image shows the graph of \mathrm{wal}_k for k = 1,2,3,4.

First note that Walsh functions are piecewise constant. For k=0 we have \mathrm{wal}_0(x)=1 for all x\in [0,1). Let k  \in \mathbb{N} with binary representation k = \kappa_0+\kappa_1 2+\cdots + \kappa_{a-1}2^{a-1}. For x\in [r2^{-a},(r+1)2^{-a}) for some 0 \le r <2^a with binary representation r=r_0+r_12+\cdots+r_{a-1}2^{a-1} we have

\displaystyle \begin{array}{rcl} x&=&\frac{r_{a-1}}{2}+\frac{r_{a-2}}{2^2}+\cdots+\frac{r_0}{2^{a-1}}+\frac{x_a}{2^a}+\frac{x_{a+1}}{2^{a+1}}+\cdots,\\&&\\ y&=&\frac{r_{a-1}}{2}+\frac{r_{a-2}}{2^2}+\cdots+\frac{r_0}{2^{a-1}}+\frac{y_a}{2^a}+\frac{y_{a+1}}{2^{a+1}}+\cdots.\end{array}

Then

\displaystyle \mathrm{wal}_k(x)=(-1)^{\kappa_0r_{a-1}+\cdots+\kappa_{a-1}r_0}=\mathrm{wal}_k(y)

and hence \mathrm{wal}_k is constant on intervals of the form [r2^{-a},(r+1)2^{-a}).

Walsh functions are orthonormal

We now show that Walsh functions are orthogonal with respect to the L_2 inner product

\displaystyle \langle f, g\rangle_{L_2}=\int_0^1 f(x)g(x)\, \mathrm{d}x,

where f,g:[0,1]\to\mathbb{R} are real-valued functions. In the following we write \langle\cdot, \cdot\rangle instead of \langle \cdot, \cdot \rangle_{L_2}.

Let k\in\mathbb{N}_0, then

\displaystyle \langle \mathrm{wal}_k, \mathrm{wal}_k\rangle = \int_0^1 \mathrm{wal}_k(x)\mathrm{wal}_k(x)\,\mathrm{d}x=\int_0^1 1\,\mathrm{d}x = 1.

Now let k,l \in\mathbb{N}_0 with k\neq l have binary representations

\displaystyle \begin{array}{rcl} k&=&\kappa_0+\kappa_12+\cdots+\kappa_{a-1}2^{a-1}, \\&&\\ l&=&\lambda_0+\lambda_12+\cdots+\lambda_{b-1}2^{b-1}.\end{array}

Without loss of generality assume that a\ge b. Then

\displaystyle \begin{array}{rcl} \langle \mathrm{wal}_k, \mathrm{wal}_l \rangle & =& \int_0^1 \mathrm{wal}_k(x) \mathrm{wal}_l(x)\,\mathrm{d}x \\&& \\&=& \frac{1}{2^a}\sum_{r=0}^{2^a-1} \mathrm{wal}_k(r2^{-a}) \mathrm{wal}_l(r2^{-a}) \\&&\\&=& \frac{1}{2^a}\sum_{r_0=0}^{1}\cdots \sum_{r_{a-1}=0}^1 (-1)^{(\kappa_0+\lambda_0)r_{a-1}+\cdots+(\kappa_{a-1}+\lambda_{a-1})r_0} \\&&\\&=&\prod_{i=0}^{a-1}\frac{1}{2}\sum_{r_{a-1-i}=0}^1 (-1)^{(\kappa_i+\lambda_i)r_{a-1-i}}. \end{array}

Since k\neq l, there is an 0\le i_0 \textless a such that \kappa_{i_0}+\lambda_{i_0}=1 (where we set \lambda_b=\cdots=\lambda_{a-1}=0 if b \textless a) and therefore \sum_{r_{a-1-i_{0}}=0}^1 (-1)^{(\kappa_{i_0}+\lambda_{i_0})r_{a-1-i_0}} = 0. This implies that \langle \mathrm{wal}_k, \mathrm{wal}_l\rangle = 0.

Proposition
The Walsh functions \mathrm{wal}_k, where k=0,1,2,\ldots, are orthonormal with respect to the L_2 inner product, i.e. for all k,l \in \mathbb{N}_0 we have

\displaystyle \langle \mathrm{wal}_k, \mathrm{wal}_l \rangle = \left\{\begin{array}{rl} 1 &\mbox{if } k=l, \\ &\\ 0 &\mbox{if } k\neq l. \end{array} \right.

Walsh functions are complete

We now show that the Walsh functions form a complete orthonormal system in L_2 (see the post on the mean square convergence of Fourier series for an analoguous result for Fourier series).

Definition (Walsh polynomial)
Let N \in \mathbb{N}_0 and a_0, a_1,a_2,\ldots \in \mathbb{R} be real numbers. The function

\displaystyle \begin{array}{rcl} p:[0,1) & \to & \mathbb{R} \\ && \\ x & \mapsto & \sum_{k=0}^{N-1} a_k \mathrm{wal}_k(x) \end{array}

is called a Walsh polynomial.

As in the Fourier case, see here, we define the Dirichlet kernel for Walsh functions.

Definition (Dirichlet kernel for Walsh functions)
The Walsh polynomial

\displaystyle D_N(x) = \sum_{k=0}^{N-1} \mathrm{wal}_k(x)

is called the Walsh-Dirichlet kernel.

Lemma
For any m\in\mathbb{N}_0 we have

\displaystyle D_{2^m}(x) = \left\{\begin{array}{rl} 2^m & \mbox{if } x \in [0,2^{-m}), \\&\\ 0 & \mbox{if } x \in [2^{-m},1). \end{array} \right.

Proof
Let x=\frac{x_1}{2}+\frac{x_2}{2^2}+\cdots. If x\in[0,2^{-m}), then x_1=\cdots=x_{m}=0. Using the definition of the Dirichlet kernel we have

\displaystyle \begin{array}{rcl} D_{2^m}(x) & = & \sum_{k=0}^{2^m-1} \mathrm{wal}_k(x) \\ && \\ &=& \sum_{\kappa_0=0}^1\cdots \sum_{\kappa_{m-1}=0}^1 (-1)^{\kappa_0x_1+\cdots+\kappa_{m-1}x_m}=2^m. \end{array}

If x\in(2^{-m},1], then there is an 1\le i \le m such that {}x_i=1. Then

\displaystyle \begin{array}{rcl} D_{2^m}(x) & = & \sum_{k=0}^{2^m-1} \mathrm{wal}_k(x) \\ && \\ &=& \sum_{\kappa_0=0}^1\cdots \sum_{\kappa_{m-1}=0}^1 (-1)^{\kappa_0x_1+\cdots+\kappa_{m-1}x_m} \\ && \\ &=& \sum_{\kappa_0=0}^1 (-1)^{\kappa_0x_1} \cdots \sum_{\kappa_{m-1}=0}^1 (-1)^{\kappa_{m-1}x_m}=0, \end{array}

since \sum_{\kappa_{i-1}=0}^1 (-1)^{\kappa_{i-1}x_i}=0.
\Box

For x,y\in[0,1) with x=\frac{x_1}{2}+\frac{x_2}{2^2}+\cdots and y=\frac{y_1}{2}+\frac{y_2}{2^2}+\cdots we define the digit-wise addition and subtraction by

\displaystyle x\oplus y= \frac{u_1}{2}+\frac{u_2}{2^2}+\cdots \quad\mbox{and } x\ominus y=\frac{v_1}{2}+\frac{v_2}{2^2}+\cdots,

where u_i,v_i \in\{0,1\} are given by u_i=x_i+y_i \pmod{2} and v_i=x_i-y_i\pmod{2}.

An immediate extension of the above lemma is that for any x,y\in[0,1), where y\in[a2^{-m},(a+1)2^{-m}) for some 0\le a <2^m, we have

\displaystyle D_{2^m}(x\ominus y)=\left\{ \begin{array}{rl} 2^m &\mbox{if }  x\in[a2^{-m},(a+1)2^{-m}), \\&\\  0 & \mbox{if } x\in[0,1]\setminus [a2^{-m}, (a+1)2^{-m}). \end{array} \right.

The following result is equivalent to the completeness of the Walsh function system.

Lemma
Let f:[0,1]\to\mathbb{R} be Lebesgue integrable such that

\displaystyle \langle f, \mathrm{wal}_k\rangle = \int_0^1 f(x)\mathrm{wal}_k(x)\,\mathrm{d}x=0 \quad \mbox{for all } k \in \mathbb{N}_0.

Then f(x)=0 for almost all x\in[0,1].

Proof
Let

\displaystyle F(x)=\int_0^x f(x)\,\mathrm{d}x \quad\mbox{for } x\in[0,1].

Then by the fundamental theorem of calculus, {}F is continuous and differentiable almost everywhere with F^\prime=f. Then \langle f, \mathrm{wal}_0\rangle=0 implies that F(1)=0.

We proceed by induction on {}m. Assume that for a given integer m \ge 0 we have shown already that F(a2^{-m})=0 for all 0\le a <2^m. For any 0\le b <2^{m+1} we have

\begin{array}{rcl} \displaystyle \langle f, D_{2^{m+1}}(x\ominus b2^{-m-1})\rangle & = & \int_{b2^{-m-1}}^{(b+1)2^{-m-1}} f(x) \, \mathrm{d}x \\ && \\ & = & F((b+1)2^{-m-1})-F(b2^{-m-1}) =0 \end{array}

since \langle f, \mathrm{wal}_k\rangle = 0 and therefore

\displaystyle F(b2^{-m-1})= F((b+1)2^{-m-1}).

Since for b even we have F(b2^{-m-1})=0, it follows that F(b2^{-m-1})=0 for all 0 \le b <2^{m+1}.

Hence F(a2^{-m})=0 for all 0\le a <2^m and all m\in\mathbb{N}_0. Since {}F is continuous and the numbers \{a2^{-m}: 0\le a <2^m, m\in\mathbb{N}_0\} are dense in the interval [0,1) it follows that {}F is {}0 everywhere. Further, f(x)=F^\prime(x) almost everywhere, and hence f(x)=0 for almost all x\in[0,1].
\Box

Definition
Let f\in L_2([0,1]). Then

\displaystyle \widehat{f}(k)= \langle f, \mathrm{wal}_k\rangle

are called the Walsh coefficients of the function {}f. The formal sum

\displaystyle W(x) =\sum_{k=0}^\infty \widehat{f}(k) \mathrm{wal}_k(x)

is the Walsh series of {}f. Further we define the partial sums

\displaystyle W_K(x) = \sum_{k=0}^{K-1} \widehat{f}(k) \mathrm{wal}_k(x)

of the Walsh series of {}f.

We define the L_2-norm by \|f\|_{L_2}=\sqrt{\langle f, f \rangle_{L_2}}.

Theorem (Bessel’s inequality)
Let f\in L_2([0,1]). Then

\displaystyle \sum_{k=0}^\infty |\widehat{f}(k)|^2 \le \|f\|_{L_2}^2.

Proof
Let 0\le k \textless K, then

\displaystyle \langle f-W_k, \mathrm{wal}_k\rangle= \langle f,\mathrm{wal}_k\rangle - \widehat{f}(k)=0.

Therefore f-W_K is orthogonal to W_K and we can use Pythagoras theorem to obtain

\displaystyle \|f\|_{L_2}^2 = \|f-W_K+W_K\|_{L_2}^2=\|f-W_K\|_{L_2}^2 +\|W_K\|_{L_2}^2 \ge \|W_K\|_{L_2}^2.

Since \|W_K\|_{L_2}^2=\sum_{k=0}^{K-1} |\widehat{f}(k)|^2 the result follows by considering the limit of K\to\infty.
\Box

Note that for any f\in L_2([0,1]), Bessel’s inequality implies that W_1, W_2, \ldots is a Cauchy sequence (\|W_{M}-W_K\|^2_{L_2}= \sum_{k=K}^{M-1} |\widehat{f}(k)|^2 for M \textgreater K) and therefore converges to a function W\in L_2([0,1]) with \|W\|^2_{L_2}=\sum_{k=0}^\infty |\widehat{f}(k)|^2 \le \|f\|^2_{L_2} <\infty.

Theorem
Let f\in L_2([0,1]). Then

\displaystyle \lim_{K\to\infty} \|f-W_K\|_{L_2} = 0.

Proof
Let g=f-W. Then for all k\in \mathbb{N}_0 we have

\displaystyle \langle g, \mathrm{wal}_k\rangle = \langle f,\mathrm{wal}_k\rangle - \langle W,\mathrm{wal}_k \rangle =\widehat{f}(k)-\widehat{f}(k)=0.

If \|g\|_{L_2}>0, then set \phi(x)=g(x)/\|g\|_{L_2}. Then \phi is orthogonal to all functions \mathrm{wal}_k, k\in\mathbb{N}_0 and \|\phi\|_{L_2}=1. But this contradicts the lemma above and hence \lim_{K\to\infty} \|f-W_K\|_{L_2}= \|f-W\|_{L_2}=0.
\Box

Theorem (Parseval’s identity)
Let f\in L_2([0,1]). Then

\displaystyle \sum_{k=0}^\infty |\widehat{f}(k)|^2 = \|f\|_{L_2}^2.

Proof
We have

\displaystyle \|f\|_{L_2}^2 = \|f-W_K+W_K\|_{L_2}^2=\|f-W_K\|_{L_2}^2 +\|W_K\|_{L_2}^2.

Since \|f-W_K\|_{L_2}\to 0 as K\to \infty the result follows.
\Box

The next post on Walsh functions deals with generalizations of Walsh functions to arbitrary base and, more generally, to Walsh functions over groups.

This entry printed to pdf can be downloaded here

Advertisements

One response to “Walsh functions I. Orthonormality and completeness

  1. Pingback: Walsh functions | Biofirecorp

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