Wavelet Notes

B. M. Kessler, G. L. Payne, W. N. Polyzou The University of Iowa Iowa City, IA, 52242

October 27, 2004

Abstract

Notes on using wavelets in numerical calculations

file: usr/wavelets/revised-notes.tex

1 Continuous Wavelets

We begin by considering the continuous wavelet transform. The continuous wavelet transform is an alternate representation of a function, like a Fourier transform. Both continuous and discrete wavelets are built from a single function called a mother function. The notation, ψ(x), is used to denote the mother function of a wavelet.

Wavelets are built from translations and scale transformations of the mother function. Translations and scale transformations of ψ(x) are defined by:

ψ_{t,s}(x) := |s|^{−p}ψ(\frac{x − t}{s}).  (1)

The factor p is a parameter. The functions ψ_{t,s}(x) are the wavelets associated with the mother function ψ(x). The wavelet ψ_{t,s}(x) has two continuous parameters. We investigate conditions on the mother function that allow one to expand any function in terms of wavelets.

To choose the parameter p note that

∫_{−∞}^{∞} ||s|^{−p}ψ(\frac{x − t}{s})|^{q} dx =

|s|^{1−qp} ∫_{−∞}^{∞} |ψ(u)|^{q}du.  (2)

It follows that if p = 1/q the L^{q}-norm of ψ

∥ψ∥_{q} := (∫_{−∞}^{∞} |ψ(u)|^{q}du)^{1/q}  (3)

is preserved under scale transformations. Thus for p = 1/q:

∥ψ∥_{q} = ∥ψ_{s,t}∥_{q}  for all s, t.  (4)

The continuous wavelet transform of f is defined by taking the scalar product of f with the wavelet ψ_{s,t}:

f̂(s, t) := ∫_{−∞}^{∞} ψ_{s,t}^{∗}(x)f(x)dx = (ψ_{s,t}, f)  (5)

where asterik ′∗′ indicates the complex conjugate for a complex mother function. In what follows a f̂ is used to indicate the wavelet transform of the function f.

Parseval’s identity for the Fourier transform implies that the wavelet transform can be expressed in terms of the original function and the mother function or alternatively in terms of their Fourier transforms:

f̂(s, t) = (ψ_{s,t}, f) = (ψ̃_{s,t}, f̃)  (6)

where the ∼ indicates the Fourier transform defined by:

ψ̃_{s,t}(k) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−ikx}ψ_{s,t}(x)dx  (7)

f̃(k) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−ikx}f(x)dx.  (8)

Note that Parseval’s identity states (f, f) = (f̃, f̃). Using this with f = g + h and f = g + ih gives

(g, g) + (h, h) + (g, h) + (h, g) = (g̃, g̃) + (h̃, h̃) + (g̃, h̃) + (h̃, g̃) (9)

and

(g, g) + (h, h) + i(g, h) − i(h, g) = (g̃, g̃) + (h̃, h̃) + i(g̃, h̃) − i(h̃, g̃) (10)

which, using the identities (g, g) = (g̃, g̃) and (h, h) = (h̃, h̃), gives the solution to (??) and (??):

(g, h) = (g̃, h̃)  (11)

which is the form of Parseval’s identity used in (??).

The Fourier transform of the wavelet ψ_{s,t}(x) can be expressed in terms of the Fourier transform of the mother function:

ψ̃_{s,t}(k) := \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−ikx}|s|^{−p}ψ(\frac{x − t}{s})dx =

\frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−iksu}e^{−ikt}|s|^{−p+1}ψ(u)du =

|s|^{1−p}e^{−ikt}ψ̃(sk).  (12)

The inner product of the Fourier transforms gives

f̂(s, t) = (ψ̃_{s,t}, f̃) =
∫_{−∞}^{∞} ψ̃_{s,t}^{∗}(k)f̃(k)dk
∫_{−∞}^{∞} |s|^{1−p}e^{ikt}ψ̃^{∗}(sk)f̃(k)dk.  (13)

Multiplying both sides of (??) by e^{−ik′t} and integrating over t gives

\frac{1}{2π} ∫_{−∞}^{∞} e^{−ik′t}(ψ̃_{s,t}, f̃)dt =

|s|^{1−p}ψ̃^{∗}(sk′)f̃(k′),  (14)

where the representation of the delta function:

\frac{1}{2π} ∫_{−∞}^{∞} e^{−i(k′−k)t}dt = δ(k′ − k).  (15)

was used to get (??).

The right-hand side of (??) is a product of the Fourier transform of the original function with another function. We can’t divide by the function ψ̃^{∗}(sk′) because it might be zero for some values of k′. Instead, the trick is to eliminate it using the variable s.

Multiply both sides of this equation by ψ̃(sk′) and a yet to be determined weight function w(s) and integrate over s. This gives

\frac{1}{2π} ∫_{−∞}^{∞} w(s)ds ∫_{−∞}^{∞} dte^{−ik′t}ψ̃(sk′)f̂(s, t) =

f̃(k′) ∫_{−∞}^{∞} w(s)ds|s|^{1−p}ψ̃^{∗}(sk′)ψ̃(sk′) = f̃(k′)Y (k′)  (16)

where

Y (k′) = ∫_{−∞}^{∞} dsw(s)|s|^{1−p}|ψ̃(sk′)|^{2}.  (17)

In order to be able to extract the Fourier transform of the original function, it is sufficient that Y (k′) satisfies 0 < A ≤ Y (k′) ≤ B < ∞ for some numbers A and B. In this case

