# Walsh functions III: The convergence of the Walsh coefficients and pointwise convergence

In a previous post, we discussed the orthogonality properties of Walsh functions and showed that they form a complete orthonormal system in $L_2([0,1])$. In this post we discuss the rate of decay of the Walsh coefficients when the function has bounded variation of fractional order $0 \textless \alpha \le 1$ and we investigate pointwise convergence of the Walsh series and pointwise convergence of the Walsh series to the function. We consider only Walsh functions in base $2,$ although the results can be generalized to Walsh functions over groups. Information on Walsh functions over groups can be found in this post. For the necessary background information see the previous post on Walsh functions here. A table of contents for the posts on Walsh functions can be found here.

Let $0 \textless \alpha \le 1$. For ${}f:[0,1]\to\mathbb{R}$ we define the fractional variation

$\displaystyle V_\alpha(f)= \sup_{\mathcal{P}} \left( \sum_{n=1}^N |x_n-x_{n-1}| \left(\frac{|f(x_n)-f(x_{n-1})|}{|x_n-x_{n-1}|^\alpha}\right)^{2} \right)^{1/2},$

where the supremum is taken over all $N\in\mathbb{N}$ and all partitions $\mathcal{P} = \{0=x_0 \textless x_1 \textless \cdots \textless x_{N-1}\textless x_N=1\}.$

If $\alpha = 1$ and the function ${}f$ is continuously differentiable, then the mean value theorem implies that for all $0 \le x_{n-1} \textless x_n \le 1$ there exists a $x_{n-1} \le \xi_n \le x_n$ such that $\frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}} = f^{\prime}(\xi_n).$ Hence the Riemann integrability of $|f^\prime|^2$ implies that

$\displaystyle V_1(f) =\sup_{\mathcal{P}} \left( \sum_{n=1}^N |x_n-x_{n-1}| |f^\prime(\xi_n)|^2 \right)^{1/2} = \left(\int_0^1 |f^\prime(x)|^2 \,\mathrm{d} x \right)^{1/2}.$

Let

$\displaystyle \sigma_a(f) = \left( \sum_{k=2^{a-1}}^{2^a-1} |\widehat{f}(k)|^2 \right)^{1/2}.$

In the following we prove a bound on $\sigma_a(f)$ for functions with bounded variation, that is, for $f:[0,1]\to\mathbb{R}$ such that $V_\alpha(f) \textless \infty.$ Since $|\widehat{f}(k)| \le \sigma_a(f)$ for all $2^{a-1} \le k \textless 2^a,$ we can also obtain a bound on the Walsh coefficients.

Lemma
Let $0 \textless \alpha \le 1,$ and $f:[0,1]\to\mathbb{R}$ with $V_\alpha(f) \textless \infty.$ Then for any $a \ge 1$ we have

$\displaystyle \sigma_a(f) \le 2^{-\alpha a} V_\alpha(f).$

Proof

Let $x \in [\ell 2^{-a}, (\ell+1) 2^{-a}),$ then

$\displaystyle \sum_{k=0}^{2^a-1} \widehat{f}(k) {\rm wal}_k(x) = \int_0^1 f(t) \sum_{k=0}^{2^a-1} {\rm wal}_k(x \ominus t) \,\mathrm{d} t = 2^a \int_{\ell 2^{-a}}^{(\ell+1) 2^{-a}} f(t) \,\mathrm{d} t.$

For $a \ge 0$ and $0 \le \ell \textless 2^{a}$ let

$\displaystyle c_{a,\ell} = \int_{\ell 2^{-a}}^{(\ell+1) 2^{-a}} f(t) \,\mathrm{d} t.$

For $x \in [\ell 2^{-a}, (\ell+1) 2^{-a})$ let

