Wavelet properties: consequences of the dilation equation

discussion
edited 8 Jun to cross out the last line and correct it. see edit.
edited 13 Jun to correct the last line again. see edit. Sorry about that, but I shot from the hip and hit myself in the foot.

We have seen in the previous post that the idea of a set of scaling functions \{\varphi(t-k)\} spanning a space V_0\ , and such that the set \{\varphi(2t-k)\} span a space V_1\ , gives rise to a dilation equation, which we have been writing as

\varphi(t) = \sum_n {h(n)\ \sqrt{2}\ \ \varphi(2\ t - n)}.

(We also get more spaces V_j\ for both positive and negative integers j.)

We have also seen that if we impose an inner product, then wavelets live in the orthogonal complements W_j\ :

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

I should probably remark, first, that a solution \varphi(t)\ of the dilation equation is determined only to within a constant factor. We describe that, however, by describing its integral (effectively, its average) rather than, for example, its maximum value. We write

\int\ \varphi(t)\ dt = E\ ,

where E is a nonzero constant which we often choose to be 1: E = 1.

To put that another way: if there is a solution, it is not unique.

Two examples we’ve seen repeatendly are Haar and Daubechies. The Haar scaling fuction is a unit step function on the unit interval, so its integral is 1. Similarly, the integrals of the Daubechies scaling functions are 1, although I have not shown that.

There are 3 consequences of the dilation equation (mostly with other conditions added).

The first consequence of the dilation equation is that it dictates the sum of the h’s. For the form we have usually been using, namely

\varphi(t) = \sum_n {h(n)\ \sqrt{2}\ \ \varphi(2\ t - n)}

we must have

\sum_n\ h(n) = \sqrt{2}\

More generally, for an arbitrary normalizing factor A in the dilation equation

\varphi(t) = \sum_n {h(n)\ A\ \varphi(2\ t - n)}

we get

\sum_n\ h(n) = \frac{2}{A}\

Let me remark that the sum of the h’s is independent of the integral of \varphi(t)\ , i.e. independent of E.

I should also mention that I had originally written that it was independent of the “normalization,” but I want to reserve that term for the integral of the square of \varphi(t)\ . I have found it all too easy to get confused between

\int\ \varphi(t)\ dt\

and

\int\ \varphi(t)\ \varphi(t)\ dt\ .

Further discussion and the derivation of this is at the end of the post. That will make it clear that the sum of the h’s does not depend on the value of the integral (but it does require that the integral exist and be nonzero).

The second consquence of the dilation equation, with the additional requirement that the integral E = 1,

E = \int\ \varphi(t)\ dt = 1\

is that

\sum_k { \varphi(\frac{k}{2^j})} = 2^j

for integers k and j.

Note especially the special case for j = 0,

\sum_k { \varphi(k))} = 1

That is, that the sum of the values of \varphi(t)\ at the integers is 1.

That is why Burrus et al. normalized the eigenvectors to a sum of 1, those eigenvectors that we used for the values of \varphi(t)\ at the integers, in order to initialize our recursions for computing \varphi(t)\ .

The third consequence of the dilation equation, under at least two different sets of additional assumptions which I’m skipping right over – but not an assumption that \varphi(t) is orthogonal to its integer translates – is that

the sum of the even-numbered h’s is equal to the sum of the odd-numbered h’s:

\sum_n\ h(2n) = \sum_n\ h(2n+1)\ .

This result is also implied by an orthogonality condition, but it does not require it. And this is why I state it although I’m more than a little vague – I’m not sure I could be any more vague if I tried – on the conditions it assumes: this result does not require orthogonality.

My reading suggests that this result will make a lot more sense in either the frequency domain, or from the filter-bank point of view. I suppose I should have said that what I’m doing is the “multi-resiolution analysis approach”, by focusing on the V and W spaces.

I had originally intended to list the assumptions required, until I saw a simpler but alternative set of assumptions. To heck with them all, at this stage of my learning.

At this point, I view this consequence as an interesting result to be looked for, and if it ever fails to hold, then I will investigate and see why it failed.

Anyway, there are 5 things to note or to check.

  • The sum of the h’s = 2/A.
  • The scaling factor A in the dilation equation.
  • The integral E of the scaling function (is E=1?).
  • The sum of the even h’s = the sum of the odd h’s.
  • \sum_k { \varphi(\frac{k}{2^j})} = 2^j

I did not number those because I will check them in whatever order is convenient, but I will count them as I check them.

Yes, I spoke of three consequences and then I listed five items. The extra two are the values of A and E, parameters rather than consequences.

By the way, the sum of the h’s might be a good first thing to compute, since it gives us the value of A in the dilation equation. But sometimes the dilation equation comes first; and sometimes it’s just not clear which (the h’s or the equation) comes first.

Let’s look at these.

example: Haar