f̃(k) = \frac{1}{2πY (k)} ∫_{0}^{∞} w(s)ds ∫_{−∞}^{∞} dte^{−ikt}ψ̃(sk)f̂(s, t).  (18)

It is convenient to rewrite this in terms of the wavelet basis:

f̃(k) = \frac{1}{2πY (k)} ∫_{−∞}^{∞} w(s)|s|^{p−1}ds ∫_{−∞}^{∞} dtψ̃_{s,t}(k)f̂(s, t).  (19)

We define the dual wavelet by

ψ̃^{s,t}(k) = \frac{1}{2πY (k)}ψ̃_{s,t}(k).  (20)

The dual wavelet is distinguished from the ordinary wavelet by having the parameters s, t appearing as superscripts rather than subscripts.

The inversion formula can be expressed in terms of the dual wavelet by

f̃(k) = ∫_{−∞}^{∞} w(s)|s|^{p−1}ds ∫_{−∞}^{∞} dtψ̃^{s,t}(k)f̂(s, t).  (21)

In order to recover the original function, take the inverse Fourier transform of this expressions:

f(x) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} dke^{ikx}f̃(k) =

∫_{−∞}^{∞} w(s)|s|^{p−1}ds ∫_{−∞}^{∞} dtψ^{s,t}(x)f̂(s, t)  (22)

where

ψ^{s,t}(x) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} dke^{ikx}ψ̃^{s,t}(k).  (23)

In general this is a tedious procedure because the dual wavelet ψ^{s,t}(x) must be computed using (??) and (??) for each value of s and t. If the dual wavelet also had a mother function, then it would only be necessary to Fourier transform the “dual mother” and then all of the other Fourier transforms could be expressed in terms of the transform of the “dual mother”.

The first step in constructing a “dual mother” is to investigate the structure of the dual wavelets in x-space:

ψ^{s,t}(x) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} dke^{ikx}ψ̃^{s,t}(k) =

\frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} dke^{ikx} \frac{1}{2πY (k)}|s|^{1−p}e^{−ikt}ψ̃(sk) =

ψ^{s,0}(x − t)

where

ψ^{s,0}(x) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} dke^{ikx} \frac{1}{2πY (k)}|s|^{1−p}ψ̃(sk).

This shows for a single scale the dual wavelet and its translation can be expressed in terms of a single function. This is not necessarily true for the dual wavelet and the scaled quantity.

ψ^{s,0}(x) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} dke^{ikx} \frac{1}{2πY (k)}|s|^{1−p}ψ̃(sk)

= \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} due^{iu \frac{x}{s}} \frac{1}{2πY (u/s)}|s|^{−p}ψ̃(u).

This fails to be a rescaling of a single function because of the s dependence in the quantity Y (u). It follows that if a weight function w(s) is chosen so Y (u/s) = Y is constant, the dual wavelet will satisfy

ψ^{s,0}(x) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} due^{iu \frac{x}{s}} \frac{1}{2πY} |s|^{−p}ψ̃(u) = |s|^{−p}ψ^{1,0}(x/s).  (24)

In this case Y (u) is a constant which we denote by Y. The function ψ^{1,0}(x) serves as the dual mother wavelet.

To determine w(s) note that

Y (sk) = ∫_{−∞}^{∞} dtw(t)|t|^{1−p}|ψ̃(tsk)|^{2}.

Let t′ = st to get

Y (sk) = ∫_{−∞}^{∞} dtw(t)|t|^{1−p}|ψ̃(tsk)|^{2} =

|s|^{p−2} ∫_{−∞}^{∞} dt′w(t′/s)|t|^{′1−p}|ψ̃(t′k)|^{2}.

This will equal Y (k) provided

w(t′) = |s|^{p−2}w(t′/s) or w(s) = |s|^{p−2}w(1).

With this choice

Y (k) = Y = w(1) ∫_{−∞}^{∞} \frac{dt}{|t|}|ψ̃(t)|^{2}.

Assuming this choice of weight the admissibility condition becomes

0 < A ≤ Y ≤ B < ∞.

Having computed the constant Y it is now possible to write down an explicit expression for the dual mother wavelet:

ψ^{s,0}(x − t) =

\frac{|s|^{−p}}{\sqrt{2π}} ∫_{−∞}^{∞} due^{iu \frac{(x−t)}{s}} \frac{1}{2πY} ψ̃(u)

Letting k = u/s

\frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} dk \frac{1}{2πY} |s|^{1−p}e^{ik(x−t)}ψ̃(ks)

\frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} dk \frac{1}{2πY} e^{ikx}ψ̃_{s,t}(k).

This has the form

ψ^{s,t}(x) = \frac{1}{2π} \frac{1}{Y} ψ_{s,t}(x).  (25)

Thus the inversion procedure can be summarized by the formulas:

f(x) = ∫_{−∞}^{∞} |s|^{2p−3}ds ∫_{−∞}^{∞} dtψ^{s,t}(x)f̂(s, t)  (26)
Y = ∫_{−∞}^{∞} \frac{dt}{|t|}|ψ̃(t)|^{2}  (27)
ψ^{s,t}(x) = \frac{ψ_{s,t}(x)}{2πY}  (28)
ψ_{s,t} = |s|^{−p}ψ(\frac{x − t}{s}).  (29)

The mother function must satisfy 0 < Y < ∞. This requires that the Fourier transform of the mother function vanishes at the origin. This is equivalent to saying that the integral of the mother function is zero.

