Wavelets: Consequences of Orthogonality and Review II

digression: eigenvalue 1

Before I proceed with consequences of orthogonality, I need to mention an omission. For one thing, I have gotten so caught up in the properties I’ve been looking at, that I have forgotten one of the crucial ones we used earlier. For another thing, the consequence which I have forgotten is still a little strange to me.

The consequence (or consequences)?

  • That the dilation equation could be written as an eigenvalue equation,
  • that the existence of a scaling function seems to be equivalent to an eigenvalue = 1,
  • and that the values of the scaling function at the integers are given by the corresponding eigenvector.

This has been crucial to some of our work: the recursion which I use for computing the scaling function is initialized by setting the values of the scaling function at the integers — that is, by finding the eigenvector with eigenvalue 1. Recursion — especially when combined with a lookup table — is very easy and very powerful; but we absolutely had to have initial values, and that eigenvector provided them. (I did this for the Daubechies D4, and for four wavelet systems with 6 nonzero h’s.)

The strangeness? Read the rest of this entry »

Wavelets: Review I and Going Forward a Little

Let us recall what we have.

We have a collection of nested spaces…

\dotsm\ V_{-3} \subset\  V_{-2} \subset\  V_{-1} \subset\  V_{0} \subset\  V_{1} \subset\  V_{2}\ \dotsm\ \

… whose intersection is the trivial space and whose union is all square integrable functions on the real line:

\cap\ V_i = \{0\}\ and \cup\ V_i = L^2(R)\ .

We assume that the spaceV_0\ is translation invariant and has the scaling property:

f(x) \in V_0\ \text{ if and only if } f(x-k) \in V_0\ for all integers k;

f(x) \in V_j \text{ if and only if } f(2^{-j} x) \in V_0\ .

Finally, the only real theorem I have shown you says that if we also have an orthonormal basis for V_0\ , then we can get an orthonormal basis for L^2(R)\ :

\psi_{j,k} (x) := 2^{j/2)} \psi(2^j\ x - k)\
Read the rest of this entry »

Wavelets: Multiresolution Analysis (MRA)

By and large I try not to flee into cold, formal mathematics, not here. You can find all too many books that will give you just the mathematics (and some of them are invaluable references). On the other hand, sometimes I am way too vague. Let me try to give you a clear statement of what I’m going on about when I say “multiresolution analysis” (MRA).

(Don’t misunderstand me. When I’m studying something, I’m sitting there with collections of definitions, theorems, proofs, and examples – trying to make sense of them. I just think that the collection itself is not a substitute for understanding.)

There’s a lot to be said for having a clearly stated theorem. Working through this has had a large impact on my own grasp of the properties of wavelets.

The most lively summary of multiresolution analysis can be found in the first couple of pages of chapter 5 of Daubechies’ “Ten Lectures on Wavelets”. The most lively introduction can be found on pages 10-16.

I have more than a few, close to several, books that seem to present the following concepts in the same way. First, they use multi-resolution analysis to describe orthonormal wavelets; then they use filter banks to describe biorthogonal wavelets; finally, they explain how biorthogonal wavelets could be described by a modified multi-resolution analysis.
Read the rest of this entry »

Wavelets: semi-orthogonal, from linear splines

Edit: 13 July, just one remark added. see “edit” below.

How are things going? As I said yesterday in “happenings”, the simplest answer is: right now I’m just thrilled when I can reproduce a drawing in a book, even if I don’t understand why the method works or where the function came from.

This is post that I ended up with when I started out to write a “happenings” post yesterday. I promised you a picture. In fact, I’ll give you a mother wavelet for the linear spline scaling function. (That link occurs a few more times. What can I say? That’s what I’m building on, in more than one way.)

You may recall that I have shown you two ways to approximate a scaling function. The one I do not understand applies convolution and downsampling repeatedly. The one I do understand is the dyadic expansion, and I’ve been using it ever since I worked it out, in preference to the other method.

Well. I have now seen a scaling function which is infinite at all the dyadic points, so the dyadic expansion hasn’t got a prayer of working! But the convolution and downsampling algorithm gives me a drawing which seems to match the book.
Read the rest of this entry »

Wavelet properties: orthogonality & counterexample


Edit 3 Aug. It is embarrassing to be so wrong in my guesses. Well, I understand more today than I did yesterday.

The two forms of orthogonality are not the same. We saw in the subsequent post about semi-orthogonality that we could have an orthogonal direct sum V_0 \oplus W_0 while having non-orthonormal bases in V_0 and W_0\ . Conversely, if we had a direct sum which was not orthogonal, we could still choose orthonormal bases in the two spaces. Okay, let me rephrase that: if we have bases in V_0 and W_0\ at all, I know we can make them orthonormal.

I am no longer sure about the following guess about integer translates of elements of W_0\ . And I am completely wrong about the conjecture in red.
Read the rest of this entry »

Wavelet Properties: one more from the dilation equation


I want to add one more property to the previous post. This is long enough that I do not want to insert it as an edit. It’s amazing that I ever considered even for a moment to insert it as an edit!

Just as we deduce what is called a partition of unity \sum_k { \varphi(k)} = 1 from the dyadic sum

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

(by setting j = 0)

we can get a more general equation, if \varphi is continuous. We can show that

\sum_k { \varphi(t-k)} = 1\ ,

where the sum, as before, is over all integer k. (The proof uses the previous dyadic sum and continuity to say something about non-integer values.) This may be called a generalized partition of unity.
Read the rest of this entry »

Wavelet properties: consequences of the dilation equation

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).
Read the rest of this entry »

Wavelet Properties: the dilation equation.


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. Read the rest of this entry »

N = 6 scaling functions and mother wavelets


The impetus for this post is figure 1.4 on page 6 of Burrus et al. (Since it’s been a while, that’s Burrus, C. Sidney; Gopinath, Ramesh A.; Guo, Haitao. Introduction to Wavelets and Wavelet Transforms, A Primer. Prentice Hall, 1998.ISBN 0 13 489600 9.)

They offered the figure as an illustration of four different scaling functions; in addition, these scaling functions were parameterized by two angles.

Now I know how to produce the drawings of those scaling functions — and I also know how to produce drawings of the corresponding mother wavelets, which they did not show on page 6. It also turns out that they have interchanged the legends for figures (a) and (b) — and when we can produce the drawings ourselves, that mistake becomes almost irrelevant.

This post also serves to reiterate the calculation sequence for plotting a scaling function and its corresponding mother wavelet. Read the rest of this entry »

Mother wavelet from scaling function: D4 and Haar

D4 dyadic wavelet

We can compute the mother wavelet from the scaling function. Let me show you how to do this for Daubechies’s D4.

First, we need the scaling function.

the D4 scaling function again, quickly

This is review. There is a matrix M0 which has an eigenvector with eigenvalue 1, and that eigenvector gives me the values of the scaling function \varphi at the integers. Once I have initial values, I can compute \varphi by recursion (and because of the specific form of the recursion, only at points whose denominator is a power of 2).

I start by constructing the matrix M0 in principle… Read the rest of this entry »