Introduction

What do I propose to show you? (Certainly not all in one post.)

My understanding is neither complete nor rigorous. But wavelets and scaling functions, and their coefficients g and h, respectively, have a lot of properties. I want to sort them out.

I’m not trying for rigor. (Heresy!) I’m laying things out on a table so I can begin to relate them to each other.

The properties which I want to show you seem to fall into 4 categories.

1. Where do the dilation equation and wavelets come from?
2. What can we deduce from the dilation equation?
3. What can we deduce from the requirement that the scaling function and its integer translates be orthogonal?
4. A few things that I really, really don’t understand yet.

There is a fair bit of repetition in here. In particular, it seemed worthwhile to repeat things within the examples.

Where do the dilation equation and wavelets come from?

Discussion

Suppose we have a function $\varphi(t)$… even more, suppose we have a collection of its “integer translates” $\{\varphi(t-k)\}\$, where k may be any integer.

That is, for example, take $\varphi(t)$ to be any of the scaling functions we have seen in the following two posts: the Haar, or the Daubechies D4 or the D6 or other scaling functions we drew here.

Define the space $V_0$ to be that space spanned by the collection of integer translates $\{\varphi(t-k)\}\$. In general, I may not be able to describe that space in any other way; whatever the $\{\varphi(t-k)\}\$ span, that is $V_0\$.

I also haven’t said that the $\{\varphi(t-k)\}\$ are linearly independent; right now, I only care what they span, not that they necessarily be a basis for it.

Now consider the collection of scaled and translated functions $\{\varphi(2t-k)\}\$, and let $V_1$ be the space they span.

For the Haar system, we know that $V_0 \subset V_1\$. Any step function with jumps at the integers may be written as a (rather special) linear combination of step functions with jumps at the half-integers.

In general, however, this is a stringent requirement. Suppose it holds, for whatever hypothetical function $\varphi(t)$ we have. That $V_0$ is a subspace of $V_1\$, with $V_1$ spanned by the set $\{\varphi(2t-k)\}\$ tells us that any function in $V_0$ may be written as a linear combination (possibly infinite!) of the $\{\varphi(2t-k)\}\$. In particular, the scaling function $\varphi(t)$ itself may be wriiten as a linear combination of the $\{\varphi(2t-k)\}\$.

But that gives us a dilation equation

$\varphi(t) = \sum_{n} c(n)\ \varphi(2t-n)\$

for some coefficients c(n). Conversely, if $\varphi(t)$ satisfies the dilation equation, then I guess we ought to have $V_0 \subset V_1\$.

The dilation equation effectively comes from the requirement that $V_0 \subset V_1\$.

Now we add a little more structure, an inner product.

If $V_0$ is a proper subspace of $V_1\$, and if we introduce an inner product, then we may split $V_1$ into $V_0$ and its orthogonal complement; that is, we define the orthogonal complement $W_0$ as:

$V_1 = V_0\ \oplus W_0\$.

For these purposes, the customary inner product of two functions f, g is the integral of their product:

$\int f(t) g(t) \, dt\$.

The definition of $W_0$ gives us a couple of immediate consequences. For one thing, every function $\psi \in W_0$ is orthogonal to the scaling function $\varphi(t) \in V_0\$ and is also orthogonal to every translate, $\varphi(t-k\$.)

For another thing, $W_0 \subset V_1\$, so every function $\psi \in W_0$ is also in $V_1\$, and therefore can be written in terms of the set $\{\varphi(2t-k)\}\$. That is, we have

$\psi(t) = \sum_{n} d(n)\ \varphi(2t-n)\$

for some coefficients d(n). This is how and why we could compute the mother wavelet from the scaling function! (Oh, yes, the mother wavelet is a function in $W_0\$.)

So the mother wavelet, as far as we know at this point, could be any function in $W_0\$, and it satisfies an equation like the dilation equation. Note, as we saw when we were computing, that we have $\psi$ on the LHS but $\varphi$ on the RHS.

And we continue, defining $W_1\$

$V_2 =: V_1 \oplus W_1$

and $W_j\$

$V_{j+1} =: V_j \oplus W_j\$.

Now, for example, take $V_2$ in terms of $V_1$ and $W_1$ and then write $V_1$ in terms of $V_0 \text{ and } W_0\$:

$V_2 =: V_1 \oplus W_1 = V_0 \oplus W_0 \oplus W_1\$.

More generally,

$V_{j+1} =: V_j \oplus W_j = V_0 \oplus W_0 \oplus W_1 \oplus ... \oplus W_j\$.