Using the representation for the wavelet transform gives a representation of a delta function:

δ(x − y) =

∫_{−∞}^{∞} |s|^{2p−3}ds ∫_{−∞}^{∞} dtψ^{s,t}(x)ψ_{s,t}^{∗}(y) =

\frac{1}{2πY} ∫_{−∞}^{∞} |s|^{2p−3}ds ∫_{−∞}^{∞} dtψ_{s,t}(x)ψ_{s,t}^{∗}(y).

We can also use this representation of the delta function to formulate a Parseval’s identity for continuous wavelets

(f, f) = \frac{1}{2πY} ∫_{−∞}^{∞} |s|^{2p−3}ds ∫_{−∞}^{∞} dt|f̂(s, t)|^{2}.  (30)

Consider the example of the Mexican hat wavelet. The mother function is

ψ(x) = \frac{1}{\sqrt{2π}} (x^{2} − 1)e^{−x^{2}/2}.

To work with the Mexican hat mother function it is useful to use properties of Gaussian integrals:

∫_{−∞}^{∞} e^{−ax^{2}+bx+c}dx =
∫_{−∞}^{∞} e^{−a(x− \frac{b}{2a})^{2}+ \frac{b^{2}}{4a} +c}dx.

Change variables to y = \sqrt{a}(x − \frac{b}{2a}) to obtain:

\frac{e^{\frac{b^{2}}{4a} +c}}{\sqrt{a}} ∫_{−∞}^{∞} e^{−y^{2}}dy =

\sqrt{\frac{π}{a}} e^{\frac{b^{2}}{4a} +c}.

This can be used to compute the Fourier transform of the Mexican hat mother function:

ψ̃(k) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−ikx}ψ(x)dx =

\frac{1}{2π} ∫_{−∞}^{∞}(x^{2} − 1)e^{−x^{2}/2−ikx}dx.

To do the integral insert a parameter a which will be set to 1 at the end of the calculation:

(−2\frac{d}{da} − 1)\frac{1}{2π} ∫_{−∞}^{∞} e^{−x^{2}a/2−ikx}dx =

(−2\frac{d}{da} − 1)\frac{1}{2π} \sqrt{\frac{2π}{a}} e^{− \frac{k^{2}}{2a}} =

(\frac{1}{a} − \frac{k^{2}}{a^{2}} − 1)\sqrt{\frac{1}{2πa}}e^{− \frac{k^{2}}{2a}} .

In the limit that a → 1 this becomes

−\sqrt{\frac{1}{2π}} k^{2}e^{− \frac{k^{2}}{2}} .

Using this expression it is possible to calculate the coefficient Y

Y = ∫_{−∞}^{∞} \frac{dk}{|k|}|ψ̃(k)|^{2} =

∫_{−∞}^{∞} \frac{dk}{|k|}|ψ̃(k)|^{2} =

\frac{1}{2π} ∫_{−∞}^{∞} |k|^{3}dke^{−k^{2}} =

\frac{1}{π} ∫_{0}^{∞} k^{3}dke^{−k^{2}}.

Inserting a parameter a which will eventually be set to 1 gives

Y = \frac{1}{2π} (−\frac{d}{da}) ∫_{0}^{∞} 2kdke^{−ak^{2}} =

\frac{1}{2π} (−\frac{d}{da})\frac{1}{a} ∫_{0}^{∞} dve^{−v} =

\frac{1}{2π} .

This satisfies the essential inequality 0 < Y < ∞ which ensures the admissibility of the Mexican hat mother function.

The expression for the wavelet transform and its inverse can be written as:

f̂(s, t) = |s|^{−p} ∫_{−∞}^{∞} dx\frac{1}{\sqrt{2π}} ((\frac{x − t}{s})^{2} − 1)e^{−( \frac{x−t}{s})^{2}/2}f(x) =

|s|^{1−p} ∫_{−∞}^{∞} du\frac{1}{\sqrt{2π}} (u^{2} − 1)e^{−u^{2}/2}f(su + t).

where x = su + t The inverse is formally given by

f(x) = ∫_{−∞}^{∞} |s|^{2p−3}ds ∫_{−∞}^{∞} dt\frac{ψ_{st}(x)}{2πY}f̂(s, t) =

∫_{−∞}^{∞} |s|^{2p−3}ds ∫_{−∞}^{∞} dt\frac{1}{\sqrt{2π}} |s|^{−p}((\frac{x − t}{s})^{2} − 1)e^{−( \frac{x−t}{s})^{2}/2}f̂(s, t) =

\frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} |s|^{p−3}ds ∫_{−∞}^{∞} dt((\frac{x − t}{s})^{2} − 1)e^{−( \frac{x−t}{s})^{2}/2}f̂(s, t) =

\frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} |s|^{p−3}ds ∫_{−∞}^{∞} du(u^{2} − 1)e^{−u^{2}/2}f̂(s, su + x)

where t = su + x.

Initially we were concerned because we were representing an arbitrary function by a linear superposition of functions that all have zero integral. We could not understand how wavelets could be used to represent a function with non-zero integral.

We tested this by computing the wavelet transform and its inverse for a Gaussian function with the Mexican hat wavelet. The original Gaussian function was recovered.

The resolution of this paradox has to do with the difference between L^{1} and L^{2} convergence. The wavelet transform has a vanishing L^{1} norm, but the L^{2} norm is non-zero.

2 Haar Scaling Functions and Wavelets