We take the scaling function \varphi(t)\ to be the unit-height step function nonzero on the half-open interval [0,1).

One result, its integral is 1.

Result two, if we write the dilation equation as we have usually done it…

\varphi(t) = \sum_n {h(n)\ \sqrt{2}\ \ \varphi(2\ t - n)}

then h(0) = h(1) = \frac{1}{\sqrt{2}}\ (i.e. result three, the sum of even h’s (h(0)) is, trivially, equal to the sum of odd h’s (h(1)), and (result four) the sum of the h’s is \frac{2}{\sqrt{2}} = \sqrt{2}\ .

Five, because the integral is 1, we expect that

\sum_k { \varphi(\frac{k}{2^j})} = 2^j

and that is true, too.

Let me be explicit about result five. For j = 0, we have \varphi(0) = 1 = 2^0\ .

For j = 1, we have

\varphi(0) + \varphi(1/2) = 1 + 1 = 2 = 2^1\ .

For j = 2, we have

\varphi(0) + \varphi(1/4)+ \varphi(1/2)+ \varphi(3/4) = 1 + 1 + 1 + 1= 4 = 2^2\ .

I hope the pattern is clear: we end up adding more 1’s, in just the right number to give us another power of 2..

example: Daubechies D4

One result, the dilation equation is still

\varphi(t) = \sum_n {h(n)\ \sqrt{2}\ \ \varphi(2\ t - n)}

(This is, after all, how we computed the D4 scaling function.)

The h’s are (remember that the first one is h(0), an even coefficient):

\left\{\frac{1+\sqrt{3}}{4   \sqrt{2}},\frac{3+\sqrt{3}}{4   \sqrt{2}},\frac{3-\sqrt{3}}{4   \sqrt{2}},\frac{1-\sqrt{3}}{4 \sqrt{2}}\right\}\

Result two, the sum of the h’s is

\frac{1-\sqrt{3}}{4 \sqrt{2}}+\frac{3-\sqrt{3}}{4   \sqrt{2}}+\frac{1+\sqrt{3}}{4   \sqrt{2}}+\frac{3+\sqrt{3}}{4 \sqrt{2}}\

which does, indeed, simplify to \sqrt{2}\ .

Three, the sum of the even coefficients is (sorry, the order changed)…

\frac{3-\sqrt{3}}{4 \sqrt{2}}+\frac{1+\sqrt{3}}{4   \sqrt{2}}\

which simplifies to \frac{1}{\sqrt{2}}\ .

Since that’s half the total (\sqrt{2}\ ), we can conclude that the sum of the odd coefficients is also \frac{1}{\sqrt{2}}\ . Or we can just compute the sum of the odd coefficients…

\frac{1-\sqrt{3}}{4 \sqrt{2}}+\frac{3+\sqrt{3}}{4   \sqrt{2}}\

and it is, as it must be, \frac{1}{\sqrt{2}}\ .

Now, I can’t actually compute the integral of the D4 scaling function. I can estimate it as closely as I like, but all I have is its values at as many points as I like. But that is all I need! I can, in other words, compute things that look like finite Riemann sums — the areas of thin rectangles — but I can’t actually compute the integral except as a limit.

But the equation

\sum_k { \varphi(\frac{k}{2^j})} = 2^j

holds, and says (four) that every one of those approximations will have the same value, namely 1. Taking a limit doesn’t get any easier than the limit of a constant.

I conclude that the integral is 1 (and that’s the fifth result).

Let me be explicit.

The sum of the values of the D4 scaling function at the integers was chosen to be 1. Let’s look again at the values on the integers…

picture-37

Those 4 values are… \{0.,1.36603,-0.366025,0.\}\

and their sum is 1, and the width of each interval between them is \Delta\ t = 1\ , so the area of 4 rectangles \sum_n {f(t)\ \Delta\ t}\ ) would also be 1.

At the half integers (and integers)….

picture-38

The function values are…

\begin{array}{c} 0. \\ 0.933013 \\ 1.36603 \\ 0 \\ -0.366025 \\ 0.0669873 \\ 0.\end{array}

Now the sum is 2, but the width of each rectangle is \Delta\ t = \frac{1}{2}\ , so the total area is, again, 1.

At all the quarter integers (including halves and integers)…

picture-39

The function values are…

\begin{array}{c} 0. \\ 0.63726 \\ 0.933013 \\ 1.10377 \\ 1.36603 \\ 0.341506 \\ 0 \\ -1355.76 \\ -0.366025 \\ 0.0212341 \\ 0.0669873 \\ -0.0122595 \\ 0.\end{array}

The sum is 4, but each rectangle is of width 1/4, so the total area is still 1.

And so on.

So the equation

\sum_k { \varphi(\frac{k}{2^j})} = 2^j