We can write a function in $V_{j+1}$ using a single scaling function in $V_0\$, and wavelets from the $W_0 \text{,...\ } W_j\$. (Oh, yes, the wavelets derived from the scaling function $\varphi(t) \in V_0$ are functions in the $W_j\$ spaces.)

We will see, in the example below, that it makes sense to go the other way, too. Suppose that for some reason – I’ll give you one, soon – we want our scaling function to be a step function of width 4 instead of width 1. (So I am speaking of the Haar system in particular, but it can make sense to go the other way for any wavelet system.)

Where does that live? Well, step functions of width 2 should live in $V_{-1}\$. They are related to step functions of width 1 in the same way step functions of width 1 are related to step functions of width 1/2.

So step functions of width 4 should live in $V_{-2}\$. And we should have

$V_{-1} = V_{-2} \oplus W_{-2}\$,

$V_{0} = V_{-1} \oplus W_{-1} = V_{-2} \oplus W_{-2} \oplus W_{-1}\ .$

Example: Haar

For the Haar system, here’s the scaling function $\varphi(t)$ and one possible translate, $\varphi(t+1)\$, on [-1,3]…

As I said earlier, define the space $V_0$ to be that space spanned by the collection of integer translates $\{\varphi(t-k)\}\$. We can describe $V_0\$: the space of step functions with jumps at the integers.

Now we consider the collection of scaled and translated functions $\{\varphi(2t-k)\}\$. Here’s $\varphi(2t)$ for the Haar… and for one of its translates, in this case, $\varphi(2t-1)\$.

They are nonzero only over a half-unit interval. That is significant for their inner products with themselves (their norms).

Define the space $V_1$ as that space spanned by the collection $\{\varphi(2t-k)\}\$. For the Haar system, we can describe $V_1$ as the space of step functions with jumps at the half-integers.

Note that if we add $\varphi(2t)$ and $\varphi(2t-1)\$, we get the unit step function on [0,1) — that is, we get $\varphi(t)\$:

$\varphi(t) = \varphi(2t) + \varphi(2t-1)\$.

That’s a form of the dilation equation!

(It’s not the way we’ve been writing it – we’re missing $\sqrt{2}\$ – but this is a dilation equation, and we can – and will shortly ! – insert the $\sqrt{2}\$ easily enough.)

That says that $V_0 \subset V_1\$: any piecewise step function whose jumps are at integers can be written as (an admittedly special) piecewise step function whose jumps are at half-integers.

For the Haar functions $\varphi(t)$, this is a property we observe. We generalize it and say that we want it to be a property of any scaling function; we require the space $V_0$ (spanned by $\{\varphi(t-k)\}$ ) to be a subspace of $V_1$ (spanned by $\{\varphi(2t-k)\}$):

Assume

• the set $\{\varphi(t-k)\}$ spans $V_0$ by definition of $V_0$
• the set $\{\varphi(2t-k)\}$ spans $V_1$ by definition of $V_1$
• $V_0 \subset V_1$

Then any function in $V_1$ can be written, by definition, as a linear combination of the $\varphi(2t-k)$… hence any function in $V_0 \subset V_1$ can be written as a linear combination of the $\varphi(2t-k)$… hence the particular function $\varphi(t) \in V_0$ can be written as a linear combination of the $\varphi(2t-k)$.

That is, we have a dilation equation

$\varphi(t) = \sum_{n} c(n) \varphi(2t-n)$

essentially because we require $V_0 \subset V_1$.

The D4 and D6 scaling functions are solutions to the dilation equation for particular coefficients. Maybe now is a good time to emphasize that the h’s and the scaling function $\varphi(t)$ are hidden in the mist, as it were. We can apparently write a dilation equation for any set (possibly infinite) of h’s, and we have no idea if there’s a solution at all. And if there is a solution, is it unique, is it continuous, is it differentiable, is it integrable, is it square integrable? This is why we look for properties of the h’s and the solution.

Example: Nievergelt

The text (Nievergelt, Yves. Wavelets Made Easy. Birkhäuser, 2001 (2nd printing with corrections), ISBN 0 8176 4061 4.) opens with a simple example.

We have 4 data points, and I want to illustrate these V and W spaces. The specific data is

$\{5,1,2,8\}\$.

Now imagine that instead of 4 points I have a step function f(t) defined on the quarter integers in [0,1). I have $V_0 \text{ thru } V_2\$ (integers, halves, quarters), so I write

$V_2 = V_1 \oplus W_1 = V_0 \oplus W_0 \oplus W_1\$.