$\displaystyle \begin{array}{rcl} g(x) & := & \sum_{k=2^{a-1}}^{2^a-1} \widehat{f}(k) {\rm wal}_k(x) \\ && \\ & = & \sum_{k=0}^{2^a-1} \widehat{f}(k) {\rm wal}_k(x) - \sum_{k=0}^{2^{a-1}-1} \widehat{f}(k) {\rm wal}_k(x) \\ && \\ & = & 2^{a} c_{a,\ell} - 2^{a-1} c_{a-1,\lfloor \ell/b\rfloor}.\end{array}$

Using Parseval’s identity for the Walsh function system we obtain

$\displaystyle \begin{array}{rcl} \sum_{k=2^{a-1}}^{2^a-1} |\widehat{f}(k)|^2 & = & \int_0^1 |g(x)|^2 \,\mathrm{d} x \\ & & \\ & = & \sum_{\ell=0}^{2^a-1} 2^{-a} \left|2^a c_{a,\ell}- 2^{a-1} c_{a-1,\lfloor \ell/2\rfloor} \right|^2 \\ && \\ & = & 2^{a} \sum_{\ell =0}^{2^a-1} \left| c_{a,\ell}- 2^{-1} c_{a-1,\lfloor \ell/2\rfloor} \right|^2. \end{array}$

Let $r = 2\lfloor \ell/2 \rfloor$. The last summand can be estimated by

$\displaystyle \begin{array}{rcl} |c_{a,\ell}- 2^{-1} c_{a-1,\lfloor \ell/2\rfloor}| & = & 2^{-1} |2c_{a,\ell} - c_{a,r}- c_{a,r+1}| \\ && \\ & \le & 2^{-1} \sum_{u=0}^{1} |c_{a,\ell}-c_{a,r+u}|. \end{array}$

Therefore

$\displaystyle \begin{array}{rcl} \sum_{k=2^{a-1}}^{2^a-1} |\widehat{f}(k)|^2 & \le & 2^{a-2} \sum_{\ell=0}^{2^{a}-1} \sum_{u=0}^{1} |c_{a,\ell}-c_{a,2\lfloor \ell/2\rfloor + u}| \times \\ && \\ && \sum_{u^\prime=0}^{1} |c_{a,\ell}-c_{a,2\lfloor \ell/2\rfloor + u^\prime}|. \end{array}$

We have

$\displaystyle \begin{array}{rcl} |c_{a,\ell}- c_{a,2\lfloor \ell/2\rfloor +u}| & = & \left|\int_{2^{-a}\ell}^{2^{-a}(\ell+1)} f(t) \,\mathrm{d} t - \int_{2^{-a}(2\lfloor \ell/2 \rfloor + u)}^{2^{-a}(2\lfloor \ell/2 \rfloor +u+1)} f(t) \,\mathrm{d} t \right| \\ && \\ & \le & \int_{2^{-a} \ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2\lfloor \ell/2 \rfloor + u - \ell))| \,\mathrm{d} t,\end{array}$

and therefore

$\displaystyle \begin{array}{rcl} \sum_{k=2^{a-1}}^{2^a-1} |\widehat{f}(k)|^2 & \le & 2^{a-2} \sum_{\ell=0}^{2^{a}-1} \sum_{u=0}^{1} \\ && \\ && \int_{2^{-a} \ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2\lfloor \ell/2 \rfloor + u - \ell))| \,\mathrm{d} t \times \\ && \\ && \sum_{u^\prime=0}^{1} \int_{2^{-a} \ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2\lfloor \ell/2 \rfloor + u^\prime - \ell))| \,\mathrm{d} t \\ && \\ & = & 2^{a-2} \sum_{u=0}^{1} \sum_{u^\prime=0}^{1} \sum_{\ell=0}^{2^{a}-1} \\ && \\ && \int_{2^{-a} \ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2\lfloor \ell/2 \rfloor + u - \ell))| \,\mathrm{d} t \times \\ && \\ && \int_{2^{-a} \ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2\lfloor \ell/2 \rfloor + u^\prime - \ell))| \,\mathrm{d} t. \end{array}$

Using Cauchy-Schwarz’ inequality we have

