How to prove that the Haar system is orthonormal?

Question

Haar wavelets are defined as:

$$ \psi_{0,0}(t) = \begin{cases} 1, \text{ for } 0<t< 1/2\\ -1, \text{ for } 1/2<t<1 \\ 0, \text{ otherwise } \end{cases} $$ Where mother wavelet is$$\psi_{n,k} = 2^{-n/2} \psi_{0,0}(2^n t -k).$$ And for $n \geq 0$, $0 \leq k < 2^n$ $$ {\psi_{i,n}\psi_{k,l}} = \delta_{i,l}\delta_{k,n}$$

Show that these wavelets form an orthonormal set:

Answer 1

We need to show the following $$\langle \psi_{n,k_1},\psi_{n,k_2}\rangle=0\\\langle \psi_{n_1,k},\psi_{n_2,k}\rangle=0\\\langle \psi_{n_1,k_1},\psi_{n_2,k_2}\rangle=0\\\langle \psi_{n,k},\psi_{n,k}\rangle=1$$when $n_1\ne n_2$ and $k_1\ne k_2$ and $$\langle f,g\rangle=\int_Df(x)g^*(x)dx$$

(1) for $k_1\ne k_2$

$$\langle \psi_{n,k_1},\psi_{n,k_2}\rangle{=\int_{\Bbb R}2^{-n}\psi_{0,0}(2^nx-k_1)\psi_{0,0}(2^nx-k_2)dx\\=2^{-2n}\int_{\Bbb R}\psi_{0,0}(u-k_1)\psi_{0,0}(u-k_2)du\\=2^{-2n}\int_{(k_1,k_1+1)\cap(k_2,k_2+1)}\psi_{0,0}(u-k_1)\psi_{0,0}(u-k_2)du\\=2^{-2n}\int_{\emptyset}\psi_{0,0}(u-k_1)\psi_{0,0}(u-k_2)du\\=0}$$

(2) for $n_1\ne n_2$ withput loss of generality assume $n_1>n_2$. Therefore$$\langle \psi_{n_1,k},\psi_{n_2,k}\rangle{=\int_{\Bbb R}2^{-{n_1+n_2\over 2}}\psi_{0,0}(2^{n_1}x-k)\psi_{0,0}(2^{n_2}x-k)dx\\=\int_{({k\over 2^{n_1}},{k+1\over 2^{n_1}})\cap ({k\over 2^{n_2}},{k+1\over 2^{n_2}})}2^{-{n_1+n_2\over 2}}\psi_{0,0}(2^{n_1}x-k)\psi_{0,0}(2^{n_2}x-k)dx}$$note that for $k\ne 0$ $${k+1\over 2^{n_1}}\le {k\over 2^{n_2}}$$and therefore $$({k\over 2^{n_1}},{k+1\over 2^{n_1}})\cap ({k\over 2^{n_2}},{k+1\over 2^{n_2}})= \emptyset$$This important result says that $\langle \psi_{n_1,k},\psi_{n_2,k}\rangle= 0$ whenever $k\ne 0$. In the case $k=0$ we obtain $$\langle \psi_{n_1,0},\psi_{n_2,0}\rangle{=\int_{(0,{1\over 2^{n_1}})\cap (0,{1\over 2^{n_2}})}2^{-{n_1+n_2\over 2}}\psi_{0,0}(2^{n_1}x)\psi_{0,0}(2^{n_2}x)dx\\=\int_0^{1\over 2^{n_1}}2^{-{n_1+n_2\over 2}}\psi_{0,0}(2^{n_1}x)\psi_{0,0}(2^{n_2}x)dx\\=\int_0^{1}2^{-{3n_1+n_2\over 2}}\psi_{0,0}(u)\psi_{0,0}(2^{n_2-n_1}u)du\\=\int_0^{1}2^{-{3n_1+n_2\over 2}}\psi_{0,0}(u)du=0}$$

(3)

We show that $$\int_{\Bbb R}\psi_{0,0}(2^{n_1}x-k_1)\psi_{0,0}(2^{n_2}x-k_2)dx=0$$

proof

Assume $n_2>n_1$. Therefore

$$\int_{\Bbb R}\psi_{0,0}(2^{n_1}x-k_1)\psi_{0,0}(2^{n_2}x-k_2)dx{={1\over 2^{n_1}}\int_{k_1}^{k_1+1}\psi_{0,0}(u-k_1)\psi_{0,0}(2^{n_2-n_1}u-k_2)du}\\={1\over 2^{n_1}}\int_{k_1}^{k_1+{1\over 2}}\psi_{0,0}(2^{n_2-n_1}u-k_2)du-{1\over 2^{n_1}}\int_{k_1+{1\over 2}}^{k_1+1}\psi_{0,0}(2^{n_2-n_1}u-k_2)du$$from the other side $${1\over 2^{n_1}}\int_{k_1}^{k_1+{1\over 2}}\psi_{0,0}(2^{n_2-n_1}u-k_2)du=0$$ since $${1\over 2^{n_1}}\int_{k_1}^{k_1+{1\over 2}}\psi_{0,0}(2^{n_2-n_1}u-k_2)du{={1\over 2^{n_2}}\int_{k_1\cdot 2^{n_2-n_1}}^{\left(k_1+{1\over 2}\right)\cdot 2^{n_2-n_1}}\psi_{0,0}(w-k_2)dw\\={1\over 2^{n_2}}\int_{k_1\cdot 2^{n_2-n_1}-k_2}^{\left(k_1+{1\over 2}\right)\cdot 2^{n_2-n_1}-k_2}\psi_{0,0}(w)dw\\=0}$$where the last equality comes from $$\int_0^1 \psi_{0,0}(x)dx=0$$

(4)

$$\langle \psi_{n,k},\psi_{n,k}\rangle{=\int_{\Bbb R}2^{-n}\psi_{0,0}^2(2^nx-k)dx\\=\int_{k\over 2^n}^{k+1\over 2^n}2^{-n}\psi_{0,0}^2(2^nx-k)dx\\=\int_{k\over 2^n}^{k+1\over 2^n}2^{-n}dx\\=1}$$which finishes our (long and exhaustive!) proof $\blacksquare$

Answer 2

If the supports are disjoint then of course the $L^2$ inner product is zero. If the supports overlap, the explanation for the orthogonality is as follows. A Haar wavelet has zero integral, or averages to zero. The wavelet with higher frequency (higher $n$) has support in an interval where the lower frequency wavelet is constant. So the inner product is just that constant times the spatial average of the higher frequency wavelet, i.e., zero.