Scaling functions play a central role in the construction of orthonormal bases of compactly supported wavelets. The concept of scaling functions is most easily understood using Haar wavelets (these are made out of simple box functions). These are the simplest compactly of supported wavelets.

The Haar scaling function is defined by

ϕ(x) = \{ \begin{matrix}0 & x ≤ 0 \\ 1 & 0 < x ≤ 1 \\ 0 & x > 1 \end{matrix} .  (31)

Note that it is normalized so

(ϕ, ϕ) := ∫_{−∞}^{∞} ϕ^{∗}(x)ϕ(x)dx = ∫_{0}^{1} ϕ(x)dx = 1.  (32)

The operations of discrete translation and dilatation are used extensively in the study of compactly supported wavelets. Define the unit translation operator T by

(T χ)(x) = χ(x − 1).  (33)

This operator moves χ(x) to the right by one unit. The unit translation operator has the property:

(T ψ, T χ) = ∫_{−∞}^{∞} ψ^{∗}(x − 1)χ(x − 1)dx =  (34)

changing variables to y = x − 1 gives:

∫_{−∞}^{∞} ψ^{∗}(y)χ(y)dy = (ψ, χ)  (35)

or

(T ψ, T χ) = (ψ, χ).  (36)

If A is a linear operator its adjoint A^{†} is defined by the relation

(ψ, A^{†}χ) = (Aψ, χ).  (37)

It follows that

(ψ, T^{†}χ) = (T ψ, χ) = ∫_{−∞}^{∞} ψ^{∗}(x − 1)χ(x)dx.  (38)

Changing variables to y = x − 1 gives

(ψ, T^{†}χ) = ∫_{−∞}^{∞} ψ^{∗}(y)χ(y + 1)dy  (39)

or

(T^{†}χ)(x) = χ(x + 1)  (40)

which is a felt shift by one unit. Since

(ψ, χ) = (T ψ, T χ) = (ψ, T^{†}T χ)  (41)

it follows that T^{†} = T^{−1}. An operator whose adjoint is its inverse is called unitary. Unitary operators preserve inner products.

It follows from the definition of the Haar scaling function ϕ(x) that

(T^{m}ϕ, T^{n}ϕ) = (ϕ, T^{n−m}ϕ) = ∫_{−∞}^{∞} ϕ^{∗}(x)ϕ(x − n + m)dx =

∫_{0}^{1} ϕ(x − n + m)dx = δ_{nm}  (42)

This means the functions

ϕ_{m}(x) := (T^{n}ϕ)(x) = ϕ(x − n)  (43)

are orthonormal. There are an infinite number of these functions as n : −∞ → ∞ in integer steps.

Define V_{0} to be the subspace of the space of square integrable functions of the form

f(x) = ∑_{n=−∞}^{∞} f_{n}ϕ_{n}(x) = ∑_{n=−∞}^{∞} f_{n}(T^{n}ϕ)(x)  (44)

where the square integrability requires that the coefficients satisfy

∑_{n=−∞}^{∞} |f_{n}|^{2} < ∞.  (45)

For the Haar scaling functions V_{0} is the space of square integrable functions that are piecewise constant on each unit interval. Note that while there are an infinite number of functions in V_{0}, it is a small subspace of the space of square integrable functions.

In addition to translations, define the linear operator D corresponding to discrete scale transformations:

(Dχ)(x) = \frac{1}{\sqrt{2}}χ(x/2).  (46)

When this is applied to the Haar scaling function it gives

(Dϕ)(x) = \{ \begin{matrix}0 & x ≤ 0 \\ \frac{1}{\sqrt{2}} & 0 < x ≤ 2 \\ 0 & x > 2 \end{matrix}  (47)

This function has the same box structure, except it is twice as wide as the original scaling function and shorter by a factor of \sqrt{2}. Note that the normalization ensures

(Dψ, Dχ) = ∫_{−∞}^{∞} \frac{1}{2}ψ^{∗}(x/2)χ(x/2)dx  (48)

setting y = x/2,

= ∫_{−∞}^{∞} ψ^{∗}(y)χ(y)dy = (ψ, χ)  (49)

or

(Dψ, Dχ) = (ψ, χ).  (50)

To compute the adjoint of D note that

(ψ, D^{†}χ) = (Dψ, χ) = ∫_{−∞}^{∞} \frac{1}{\sqrt{2}}ψ^{∗}(x/2)χ(x)dx.  (51)

Setting y = x/2

∫_{−∞}^{∞} ψ^{∗}(y)\sqrt{2}χ(2y)dy  (52)

implies that

(D^{†}χ)(x) = \sqrt{2}χ(2x).  (53)

This shows that D^{†} = D^{−1} or D also unitary.

Define the functions

ϕ_{mn}(x) = (D^{m}ϕ_{n})(x) = 2^{−m/2}ϕ(2^{−m}x − n) = 2^{−m/2}ϕ(2^{−m}(x − 2^{m}n)). (54)

where the left index indicates the scale and the right index indicates the number of integer translations. It follows that for fixed m

(ϕ_{mn}, ϕ_{mk}) = (D^{m}ϕ_{n}, D^{m}ϕ_{k}) = (ϕ_{n}, D^{m−m}ϕ_{k}) = (ϕ_{n}, ϕ_{k}) = δ_{nk}  (55)

This shows that the functions ϕ_{mn}(x) for fixed m are orthonormal. We define the subspace V_{m} of the square integrable functions to be those functions of the form:

f(x) = ∑_{n=−∞}^{∞} f_{n}ϕ_{mn}(x) = ∑_{n=−∞}^{∞} f_{n}(D^{m}T^{n}ϕ)(x)  (56)

where the square integrability requires that the coefficients satisfy

∑_{n=−∞}^{∞} |f_{n}|^{2} < ∞.  (57)

These functions are square summable functions that are piecewise constant on intervals of width 2^{m}.

In general the scaling function ϕ(x) is defined as the solution of a scaling equation subject to a normalization condition. The scaling equation relates the scaled scaling function, (Dϕ)(x), to translates of the original scaling function. The general form of the scaling equation is

(Dϕ)(x) = ∑ h_{l}T^{l}ϕ(x)  (58)

where h_{l} are fixed constants, and the sum may be finite or infinite.

In general this equation cannot be solved analytically. In the Haar case we can write down the solution realizing that the scaled box is stretched over two adjacent boxes with a suitable reduction in height. It follows that:

Dϕ(x) = \frac{1}{\sqrt{2}}ϕ(x/2) = \frac{1}{\sqrt{2}}ϕ(x) + \frac{1}{\sqrt{2}}T ϕ(x) =

\frac{1}{\sqrt{2}}ϕ(x) + \frac{1}{\sqrt{2}}ϕ(x − 1).  (59)

Here h_{0} = h_{1} = 1/\sqrt{2}. These coefficients are special to the Haar scaling function. The best way to think of this is that the scaling function ϕ(x) is the solution of the scaling equation up to normalization. The normalization is fixed by

∫ ϕ(x)dx = 1.

To proceed a few additional relations are useful for future computations. First note

DT ψ(x) = Dψ(x − 1) = \frac{1}{\sqrt{2}}ψ(x/2 − 1) = \frac{1}{\sqrt{2}}ψ(\frac{x − 2}{2}) = T^{2}Dψ(x) (60)

which leads to the operator relation

DT = T^{2}D.  (61)

It follows from this equation that

Dϕ_{n}(x) = DT^{n}ϕ(x) = T^{2n}Dϕ(x) = T^{2n}(h_{0}ϕ(x) + h_{1}T ϕ(x)).  (62)

This shows that all of the basis elements in V_{1} can be expressed in terms of basis elements in V_{0}. For the Haar case this is obvious, but the argument above is more general.

Specifically if ψ(x) ∈ V_{1} then

ψ(x) = ∑_{−∞}^{∞} d_{n}ϕ_{1n}(x) =  (63)

∑_{−∞}^{∞} d_{n}Dϕ_{n}(x) = ∑_{−∞}^{∞}(d_{n}h_{0}ϕ_{2n}(x) + d_{n}h_{1}ϕ_{2n+1}(x)) =  (64)

∑_{−∞}^{∞} c_{n}ϕ_{n}(x)  (65)

where

c_{2n} = d_{n}h_{0} c_{2n+1} = d_{n}h_{1}.  (66)

It is easy to show that

∑_{−∞}^{∞} |c_{n}|^{2} = ∑_{−∞}^{∞} |d_{n}|^{2}.  (67)

What we have shown, as a consequence of the scaling equation, is the inclusion

V_{0} ⊃ V_{1}.  (68)

Similarly, it is not difficult to show the inclusions

⋯ V_{−k} ⊃ V_{−k+1} ⊃ ⋯ ⊃ V_{0} ⊃ ⋯ V_{k} ⊃ V_{k+1} ⋯  (69)

In this example these are all spaces of piecewise constant, square integrable functions that are constant on segments that differ by powers of 2.

First note that as k → −∞ the approximation to f(x) given by

f_{k}(x) = ∑_{n=−∞}^{∞} f_{kn}ϕ_{kn}(x)  (70)

with

f_{kn} = ∫_{−∞}^{∞} ϕ_{kn}^{∗}(x)f(x)dx  (71)

is bounded by the upper and lower Riemann sums for steps of width 2^{−k}. This is because the coefficients f_{kn} are just average values of the function on the appropriate sub-interval (to deal with the infinite interval it is best to first consider functions that vanish outside of finite intervals and take limits).

Since the upper and lower Riemann sums converge to the same integral (when the function is integrable) it follows that

∫_{−∞}^{∞} |f_{k}(x) − f(x)|dx < ϵ  (72)

for sufficiently large −k. A related argument can be extended to get L^{2} convergence .

Similarly, as k → +∞, the width of ϕ_{kn}(x) grows like 2^{k} while the height falls off like 2^{−k/2}. Again, if the function vanishes outside of a bounded interval then for sufficiently large k there is only one (or two) ϕ_{kn}(x) that are non-vanishing where the function is non-vanishing. In the case that only one ϕ_{kl} overlaps the support of f(x)

f_{k}(x) ∼ 2^{−k/2}ϕ_{kn_{0}}(x) ∫_{−∞}^{∞} f(x)dx  (73)

The integral of the square of this function ∼ 2^{−k} → 0 as k → ∞.

Note that

∫_{−∞}^{∞} f_{k}(x)dx → ∫_{−∞}^{∞} f(x)dx  (74)

as k → ∞. This shows that this integral is finite in L^{1} but 0 in L^{2}. Define the projection operators

P_{k}f(x) = ∑_{n=−∞}^{∞} f_{kn}ϕ_{kn}(x)  (75)

where

f_{kn} = ∫_{−∞}^{∞} ϕ_{kn}^{∗}(x)f(x)dx.  (76)

The above conditions can be stated in terms of these projectors:

lim_{k→−∞} P_{k} = I  (77)
lim_{k→+∞} P_{k} = 0.  (78)

These conditions are valid for a large class of scaling functions.

We are now ready to construct wavelets. First recall the condition

V_{0} ⊃ V_{1}.  (79)

Let W_{1} be the space of vectors in the space V_{0} that are orthogonal to the vectors in V_{1}. We can write

V_{0} = V_{1} ⊕ W_{1}  (80)

This notation means that any vector in V_{0} can be expressed as a sum of two vectors - one that is in V_{1} and one that is orthogonal to every vector in V_{1}.

Note that the scaling equation implies that every vector in V_{1} can be expressed as a linear combination of vectors in V_{0} using

Dϕ_{n}(x) = h_{0}ϕ_{2n}(x) + h_{1}ϕ_{2n+1}(x)  (81)

Clearly the functions that are orthogonal to these in V_{1} on the same interval can be expressed in terms of the functions

ψ_{1n}(x) := Dψ_{n}(x) = h_{1}ϕ_{2n}(x) − h_{0}ϕ_{2n+1}(x) = \frac{1}{\sqrt{2}}(ϕ_{2n}(x) − ϕ_{2n+1}(x)) (82)

These are the elements of V_{0} that satisfy

(Dψ_{1n}, Dϕ_{l}) = 0.  (83)

Thus we have that W_{1} is the space of square integrable functions of the form

f(x) = ∑_{n=−∞}^{∞} f_{n}ψ_{1n}(x)  (84)

with

f(x) = ∑_{n=−∞}^{∞} |f_{n}|^{2}  (85)

where we have used

(ψ_{1n}, ψ_{1k}) = δ_{nk}  (86)

which follows from the definitions.

Similarly, we can decompose V_{l} = V_{l+1} ⊕ W_{l+1} for each value of l. For the special case l = −1 we define the mother wavelet as

ψ(x) := D^{−1}(h_{1}ϕ(x) − h_{0}T ϕ(x)) =  (87)
h_{1}\sqrt{2}ϕ(2t) − h_{0}\sqrt{2}ϕ(2(t − 1)) = (ϕ(2t) − ϕ(2(t − 1)))  (88)

which is manifestly orthogonal to the scaling function. Translates of this function define a basis for W_{0}

ψ_{n}(x) = T^{n}ψ(x) = T^{n}D^{−1}(h_{1}ϕ(x) − h_{0}T ϕ(x)) =  (89)
D^{−1}(h_{1}ϕ_{2n}(x) − h_{0}ϕ_{2n+1}(x)).  (90)

It is simple to show that

(ψ_{n}, ψ_{k}) = δ_{nk}  (91)

If we decompose every space we have for any k

V_{−k} = W_{−k+1} ⊕ V_{−k+1} =  (92)
W_{−k+1} ⊕ W_{−k+2} ⊕ V_{−k+2} =  (93)
W_{−k+1} ⊕ W_{−k+2} ⊕ ⋯ ⊕ W_{l} ⊕ V_{l}  (94)

Note that unlike the V spaces, the W_{k} spaces are all mutually orthogonal, since if k > l → W_{k} ⊂ V_{l} which is orthogonal to W_{l} by definition.

If f(x) is any square integrable function the conditions

lim_{k→−∞} P_{k} = I  (95)
lim_{k→+∞} P_{k} = 0  (96)

mean that for sufficiently large k and l that f(x) can be well approximated by a function in

W_{−k+1} ⊕ W_{−k+2} ⊕ ⋯ ⊕ W_{l}.  (97)

This means that the function can be approximated by a linear combination of basis functions (wavelets) from each of the spaces W_{r} .

Basis functions for W_{m} are given by

ψ_{mn}(x) = D^{m}T^{n}ψ(x) = D^{m−1}(h_{1}ϕ_{2n}(x) − h_{0}ϕ_{2n+1}(x)).  (98)

That these are a basis with the required properties is easily shown by showing that these functions are orthogonal to V_{m} and can be used to recover the remaining vectors in V_{m−1}.

The functions ψ_{nl}(x) satisfy

(ψ_{nl}, ψ_{n′l′}) = δ_{nn′}δ_{ll′}  (99)

where the δ_{nn′} follows from the orthogonality of the spaces W_{n} and W_{n′} for n ≠ n′.

The δ_{ll′} follows from the unitarity of D and

(ψ, T^{n}ψ) = δ_{n0}.  (100)

The important steps generalize to the case of a general scaling equation of the form:

Dϕ(x) = ∑ h_{l}T^{l}ϕ(x)  (101)

This equation is solved to find the scaling function ϕ(x). This, along with translations and dilatations is used to construct the spaces V_{l}. The scaling equation ensures the existence of space W_{k} that can be used to build discrete orthonormal basis. The mother wavelet is expressed in terms of the scaling function and the coefficients as

ψ(x) = D^{−1} ∑_{l} g_{l}T^{l}ϕ(x) g_{l} = (−)^{k}h_{k−l} k odd  (102)

In general the coefficients h_{l} must satisfy constraints for the solution to the scaling equation to exist. The expression for g_{l} will be derived in the next section.

3 Scaling Functions - General Considerations

In this section we give a more general treatment of scaling equations. In general the scaling function is the solution of the scaling equation

Dϕ(x) = ∑_{l} h_{l}T^{l}ϕ(x).  (103)

In addition to satisfying the scaling equations we require that integer translates of the scaling functions are orthonormal

(ϕ_{n}, ϕ_{m}) = (T^{n}ϕ, T^{m}ϕ) = (ϕ, T^{m−n}ϕ) = δ_{mn}.  (104)

The initial scale is fixed by the normalization condition

∫ ϕ(x)dx = 1.  (105)

We investigate the consequences of these three conditions.

Using the definitions of the operators D and T the scaling equation becomes:

\frac{1}{\sqrt{2}}ϕ(\frac{x}{2}) = ∑ h_{l}ϕ(x − l).  (106)

It can be put in the useful form

ϕ(x) = ∑_{l} \sqrt{2}h_{l}ϕ(2x − l).  (107)

In general the sums may be from −∞ → ∞. Finite sums are treated by assuming that only a finite number of the h_{l}’s are non zero. All of the compactly supported scaling functions are solution of scaling equations with a finite number of non-zero coefficients.

The claim is that if this equation has a solution, it is unique up to an overall normalization factor. To investigate this claim take the Fourier transform of both sides of equation (??) to get

\frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−ikx}ϕ(x)dx = ∑_{l} \sqrt{2}h_{l} \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−ikx}ϕ(2x − l)dx.  (108)