$\displaystyle \begin{array}{rcl} && \int_{2^{-a} \ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2\lfloor \ell/2 \rfloor + u - \ell))| \,\mathrm{d} t \\ && \\ & & \le \left( \int_{2^{-a}\ell}^{2^{-a}(\ell+1)} 1 \,\mathrm{d} t \right)^{1/2} \left( \int_{2^{-a}\ell}^{2^{-a}(\ell+1)} |f(t)-f(t+2^{-a}(2\lfloor \ell/2\rfloor + u - \ell))|^2 \,\mathrm{d} t \right)^{1/2} \\ && \\ & & = 2^{-a/2} \left( \int_{2^{-a}\ell}^{2^{-a}(\ell+1)} |f(t)-f(t+2^{-a}(2\lfloor \ell/2\rfloor + u - \ell))|^2 \,\mathrm{d} t \right)^{1/2}, \end{array}$

which implies

$\displaystyle \begin{array}{rcl} && \sum_{k=2^{a-1}}^{2^a-1} |\widehat{f}(k)|^2 \le 2^{-2} \sum_{u=0}^{1} \sum_{u^\prime=0}^{1} \sum_{\ell=0}^{2^{a}-1} \\ && \\ && \left(\int_{2^{-a} \ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2\lfloor \ell/2 \rfloor + u - \ell))|^2 \,\mathrm{d} t \right)^{1/2} \times \\ && \\ && \left( \int_{2^{-a} \ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} 2\lfloor \ell/2 \rfloor + u^\prime - \ell))|^2 \,\mathrm{d} t \right)^{1/2} \\ && \\ & & \le \max_{0 \le u,u^\prime < 2} \sum_{\ell=0}^{2^a-1} \left(\int_{2^{-a} \ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2\lfloor \ell/2 \rfloor + u - \ell))|^2 \,\mathrm{d} t \right)^{1/2} \times \\ && \\ && \left( \int_{2^{-a} \ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2\lfloor \ell/2 \rfloor + u^\prime - \ell))|^2 \,\mathrm{d} t \right)^{1/2} \\ && \\ & & = \max_{0 \le u \textless 2} \sum_{\ell=0}^{2^a-1} \int_{2^{-a}\ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2 \lfloor \ell/2\rfloor + u - \ell))|^2 \,\mathrm{d} t, \end{array}$

where the last inequality follows as the Cauchy-Schwarz inequality is an equality for two vectors which are linearly dependent. Let $u^\ast$ be the value of $0 \le u \textless 2$ for which the last term takes on its maximum, then

$\displaystyle \begin{array}{rcl} && \sum_{k=2^{a-1}}^{2^a-1} |\widehat{f}(k)|^2 \\ && \\ & \le & \sum_{\ell=0}^{2^a-1} \int_{2^{-a}\ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2 \lfloor \ell/2\rfloor + u^\ast - \ell))|^2 \,\mathrm{d} t \\ && \\ & = & \sum_{\ell^{\prime\prime}=0, \ell^{\prime\prime} \neq u^\ast}^{1} \sum_{\ell^\prime =0}^{2^{a-1}-1} \int_{2^{-a}(\ell^\prime 2 + \ell^{\prime\prime})}^{2^{-a}(\ell^{\prime} 2 + \ell^{\prime\prime} +1)} |f(t) - f(t+2^{-a} (u^\ast - \ell^{\prime\prime}))|^2 \,\mathrm{d} t \\ && \\ & \le & \max_{0 \le v \textless 2} \sum_{\ell^\prime=0}^{2^{a-1}-1} \int_{2^{-a}\ell^{\prime} 2}^{2^{-a}(\ell^{\prime} 2 +1)} |f(t + 2^{-a} v) - f(t+ 2^{-a} u^\ast)|^2 \,\mathrm{d} t \\ && \\ & \le & \sum_{\ell^\prime=0}^{2^{a-1}-1} \int_{2^{-a}\ell^{\prime} 2}^{2^{-a}(\ell^{\prime} 2 +1)} |f(t) - f(t+ 2^{-a})|^2 \,\mathrm{d} t \\ && \\ & \le & \sum_{\ell^\prime=0}^{2^{a-1}-1} 2^{-a} \sup_{t \in [2^{-a} \ell^\prime 2, 2^{-a} (\ell^\prime 2 + 1))} |f(t) - f(t+ 2^{-a})|^2 \\ && \\ & \le & 2^{-2 \alpha a} \sum_{\ell^\prime=0}^{2^{a-1}-1} 2^{-a} \sup_{t \in [2^{-a} \ell^\prime 2, 2^{-a} (\ell^\prime 2 + 1))} \left(\frac{|f(t) - f(t+ 2^{-a})|}{2^{-\alpha a}} \right)^2 \\ && \\ & \le & 2^{-2\alpha a} \sup_{0=x_0 \textless x_1 \textless \cdots \textless x_{N-1} \textless x_N =1} \sum_{n=1}^{N} |x_n-x_{n-1}| \left(\frac{|f(x_{n}) - f(x_{n-1})|}{|x_n-x_{n-1}|^\alpha}\right)^2 \\ && \\ & \le & 2^{-2\alpha a} V_\alpha^2(f). \end{array}$

