# The Walsh basis

If you ask a random passerby to give you an orthonormal basis for $L^2[0,1]$, they will probably respond with $e_n(t)=\exp(2\pi i nt)$, $n\in \mathbb Z$. There is a lot to like about this exponential basis: most importantly, it diagonalizes the $\frac{d}{dt}$ operator: $\frac{d}{dt}e_n=2\pi i n e_n$. This property makes the exponential basis indispensable in the studies of differential equations. However, I prefer to describe the Walsh basis, which has several advantages:

• the basis functions take just two values $\pm 1$, which simplifies the computation of coefficients
• the proof of the basis property is easier than for the exponential basis
• there is a strong connection to probability: the Walsh expansion can be seen as conditional expectation, and the partial sums form a Doob martingale
• partial sums converge a.e. for any $L^1$ function, which is not the case for the exponential basis.

First, introduce the Rademacher functions $r_n=\mathrm{sign}\, \sin (2^{n+1} \pi t)$, $n=0,1,2,\dots$ (The enumeration is slightly different from what I used in class.) These are $r_0,r_1,r_2,r_3$:

Alternatively, one can define $r_n$ as the function which takes the values $+1,-1$ alternatively on the dyadic intervals $\displaystyle \bigg[\frac{j}{2^{n+1}},\frac{j+1}{2^{n+1}}\bigg)$.

To define the $n$th Walsh function $W_n$, express the index $n$ as the sum of powers of 2, i.e., $n=2^{p_1}+2^{p_2}+\dots$ and let $W_n=r_{p_1}r_{p_2}\dots$. For example, $W_{13}=r_3r_2r_0$ because $13=2^3+2^2+2^0$. Since the binary representation is unique, the definition makes sense. We also have $W_0=1$ because the product of an empty set of numbers is 1.

In class I checked that the set $\lbrace W_n\colon n=0,1,2,\dots\rbrace$ is orthonormal. Also, for any integer $k\ge 0$ the linear span of $\lbrace W_n\colon 0\le n< 2^k \rbrace$ is the space $V_k$ of all functions that are constant on the dyadic intervals of length $2^{-k}$. This follows by observing that $\lbrace W_n\colon 0\le n< 2^k \rbrace\subset V_k$ and that the dimension of $V_k$ is $2^k$.

To prove that the Walsh basis is indeed a basis, suppose that $h\in L^2[0,1]$ is orthogonal to all $W_n$. Since $h\perp V_k$ for all $k$, the integral of $h$ over any dyadic interval is zero (note that the characteristic function of any dyadic interval belongs to some $V_k$). But any subinterval $I\subset [0,1]$ can be written as a disjoint countable union of dyadic intervals: just take all dyadic intervals that are contained in $I$. (You don't necessarily get the right type of endpoints, but as long as we work with integrals, the difference between open and closed intervals is immaterial.) Thus, the integral of $h$ over any subinterval of $[0,1]$ is zero. By the Lebesgue differentiation theorem, for a.e. $t$ we have $\displaystyle h(t)=\lim_{\delta\to 0}\frac{1}{2\delta}\int_{t-\delta}^{t+\delta} h =0$. Thus $h=0$ as required.

The proof is even simpler if we use the non-centered form of the Lebesgue differentiation theorem: for a.e. $t$ the average $\frac{1}{b-a}\int_a^b h$ approaches $h(t)$ as $a,b\to t$ in such a way that $a\le t\le b$. Armed with this theorem, we can consider the sequence of dyadic intervals containing $t$, and immediately obtain $h(t)=0$ a.e.

Having proved that $\lbrace W_n\rbrace$ is a basis, let’s expand something in it. For example, this moderately ugly function $f$:

I used Maple to compute the coefficients $c_n=\langle f, W_n\rangle$ and plotted the partial sums $\sum_{n=0}^N c_n W_n$ for $N=1,3,7,15$:

Such partials sums (those that use $2^k$ basis functions) are particularly nice: they are obtained simply by averaging $f$ over each dyadic interval of length $2^{-k}$. In probability theory this is known as conditional expectation. The conditional expectation is a contraction in any $L^p$ space, including $L^1$ which gives so much trouble to the exponential basis. The highly oscillatory parts of $f$ are killed by the dyadic averaging; in contrast, when integrated against the exponentials, they may cleverly accumulate and destroy the convergence of partial sums.

## 1 thought on “The Walsh basis”

1. “If you ask a random passerby to give you an orthonormal basis for L^2…”

We might have different definitions of “random”!