Changing variables x → 2x − l gives

\frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−ikx}ϕ(x)dx = ∑_{l} \frac{1}{\sqrt{2}}h_{l} \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−i(k/2)(x+l)}ϕ(x)dx. (109)

or

ϕ̃(k) = ϕ̃(\frac{k}{2})h̃(\frac{k}{2})  (110)

where

h̃(k) = ∑_{l} \frac{h_{l}}{\sqrt{2}}e^{−ikl}.  (111)

This form of the scaling equation can be iterated n times to get:

ϕ̃(k) = ϕ̃(\frac{k}{2^{n}}) ∏_{m=1}^{n} h̃(\frac{k}{2^{m}})  (112)

This equation holds for any n provided the Fourier transforms exist. For a finite n, an approximation can be made by a finite number of iterations of the form

ϕ̃_{n}(k) = ϕ̃_{n−1}(\frac{k}{2})h̃(\frac{k}{2})  (113)

for any starting function ϕ̃_{0}(k). In the limit of large n the function ϕ̃_{m}(k) should converge to the scaling function. It is clear that this result is approximately independent of the choice of starting function; it really depends on the coefficients h_{l}.

If the limit exists as n → ∞, and the scaling function is continuous in a neighborhood of zero, then

ϕ̃(k) = lim_{n→∞} ϕ̃(\frac{k}{2^{n}}) ∏_{l=1}^{n} h̃(\frac{k}{2^{l}}) =