$\Box$

Remark
The above also implies that

$\displaystyle \begin{array}{rcl} && \sum_{k=2^{a-1}}^{2^a-1} |\widehat{f}(k)|^2 \\ && \\ & \le & \sum_{\ell=0}^{2^a-1} \int_{2^{-a}\ell}^{2^{-a}(\ell+1)} |f(t) - f(t+2^{-a} (2 \lfloor \ell/2\rfloor + u^\ast - \ell))|^2 \,\mathrm{d} t \\ && \\ & = & \sum_{\ell^{\prime\prime}=0, \ell^{\prime\prime} \neq u^\ast}^{1} \sum_{\ell^\prime =0}^{2^{a-1}-1} \int_{2^{-a}(\ell^\prime 2 + \ell^{\prime\prime})}^{2^{-a}(\ell^{\prime} 2 + \ell^{\prime\prime} +1)} |f(t) - f(t+2^{-a} (u^\ast - \ell^{\prime\prime}))|^2 \,\mathrm{d} t \\ && \\ & \le & \max_{0 \le v \textless 2} \sum_{\ell^\prime=0}^{2^{a-1}-1} \int_{2^{-a}\ell^{\prime} 2}^{2^{-a}(\ell^{\prime} 2 +1)} |f(t + 2^{-a} v) - f(t+ 2^{-a} u^\ast)|^2 \,\mathrm{d} t \\ && \\ & \le & \sup_{0 \le h \le 2^{-a}} \int_0^{1-h} |f(t) - f(t+h)|^2 \,\mathrm{d} t, \end{array}$

where the last expression is just the modulus of continuity.

The Lemma above can also be generalized to arbitrary bases $b \ge 2$ and dimensions $s \ge 1.$ This result can be found in the book J.D. and F. Pillichshammer, Digital Nets and Sequences. Cambridge University Press, Cambridge, 2010, in Chapter 13.

Pointwise convergence of Walsh series

For functions ${}f$ for which $V_\alpha(f) \textless \infty$ for some $1/2 \textless \alpha \le 1$ we obtain pointwise convergence of the Walsh series. For some background information on pointwise convergence see here.

Theorem
Let $f:[0,1]\to\mathbb{R}$ be integrable and such that $V_\alpha(f) \textless \infty$ for some $1/2 \textless \alpha \le 1.$ Then

$\displaystyle \sum_{k=0}^\infty |\widehat{f}(k)| \textless \infty$

and the Walsh series

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

converges pointwise.

Proof

Since $|{\rm wal}_k(x)| \le 1,$ we have

