Wavelet Properties: the dilation equation.

May 31, 2009 — rip

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]…

haar t and trans

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

haar 2t and trans

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.

spaces grid

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.

spaces new f

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

haar V0

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:

haar W0

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:

haar W1 W2

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

spaces wide shift

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.

spaces wide no shift

The wavelet expansion should use

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

and instead of

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:

spaces wide fit

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

Posted in math time series, wavelets. Tags: , . 2 Comments »

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

  1. theheartcollector Says:
    June 1, 2009 at 2:39 pm

    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.

    Thank you for your time,
    Mihai

    Reply
  2. rip Says:
    June 6, 2009 at 9:19 pm

    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.

    Good luck on your research.

    Rip

    Reply

Leave a Reply

«

»