would seem to give us that the area of every dyadic approximation of a wavelet is equal to 1, and that — in the limit — gives us the integral. The powers of 2 on the RHS exactly offset the diminishing widths of the rectangles in the finite sums used to compute areas of the step functions.

digression on h’s

Let us return to the Haar system. When I showed you the V and W spaces, I wrote the dilation equation as

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

This implies that we have two nonzero c’s:

c(0) = c(1) = 1,

(and the sum of the coefficients is clearly 2).

But we are used to writing the dilation equation as

\varphi(t) = \sum_{n} h(n)\ \sqrt{2}\ \varphi(2t-n)\ ,

which says

c(n) = h(n)\ \sqrt{2},

so that we wrote the Haar system with

h(0) = h(1) = \frac{1}{\sqrt{2}},

(and the sum of the coefficients is \sqrt{2}).

Another form of the equation is common:

\varphi(t) = \sum_{n} h(n)\ 2\ \varphi(2t-n),

which says that

c(n) = 2 h(n)

so that the Haar system would have

h(0) = h(1) = \frac{1}{2},

(and the sum of the coefficients is 1).

Many books point out the existence of different scalings. Strang & Nguyen (Strang, Gilbert; Nguyen, Truong.Wavelets and Filter Banks.Wellesley-Cambridge Press, 1997 (revised edition).ISBN 0 9614088 7 1), however, are more explicit (p. 23):

  • if you are working primarily with the dilation equation, set the sum of coefficients to 2 “… to preserve area.”
  • if you are worling with a single filter, set the sum of coefficients to 1. “That preserves the zero frequency DC term….”
  • if you are workig with a filter bank, set the sum of coefficients to \sqrt{2} “… to account for the downsampling step.

As I said when we looked at Nievergelt’s example, setting the area to 1 (sum = 2) is different from making an orthonormal basis out of the wavelets (sum = \sqrt{2}\ ).

This is the key: if someone hands me a set of filter coefficients for a scaling function – I’m going to add them all up, and see whether the sum is 1, \sqrt{2}\ , or 2.

(Yes, in principle, other normalizations are possible, too; but these are the three I expect to find.)

Burrus et al. are using a sum of \sqrt{2}.

Let’s take a closer look at the scaling factor in the dilation equation.

the sum of the h’s

Suppose we write the dilation equation as

\varphi(t) = \sum_{n} h(n)\ A\ \varphi(2t-n)

for some constant A. We can determine the sum of the h’s.

How? Integrate. (So the integral needs to exist. Easy enough to say if we know \varphi(t)\ , but remember that, in principle, we’re talking about something whose existence is not assured.) Anyway, we integrate:

\int \varphi(t)\ dt = \int (\sum_{n} h(n)\ A\ \varphi(2t-n))\ dt\

Now, if we can interchange the integral and the summation (which may not be a finite sum!), then

\int \varphi(t)\ dt = \sum_{n} h(n)\ A\ \int(\varphi(2t-n))\ dt

Now do a change-of variable y = 2t-n, dy = 2dt. We get

\int \varphi(t)\ dt = \sum_{n} h(n)\ \frac{A}{2} \int(\varphi(y))\ dy

Now, if the integral \varphi(t)\ dt is nonzero, we can divide by it, getting

1 = \frac{A}{2}\ \sum_{n} h(n)

and then

\sum_{n} h(n) = \frac{2}{A}\ .

I’ll remark that we just divided both sides of the equation by \int\ \varphi(t)\ dt = E\ , which is why the sum of the h’s is independent of E.

For Burrus, et al., A = \sqrt{2}

so we have that the sum of the h’s is \frac{2}{\sqrt{2}} = \sqrt{2}\ .

The sum of the h’s is directly related to the factor A in the dilation equation, so just keep your eyes open for it.

Let me also point out that the normalization could be considered part of the definition of the functions which span the space V_j\ . That is, instead of taking it to be the space spanned by the set of translated and scaled functions \{\varphi(t-k)\}\ , we might introduce additional scaling, say, \{\sqrt{2}\ \varphi(t-k)\}\ . We still get the same function (vector) space – all we’ve done is change the sizes of the basis functions.

The real issue may very well be, what’s in your wallet?® — what is your software doing?

What’s next? I will add the requirement that the scaling function be orthogonal to all of its translates. (We already have that the mother wavelet is orthogonal to the scaling function, and that wavelets in W_j\ are orthogonal to functions in V_j\ . Edit: Now we’re going to require that the basis for V_j\ be orthogonal to the basis for V_{j+1}\ . No, we won’t require that – we will get it as a result of requiring that integer translates of the scaling function be orthogonal, i.e. imposing a condition in V_0\ ).

edit, added:
The basis for V_j\ will not be orthogonal to the basis for V_{j+1}\ . We will neither require it, nor obtain it as a result. I will have more to say about this.

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

%d bloggers like this: