# 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

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

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

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 ${}k$th 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.