ϕ̃(0) ∏_{l=1}^{∞} h̃(\frac{k}{2^{l}}).  (114)

If the infinite product converges, then we have an expression for the scaling function, up to normalization, which is fixed by assigning a value to ϕ̃(0). For the Haar wavelets this expression becomes

ϕ̃(0) ∏_{l=1}^{∞} \frac{1}{2}(1 + e^{−ik/2^{l}}) =

lim_{l→∞} ϕ̃(0)\frac{1}{2^{l}} (1 + e^{−ik/2})(1 + e^{−ik/4}) ⋯ (1 + e^{−ik/2^{l}})

expanding this out gives

ϕ̃(0) lim_{l→∞} \frac{1}{2^{l}} ∑_{m=0}^{2^{l}−1}(e^{−ik/2^{l}})^{m} =

ϕ̃(0) lim_{l→∞} \frac{1}{2^{l}} \frac{1 − e^{−ik}}{1 − e^{−ik/2^{l}}} =

ϕ̃(0)e^{−ik/2} \frac{sin(k/2)}{(k/2)}.  (115)

A direct calculation of the Fourier transform of the Haar scaling function gives

ϕ̃(k) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−ikx}ϕ(x)dx = \frac{1}{\sqrt{2π}} ∫_{0}^{1} e^{−ikx}dx =