$\displaystyle \left| \sum_{k=0}^\infty \widehat{f}(k) {\rm wal}_k(x) \right| \le \sum_{k=0}^\infty |\widehat{f}(k)| \le |\widehat{f}(0)| + \sum_{a=0}^\infty \sum_{k=2^{a-1}}^{2^a-1} |\widehat{f}(k)|.$

Hence $\sum_{k=0}^\infty |\widehat{f}(k)| \textless \infty$ implies the pointwise convergence of the Walsh series. It remains to show that $\sum_{k=0}^\infty |\widehat{f}(k)| \textless \infty.$

Since ${}f$ is integrable we have $|\widehat{f}(0)| \textless \infty.$ Further, using the Cauchy Schwarz inequality, we obtain

$\displaystyle \sum_{k=2^{a-1}}^{2^a-1} |\widehat{f}(k)| \le \left(\sum_{k=2^{a-1}}^{2^a-1} 1\right)^{1/2} \left(\sum_{k=2^{a-1}}^{2^a-1} |\widehat{f}(k)|^2 \right)^{1/2} \le 2^{(a-1)/2} \sigma_a(f).$

Therefore

$\displaystyle \left|\sum_{k=1}^\infty \widehat{f}(k) {\rm wal}_k(x) \right| \le \sum_{a=0}^\infty 2^{(a-1)/2} \sigma_a(f) \le 2^{-1/2} \sum_{a=0}^\infty 2^{(1/2 - \alpha) a} \textless \infty,$

since $1/2-\alpha \textless 0$ and therefore $\sum_{a=0}^\infty 2^{(1/2-\alpha) a} = \frac{1}{1-2^{1/2-\alpha}} \textless \infty.$ $\Box$

Pointwise convergence of the Walsh series to the function

Now we consider in which situations the Walsh series of a function ${}f$ converges to the function ${}f$ at every point. We have the following result.

Theorem
Let $f:[0,1]\to\mathbb{R}$ be continuous. Assume that $\sum_{k=0}^\infty |\widehat{f}(k)| \textless \infty.$ Then the Walsh series of ${}f$ converges to ${}f$ at every point $x \in [0,1),$ that is, we have

$\displaystyle f(x) = \sum_{k=0}^\infty \widehat{f}(k) {\rm wal}_k(x) \quad \mbox{for all } x \in [0,1).$

Proof
Let $x \in [0,1).$ Then for any $a\in \mathbb{N}_0$ and $x \in [2^{-a} \ell, 2^{-a} (\ell+1))$ we have

$\displaystyle \sum_{k=0}^{2^a-1} \widehat{f}(k) {\rm wal}_k(x) = \int_0^1 f(t) \sum_{k=0}^{2^a-1} {\rm wal}_k(x \ominus t) \,\mathrm{d} t = 2^a \int_{2^{-a} \ell}^{2^{-a} (\ell+1)} f(t) \,\mathrm{d} t.$

Hence, for continuous ${}f$ we have

$\displaystyle \lim_{a\to \infty} \sum_{k=0}^{2^a-1} \widehat{f}(k) {\rm wal}_k(x) = f(x) \quad \mbox{for all } x \in [0,1).$

Let $x \in [0,1)$ be fixed. Then the partial sums $\sum_{k=0}^L \widehat{f}(k) {\rm wal}_k(x)$ form a Cauchy sequence since $\sum_{k=0}^\infty |\widehat{f}(k)| \textless \infty$ and therefore the sums $\sum_{k=0}^L |\widehat{f}(k)|$ form a Cauchy sequence. Thus

$\displaystyle \lim_{L\to\infty } \sum_{k=0}^L \widehat{f}(k) {\rm wal}_k(x) \to f(x)$

and the result follows. $\Box$

The last two theorems imply the following result.

Corollary
Let $f:[0,1]\to\mathbb{R}$ be continuous and $V_\alpha(f) \textless \infty$ for some $1/2 \textless \alpha \le 1.$ Then

$\displaystyle f(x) = \sum_{k=0}^\infty \widehat{f}(k) {\rm wal}_k(x) \quad \mbox{for all } x \in [0,1).$