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

Advertisements

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