\frac{1}{\sqrt{2π}} e^{−ik/2} \frac{sin(k/2)}{(k/2)}  (116)

which agrees with (??) if we choose the normalization ϕ̃(0) = \frac{1}{\sqrt{2π}}, which is consistent with the requirement

∫ ϕ(x)dx = 1.

The coefficients h_{l} are not arbitrary. First note that setting k = 0 in (??) gives

1 = ∏_{l=0}^{∞} h̃(0).  (117)

Using (??) gives

h̃(0) = 1 = ∑_{l} \frac{h_{l}}{\sqrt{2}}  (118)

or

∑_{l} h_{l} = \sqrt{2}.  (119)

This condition is satisfied by the Haar wavelets. This is a necessary condition on the scaling coefficients in order to have a solution to the scaling equation.

Another condition is that is needed to make a multi-resolution analysis is the orthogonality of the unit translates, (ϕ_{n}, ϕ_{m}) = δ_{nm}. This requires, using (??)

2 ∑_{lk} h_{l}^{∗}h_{k} ∫_{−∞}^{∞} ϕ^{∗}(2x − 2n − l)ϕ(2x − 2m − k)dx =

2 ∑_{lk} h_{l}^{∗}h_{k} ∫_{−∞}^{∞} ϕ^{∗}(2x)ϕ(2x − 2(m − n) − (k − l))dx =

∑_{lk} h_{l}^{∗}h_{k} ∫_{−∞}^{∞} ϕ^{∗}(x)ϕ(x − 2(m − n) − (k − l))dx