It appears that I want the scaling function $\varphi(t)\$, the mother wavelet $\psi(t)\$, and two wavelets $\psi(2t)\$ and $\psi(2t-1)\$. That is, we are going to write our step function f(t) as the combination

$f(t) = a\ \varphi(t) + b\ \psi(t) + c\ \psi(2t) + d\ \psi(2t-1)\$,

where a, b, c, d are called the wavelet coefficients. They are components of a vector – in a function space – where the basis vectors are functions. (Yes, those 4 functions are a basis for $V_2\ \cap [0,1)\$.

Here’s those four functions all together.

I should probably remind us all that the Haar mother wavelet $\psi(t)$ satisfies the equation

$\psi(t) = \varphi(2t) - \varphi(2t-1)\$,

and that’s exactly how I compute it.

(“Reverse the h’s and alternate the signs.”)

Let me point out that I could also write $f(t) \in V_2\$, and I could graph the step function f(t) using these 4 basis functions (all scaling, no wavelets; all $\varphi \text{ no } \psi\$):

$f(t)=5\ \varphi (4 t)+8\ \varphi (4 t-3)+2\ \varphi (4t-2)+\varphi (4 t-1)\$.

I can write it, but it’s nowhere near as useful as the wavelet decomposition. (On the other hand, it’s probably the most convenient way to graph f(t)!) So, here’s the graph, constructed exactly that way.

Now I am going to give you Nievergelt’s wavelet decomposition. There are some awkward points, at this stage, so I’m just going to hand you the answer for now.

I should do it using an orthonormal basis; he did not. At this stage, I should compute the “wavelet coefficients” by taking dot products, and for that an orthonormal basis is extremely useful. (If the basis is not orthonormal, then we need a reciprocal basis in order to compute components using the inner product.) In practice, we would use a different algorithm, one which does not require taking inner products, hence does not require that the basis vectors be normalized.

As it happens, the scaling function and the mother wavelet are both normalized: the integrals of their squares are 1, so their norms — the square roots — are 1.

$\int \varphi(t)\ \varphi(t) \, dt\ = 1$.

$\int \psi(t)\ \psi(t) \, dt\ = 1$.

(Their areas are also 1, but that’s not what we’re computing here.)

The two daughter wavelets $\psi(2t)\$ and $\psi(2t-1)\$, however, are not normalized. It’s true that their squares, at each point, are either 1 or 0, but they are nonzero over half-intervals, so the integrals are 1/2 instead of 1. We need to multiply each of these functions by $\sqrt{2}$ to double the heights of their squares – if we want the daughter wavelets to be part of an orthonormal basis.

That is, for example,

$\int \varphi(2t)\ \varphi(2t) \, dt\ = \frac{1}{2}$.

so

$\int (\sqrt{2}\ \varphi(2t)\ ) (\sqrt{2}\ \varphi(2t)\ ) \, dt\ = 1\$.

(I told you I’d put that $\sqrt{2}$ in there. And if we wanted unit area instead of unit norm, we would have multiplied by 2, instead of by $\sqrt{2}\$. We’ll see this again.)

But I’m going to hold off on these calculations, until we’ve looked at some more properties. I simply tell you that the numerical result is that the components for this expansion are

$\{a\ ,b\ ,c\ ,d\} = \{4,-1,2,-3\}\$

… and that f(t) is

$f(t) = 4\ \varphi(t) - 1\ \psi(t) + 2\ \psi(2t) - 3\ \psi(2t-1)\$.

(That’s easy enough to check algebraically: just use the recursion equation for the $\psi \text{'s}$, and then use the dilation on the resulting $\varphi \text{'s}\$. But if you can compute all those functions, it is easier to just graph that equation and check it visually.)

Let me lead up to that in stages. Here is the least-detailed term: $f(t) \approx 4\ \varphi(t)$

It tells us that the average of the data is 4; alternatively, if we smooth the data by its average, that is what we get. Yet again, if we approximate our function $f(t) \in V_2$ by a particular function in $V_0\$, that is the approximation.

Now add the next term. If we approximate our function $f(t) \in V_2$ by our functions in $V_1 = V_0 \oplus W_0 \$, namely as

$f(t) \approx 4\ \varphi(t) - \psi(t)\$,

here’s what we get:

It can be interpreted as: the average of the first two observations is 3 and the average of the last two is 5.

Finally, our given function $f(t) \in V_2$ can be written exactly as

$f(t) = 4\ \varphi(t) - 1\ \psi(t) + 2\ \psi(2t) - 3\ \psi(2t-1)\$,

which is:

Now, one more thing. I didn’t have to replace the data by a function in $V_2\$; I could have decided that f(t) was a step function defined (that is, nonzero) on the half-open interval [1, 5) with jumps on the integers $\{1,2,3,4,5\}\$. Then my scaling function needs to be of width 4, i.e. in $V_{-2}\$, my mother wavelet is in $W_{-2}\$, and the two finest-scale wavelets are in $W_{-1}\$:

$V_{0} = V_{-2} \oplus W_{-2} \oplus W_{-1}\ .$

Let me be very clear. I could have gone so far as to replace my 4 points by the step function

$f(t)=5\ \varphi (t-1)+8\ \varphi (t-4)+2\ \varphi (t-3)+\varphi (t-2)\$.

That is, we can handle a change in scale and a shift: I can use integer times and I can even start time at t=1, if I choose. There’s no reason to use the shift, although it’s important to understand that we could; I’m going to forget the shift, and revert to just a change of scale,

$f(t)=5\ \varphi (t)+8\ \varphi (t-3)+2\ \varphi (t-2)+\varphi (t-1)\$,

i.e.

The wavelet expansion should use

$V_{0} = V_{-2} \oplus W_{-2} \oplus W_{-1}$

$f(t) = 4\ \varphi(t) - 1\ \psi(t) + 2\ \psi(2t) - 3\ \psi(2t-1)\$,

should be

$f(t) = 4\ \varphi(t/4) - 1\ \psi(t/4) + 2\ \psi(t/2) - 3\ \psi(t/2-1)\$

(with the very same coefficients, just applied to differently-scaled functions).

Here’s what it looks like:

Summary

From our chosen scaling function $\varphi(t)\$ – assuming it exists, i.e. assuming that we chose the h’s and found a scaling function as a solution of the dilation equation! – we get a nested sequence of V spaces. They are defined by integer translates and scaled versions of $\varphi(t)\$. The key requirement is that the existence of nested V spaces corresponds to a solution of the dilation equation.

By introducing an inner product (dot product), we get the W spaces, each as the orthogonal complement of a V space. In particular, since

$V_1 = V_0 \oplus W_0\$,

we have that $\psi(t) \in W_0$ is orthogonal to $\varphi(t) \in V_0\$; and since that subspace decomposition implies

$W_0 \subset V_1\$,

we have that $\psi(t)$ also satisfies something like the dilation equation.

$\psi(t) = \sum_{n} d(n)\ \varphi(2t-n)\$.

Next, I expect, we will look at what the dilation equation tells us about the h’s in it. (Or the c’s, whatever we call these coefficients and however we scale them.)

2 Responses to “Wavelet Properties: the dilation equation.”

1. theheartcollector Says:

Hello

My name is Mihai and I’m a student at the Politehnica faculty in Bucharest. I’m currently working on my graduation paper which is called “Optimization of two channel filter banks” and one of the tasks is to create the smoothest wavelet possible by computing Sobolev exponents and, unfortunately, I don’t have enough mathematical background to understand some concepts.

From what I can see here, you know mathematics way better than I do.

If you can spare some time to give some help / advice on a few issues, please give me a mail and I’ll send you a reply with the things that I do not understand. I don’t want to pollute this wonderful blog with stupid questions.

Mihai

2. rip Says:

Hi Mihai,

Sorry to take so long, but I was thinking about how to break the answer to you. You may have guessed from the passage of time since your request for personal help that my answer will be “no”.

There are a few reasons for that. The most important one is that I really don’t have time to commit to helping someone work on a project.

To come at it from another point of view, this blog is for fun; I get to do whatever I want. I am not willing to commit to any specific work even for this blog, although, in fact, I often decide that for completeness sake, there are posts which I simply have to write.

Another reason for my answer is that you really should be talking to your teachers about your work. They’re getting paid to teach you.

If you still want outside help, you should probably post your questions on some newsgroups or websites. (comp.dsp and wavelet.org come to mind.) People point out, when asked to reply via e-mail, that you really want public not private replies to your questions — so that other readers can comment on the answers. They might be wrong, they might be off-the-mark, or they might be excellent — but peer review will help you judge their value.

There is a saying that the fastest way to get an answer on USENET is not to ask a question, but to post an erroneous answer. People who will ignore the question will take the time to correct a mistaken answer.

Having said all that about working directly with you, I would welcome questions about the material on this blog. I just won’t promise to do any work on any other mathematics.