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.
- Where do the dilation equation and wavelets come from?
- What can we deduce from the dilation equation?
- What can we deduce from the requirement that the scaling function and its integer translates be orthogonal?
- 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?
Suppose we have a function … even more, suppose we have a collection of its “integer translates” , where k may be any integer.
Define the space to be that space spanned by the collection of integer translates . In general, I may not be able to describe that space in any other way; whatever the span, that is .
I also haven’t said that the 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 , and let be the space they span.
For the Haar system, we know that . 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 we have. That is a subspace of , with spanned by the set tells us that any function in may be written as a linear combination (possibly infinite!) of the . In particular, the scaling function itself may be wriiten as a linear combination of the .
But that gives us a dilation equation
for some coefficients c(n). Conversely, if satisfies the dilation equation, then I guess we ought to have .
The dilation equation effectively comes from the requirement that .
Now we add a little more structure, an inner product.
If is a proper subspace of , and if we introduce an inner product, then we may split into and its orthogonal complement; that is, we define the orthogonal complement as:
For these purposes, the customary inner product of two functions f, g is the integral of their product:
The definition of gives us a couple of immediate consequences. For one thing, every function is orthogonal to the scaling function and is also orthogonal to every translate, .)
For another thing, , so every function is also in , and therefore can be written in terms of the set . That is, we have
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 .)
So the mother wavelet, as far as we know at this point, could be any function in , and it satisfies an equation like the dilation equation. Note, as we saw when we were computing, that we have on the LHS but on the RHS.
And we continue, defining …
Now, for example, take in terms of and and then write in terms of :
We can write a function in using a single scaling function in , and wavelets from the . (Oh, yes, the wavelets derived from the scaling function are functions in the 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 . 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 . And we should have
For the Haar system, here’s the scaling function and one possible translate, , on [-1,3]…
As I said earlier, define the space to be that space spanned by the collection of integer translates . We can describe : the space of step functions with jumps at the integers.
Now we consider the collection of scaled and translated functions . Here’s for the Haar… and for one of its translates, in this case, .
They are nonzero only over a half-unit interval. That is significant for their inner products with themselves (their norms).
Define the space as that space spanned by the collection . For the Haar system, we can describe as the space of step functions with jumps at the half-integers.
Note that if we add and , we get the unit step function on [0,1) — that is, we get :
That’s a form of the dilation equation!
(It’s not the way we’ve been writing it – we’re missing – but this is a dilation equation, and we can – and will shortly ! – insert the easily enough.)
That says that : 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 , 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 (spanned by ) to be a subspace of (spanned by ):
- the set spans by definition of
- the set spans by definition of
Then any function in can be written, by definition, as a linear combination of the … hence any function in can be written as a linear combination of the … hence the particular function can be written as a linear combination of the .
That is, we have a dilation equation
essentially because we require .
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 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.
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
Now imagine that instead of 4 points I have a step function f(t) defined on the quarter integers in [0,1). I have (integers, halves, quarters), so I write
It appears that I want the scaling function , the mother wavelet , and two wavelets and . That is, we are going to write our step function f(t) as the combination
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 .
Here’s those four functions all together.
I should probably remind us all that the Haar mother wavelet satisfies the equation
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 , and I could graph the step function f(t) using these 4 basis functions (all scaling, no wavelets; all ):
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.
(Their areas are also 1, but that’s not what we’re computing here.)
The two daughter wavelets and , 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 to double the heights of their squares – if we want the daughter wavelets to be part of an orthonormal basis.
That is, for example,
(I told you I’d put that in there. And if we wanted unit area instead of unit norm, we would have multiplied by 2, instead of by . 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
… and that f(t) is
(That’s easy enough to check algebraically: just use the recursion equation for the , and then use the dilation on the resulting . 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: …
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 by a particular function in , that is the approximation.
Now add the next term. If we approximate our function by our functions in , namely as
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 can be written exactly as
Now, one more thing. I didn’t have to replace the data by a function in ; 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 . Then my scaling function needs to be of width 4, i.e. in , my mother wavelet is in , and the two finest-scale wavelets are in :
Let me be very clear. I could have gone so far as to replace my 4 points by the step function
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,
The wavelet expansion should use
and instead of
(with the very same coefficients, just applied to differently-scaled functions).
Here’s what it looks like:
From our chosen scaling function – 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 . 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
we have that is orthogonal to ; and since that subspace decomposition implies
we have that also satisfies something like the dilation equation.
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.)