∑_{l} h_{l}^{∗}h_{l−2(m−n)} = δ_{mn}  (120)

or equivalently

∑_{l} h_{l−2m}^{∗}h_{l} = δ_{m0}.  (121)

This is trivially satisfied for the Haar wavelets.

Note that if there are only two non-vanishing scaling coefficients, h_{0} and h_{1}, then the conditions (??) and (??) have a unique solution, which is the Haar scaling coefficients.

To see this first note conditions on the coefficients are

h_{0} + h_{1} = \sqrt{2}  (122)
h_{0}h_{0}^{∗} + h_{1}h_{1}^{∗} = 1.  (123)

These equations have the unique real solution h_{0} = h_{1} = \frac{1}{\sqrt{2}} To see this write h_{k} = h_{kr} + ih_{ki} for real h_{kr} and h_{ki}. Inserting these in the equations gives

h_{0r} + h_{1r} = \sqrt{2}  (124)
h_{0i} + h_{1i} = 0  (125)
h_{0r}h_{0r} + h_{0i}h_{0i} + h_{1r}h_{1r} + h_{1i}h_{1i} = 1.  (126)

Note that since

∑_{m} h_{n+2m} = ∑_{m} h_{n+2m+2k}  (127)

the m sum has two values according to whether n is even or odd:

h_{e} := ∑_{m} h_{2m} h_{o} := ∑_{m} h_{2m+1}.  (128)

This means that

∑_{m,n} h_{n}^{∗}h_{n+2m} = ∑_{m} δ_{m0} = 1 =

h_{e} ∑_{n} h_{2n}^{∗} + h_{o} ∑_{n} h_{2n+1}^{∗} = 1  (129)

or

h_{e}^{∗}h_{e} + h_{o}^{∗}h_{o} = 1.  (130)

We also have

h_{e} + h_{o} = \sqrt{2}  (131)

Assuming that the coefficients h_{l} are real these can be solved to get

h_{e} = h_{o} = \frac{1}{\sqrt{2}},  (132)

which are precisely the scaling coefficient for the Haar wavelets.

These condition are useful checks and uniquely determine the Haar coefficients; but the essential equations are (??) and (??).

For scaling equations with more than two non-zero coefficients, additional conditions are needed to determine the scaling coefficients. In all cases considered in these notes the solutions of the equations for the scaling coefficients are real.

The other conditions that require some study are the ones relating the scaling function to the mother function. The mother function lives in the space W_{0} which means that it has an expansion in V_{−1}.

ψ(x) = ∑_{n} \sqrt{2}g_{n}ϕ(2x − n).  (133)

This and all of its translates should be orthogonal to the scaling function, which is in V_{0}. In terms of the coefficients this requirements is:

(ψ_{m}, ϕ) = ∑_{n,l} h_{l}g_{n}(ϕ_{n−2m}, ϕ_{l})

∑_{n,l} h_{l}g_{n}δ_{n−2m,l}

∑_{n} h_{n−2m}g_{n} = 0  (134)

for all m. We restrict our considerations to the case that the coefficients g_{m} and h_{m} are real.

We also need orthonormality of the translated mother function

(ψ_{m}, ψ_{n}) = ∑_{l,k} g_{l}g_{k}(ϕ_{l−2m}, ϕ_{k−2n})

∑_{k} g_{k−2(n−m)}g_{k} = δ_{mn}  (135)

or equivalently

(ψ_{m}, ψ) = ∑_{k} g_{k+2m}g_{k} = δ_{m0}  (136)

If we choose g_{k} := (−1)^{k}h_{l−k} where l is odd it satisfies (??) and (??):

∑_{k} g_{k−2(n−m)}g_{k} = ∑_{k}(−1)^{k−2(n−m)}h_{l−k+2(n−m)}(−1)^{k}h_{l−k} =

∑_{k} h_{k−2(n−m)}h_{k} = δ_{mn}  (137)

where we have let l − k → k in the last term. It also follows that

∑_{n} h_{n−2m}g_{n} = ∑_{n} h_{n−2m}(−1)^{n}h_{l−n} =

∑_{n′} h_{l−n′}(−1)^{l−n′−2m}h_{n′−2m} = (−)^{l} ∑_{n′} h_{l−n′}(−1)^{n′}h_{n′−2m} =

(−1)^{l} ∑_{n′} g_{n′}h_{n′−2m}.  (138)

Since l is odd, the sum is equal to its negative which shows that it vanishes. The choice of l is arbitrary - it simply involves moving the origin of the mother. Since the mother is orthogonal to the translates of all of the father wavelets, it does not matter where the origin is placed.

This shows that the coefficients h_{l}, satisfying

∑_{l} h_{l} = \sqrt{2}.  (139)

∑_{l} h_{l−2m}h_{l} = δ_{m0}  (140)
g_{k} := (−1)^{k}h_{l−k}  l odd  (141)

give a multi-resolution analysis, scaling function, and a mother function.

To determine the support of the scaling function note that the scaling function is given by

ϕ(x) = \frac{ϕ̃(0)}{\sqrt{2π}} ∫_{−∞}^{∞} e^{ikx} ∏_{l=1}^{∞} h̃(\frac{k}{2^{l}})dk =

\frac{ϕ̃(0)}{\sqrt{2π}} ∫_{−∞}^{∞} e^{ikx} ∏_{l=1}^{∞} (∑_{n_{l}} \frac{h_{n_{l}}}{\sqrt{2}}e^{−ikn_{l}/2^{l}}) dk