Wavelet properties: orthogonality & counterexample « Rip’s Applied Mathematics Blog

Wavelet properties: orthogonality & counterexample

June 21, 2009 — rip

orthogonality

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.

Edit 28 Jun: I believe that once I know that $\psi(t)\$ is a wavelet (i.e. an element of $W_0\$ ), then so are all of its integer translates. This remark occurs once later, as well as here.

Let me speak in general terms first.

There seem to be two properties subsumed under the rubric “orthogonality”.
Edit June 29. “Seem” is the correct word. I am not ready to make this precise, but these two apparently different properties are very close, and possibly the same. I think I can say that if the scaling function and its translates are not orthogonal, then $W_0$ is not an orthogonal complement to $V_0\$ . To put that another way, we can still define a direct sum decomposition

$V_1 = V_0 + W_0$

but $V_0\$ and $W_0$ are not orthogonal subspaces. And so, when I convinced myself that “if $\psi(t)\$ is a wavelet (i.e. an element of $W_0\$ ), then so are all of its integer translates”, I was right… because I was assuming $W_0\$ to be orthogonal to $V_0\$ , and that’s one heck of an assumption.

I am looking into non-orthogonal subspaces, and into biorthogonal wavelets.

One is that we have, for example, the orthogonal direct sum decompositions

$V_1 = V_0 \oplus W_0\$

$V_2 = V_1 \oplus W_1\$

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

We are using the L2 inner product, $\int f(t) g(t) \, dt\$ . The functions f and g are orthogonal if $\int f(t) g(t) \, dt = 0\$ .

The first decomposition tells us that all the functions in $V_0\$ are orthogonal to all the functions in $W_0\$ . The second decomposition tells us the same thing about $V_1\$ and $W_1\$ : all the functions in $V_1\$ are orthogonal to all the functions in $W_1\$ .

The third decomposition tells us more: all the functions in $V_0\$ are orthogonal to all the functions in $W_1\$ ; and all the functions in $W_0\$ are othogonal to all the functions in $W_1\$ .

In particular, the scaling function $\varphi$ and its integer translates which defined $V_0\$ are orthogonal to all the wavelets in $W_0\$ and all the wavelets in $W_1\$ .

In orther words, for the scaling function $\varphi$ we should have

$\int \varphi(t)\ \phi(t) \, dt\ = 0\$ .

$\int \varphi(t-k)\ \phi(t) \, dt\ = 0\$ .

where $\phi\$ is any function (any wavelet) in any space $W_i\$ . (Yes, in particular this is true if $\phi$ is the mother wavelet $\psi\$ ; we must hesitate to talk about the arbitrary translates or the integer translates of $\psi\$ until we know that they are in $W_0\$ .) Edit 28 Jun: I believe that once I know that $\psi(t)\$ is a wavelet (i.e. an element of $W_0\$ ), then so are all of its integer translates. We can stop hesitating.

Similarly, we would have, for example,

$\int \varphi(2t)\ \phi(t) \, dt\ = 0\$ .

where $\phi\$ is now restricted to any function (i.e. any wavelet) in $W_i\$ except $W_0\$ . Why? $\varphi(2t) \in V_1\$ , which is orthogonal to $W_1 \text{ or higher}\$ but not necessarily to $W_0\$ .

Let me point out that one of the challenges here is that we don’t know much about the spaces $W_0\$ ; in particular, we don’t know yet if $\psi(t) \in W_0\$ implies that $\psi(t-1) \in W_0\$ .

The second property is that we may have that the scaling function and its integer translates are orthogonal:

$\int \varphi(t)\ \varphi(t-k) \, dt\ = P\ \delta(k) \$ .

where $\delta(k) \$ is the Kronecker delta, $\delta(0) = 1\$ and $\delta(k) = 0\$ for all k ≠ 0.

There I do not need the distribution, the “Dirac delta function”, whose defining property is the inner product $\int \delta(t)\ f(t) \, dt\ = f(0)\$ . I just want to write one equation instead of these two:

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

$\int \varphi(t)\ \varphi(t-k) \, dt\ = 0 \$ , for k ≠ 0.

However we write it, this is a property of major importance. We can deduce a whole lot more about wavelets in general, about a suitable mother wavelet, and about integer translations of wavelets. In particular, if the scaling function is orthogonal to its integer translates, then integer translates of the mother wavelet are also orthogonal to each other, and we speak of orthogonal wavelets.

This property does hold, of course, for the Haar system and for all the Daubechies scaling functions. (Technically, that’s redundant: we will eventually show that the Haar system is in fact D2, the Daubechies wavelets defined by 2 nonzero h’s.)

The reason I emphasize that there are two ideas of orthogonality here –orthogonal direct sums and integer translates of the scaling function — is that I sometimes get the impression – and it may be a mistaken impression – that people are using the later to prove consequences of the former. But the orthogonal direct sums are more general.

Recall that we can — and have — used non-orthonormal (no, I didn’t say non-orthogonal) bases in finite dimensional vector spaces. These lead us quickly to the definition of a reciprocal basis: we take dot products of a vector with the reciprocal basis to compute the basis-coefficients of that vector. (As I post this, at least, “reciprocal basis” is in the tag cloud, so you can look there.)

Well, we can do the same thing with wavelets. If we have a basis of wavelets but it is not orthonormal, then we need to construct the reciprocal basis. The pair, basis of wavelets and reciprocal basis, is called a bi-orthogonal system. Just a different name for something we’ve seen before.

(If we have an orthogonal basis which is not orthonormal, the reciprocal basis differs from the original only by scale factors on each vector but the directions are the same; this means we just end up with scale factors associated with the dot-products. I will show you this, below. But what it means is that, in practice, a merely orthogonal basis is almost as good as an orthonormal one.)

I am looking forward to playing with a bi-orthogonal system, so that I can look for the properties which depend on the ortogonal direct sum decomposition rather than on the orthogonality of integer translates of the scaling function.

If the integer translates are orthogonal but not orthonormal, we can fix that just by dividing $\varphi\$ by its norm $\sqrt{P}\$ , where P is defined by

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

digression on Fourier

Suppose we have a function which is precisely a finite Fourier series, say,

$f(x) = 3 \cos (2 x)+2 \sin (x)\$

That seems unambiguous and straightforward: our f(x) can be written exactly using sin(x) and cos(x). But, with the L2 inner product on ${[0,\ 2\pi]}\$ …

$\int_0^{2 \pi } f(t)\ g(t) \, dt\$

and the associated norm

$||g|| = \sqrt{\int_0^{2 \pi } g(t)\ g(t) \, dt}\$

we have that the set {1, cos[nx], sin[nx]} is orthogonal but not orthonormal. Each of sin(nx) and cos(nx) has norm $\sqrt{\pi}\$ (because the integral of the square is $\pi\$ )…

trig norms

and the constant function 1 (= cos (0x), if you will) has norm $\sqrt{2}\ \sqrt{\pi}\$ .

const norm

The orthonormal basis is constructed by dividing each of these functions by its norm; the reciprocal basis is constructed by dividing each of these functions by the square of its norm; equivalently, the reciprocal basis is constructed by dividing each of the orthonormal functions by the norm of the original function.

However we carry it out, the end result is that the set

$\{\frac{1}{\sqrt{2\ \pi}}, \frac{cos[nx]}{\sqrt{\pi}}, \frac{sin[nx]}{\sqrt{\pi}}\}\$

is an orthonormal basis; and the set

$\{\frac{1}{2\ \pi}, \frac{cos[nx]}{\pi}, \frac{sin[nx]}{\pi}\}\$

is the basis reciprocal to $\{1, cos[nx], sin[nx]\}\$ .

In this form…

$f(x) = 3 \cos (2 x)+2 \sin (x)\$

f(x) is given in terms of the orthogonal but non-orthonormal basis. We can confirm that its components {3, 2} wrt that basis can be computed as the dot products of f with the reciprocal basis. Only two terms are nonzero:

get coeffs

We are more likely to have simply been told that the coefficients are to be found using

$\frac{1}{\pi}\ \int_0^{2 \pi } sin(x)\ f(x) \, dt\$

and

$\frac{1}{\pi}\ \int_0^{2 \pi } cos(2x)\ f(x) \, dt\$ .

Nothing about a reciprocal basis, just a recipe with a god-given factor of $\frac{1}{\pi}\$ in front of the integrals. Conceptually, those factors belong inside the integrals, under the trig functions. But it’s the same calculation.

If, on the other hand, we had constructed the orthonormal basis $\{\frac{1}{\sqrt{2\ \pi}}, \frac{cos[nx]}{\sqrt{\pi}}, \frac{sin[nx]}{\sqrt{\pi}}\}\$ , then the coefficients wrt the orthonormal basis are

get 2nd coeffs

which may look weird until I remind you that we are implicitly writing

$f(x) = (3\ \sqrt{\pi})\ \frac{\cos (2 x)}{\sqrt{\pi}}+(2\ \sqrt{\pi})\ \frac{\sin (x)}{\sqrt{\pi}}\$

which is exactly our function f.

The point I am belaboring – perhaps excessively – is that most of us have been coping with an orthogonal but non-orthonormal basis most of our lives, and constructing the reciprocal basis in such a case amounts to just sticking a scaling factor in front of the dot product calculation for the components. We get the components without explicitly desribing the reciprocal basis.

We do much the same for wavelets and the scaling functions: so long as they are orthogonal to their integer translates, we cope with their norms not being 1.

a counterexample

Since I haven’t yet itemized the consequences of orthogonality under integer translation, I won’t show you that the following scaling function violates them. But I want to put this example out here, because it does satisfy all 6 consequences of the dilation equation; but it is not orthogonal under integer translation, and it will not satisfy the consequences of orthogonal integer translates.

And yet, because we have clearly defined spaces $V_0\$ , $V_1\$ , etc., we should have orthogonal direct sum decompositions.

Here it is. Just a triangle. You can also call it a linear spline. (And higher-order splines are also counter-examples.)

triangle

So, we can define the space $V_0\$ as the span of $\varphi(t)\$ and its integer translates $\varphi(t-k)\$ .

NOTE that because the triangle $\varphi(t)\$ is positive on (0,2), it cannot be orthogonal to two of its integer translates, namely $\varphi(t-1)\$ and $\varphi(t+1)\$ . They overlap and there are no negative values to cancel things out.

That is, it is false that $\varphi(t)\$ is orthogonal to all of its integer translates. All but two is two too few.

For example, we can look at $\varphi(t)\$ (black) and $\varphi(t-1)\$ (red) and their intersection (yellow)…

intersection

That the area under the intersection is positive tells us that these functions are not orthogonal.. The inner product, however, is not the area. We can estimate the inner product by a sum…

approx ip

I should draw the product $\varphi(t)\ \varphi(t-1)\$ …

exact ip pic

but of course we can compute the inner product exactly, too. Since the functions are linear, their product is quadratic (where its not zero) and the integral is cubic. In fact, it’s

exact ip calc

Anyway, we take that triangular scaling function and all its integer translates to be $V_0\$ .

We can define $V_1\$ as the span of the set $\{\varphi(2t-k)\}\$ . Those are just narrower triangles of height 1, e.g $\{\varphi(2t)\}\$ looks like….

v1 triangle

The really big question is: is $V_0\$ a subspace of $V_1\$ , $V_0 \subset V_1\$ ?

The answer is yes. (Otherwise this wouldn’t be a counterexample!) We have that

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

I can show it to you (the command shows that I am adding three functions in $V_1$ to get my scaling function in $V_0\$ :

sum of triangles

Now, that’s our dilation equation, except that we don’t have the factor of $\sqrt{2}\$ . To put that another way, if the h’s are

$\{1/2,1,1/2\}\$

then their sum is 2.

To put that a third way, right now we have A = 1.

No big deal; to change the sum we multiply and divide by $\sqrt{2}\$ . This gives us our usual dilation equation

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

with new h’s

$\{\frac{1}{2 \sqrt{2}},\frac{1}{\sqrt{2}},\frac{1}{2 \sqrt{2}}\}\$ .

Now, we have 6 properties to check…

The sum of the h’s = 2/A.
$\varphi(t) = \sum_n {h(n)\ A\ \ \varphi(2\ t - n)}\$ .
$E = \int\ \varphi(t)\ dt \$ .
The sum of the even h’s = the sum of the odd h’s.
$\sum_k { \varphi(\frac{k}{2^j})} = 2^j \text{(for E = 1)}$
$\sum_k { \varphi(t+k)} = 1 \text{(for E = 1)}\$

And I have been consistently referring to even h’s, for example, when I really mean h’s with even index, h(2n).

We have (one) set A = $\sqrt{2}\$ and (two) the sum of the h’s is $\sqrt{2}\$ .

There is only one odd h, h[1], and it’s $\frac{1}{\sqrt{2}}\$ , and each of the two even h’s is half that value, so we do have (three) the sum of the even h’s equals the sum of the odd h’s. Now is a good time to remark that the number of h’s is not even.

What about $E = \int\ \varphi(t)\ dt \$ ?

Our scaling function is a triangle of base 2 and height 1, so (four) its area is 1, so E = 1.

That triangle is continuous, so we should have (five) the generalized partition of unity

$\sum_k { \varphi(t+k)} = 1 \text{(for E = 1)}\$

Let’s try a few. Here are t = 1/2, 1/4, -3/8, 31/16. This sample is not a proof, but it’s all I personally need for now.

generalized partition

And since E = 1 we should have (six) the dyadic sum

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

Let’s try the first few.

partition

Remarks

Those linear splines and their translates do provide us with spaces $V_0\$ , $V_1\$ , and so on. They satisfy the 6 properties I expect them to.

But I have no idea, so far, how to find a function in $W_0\$ . There are two obvious candidates — orthogonal to the scaling function — but they fail to be orthogonal to all of its integer translates.

This is not a big deal. We’re going to warp those splines to hell and back, I think. Or maybe it will be the scaling function. I’m not sure yet, but something will be transmogrified.

There is a way to get an orthonormal basis from the set of splines: the result is called Battle-Lemarie wavelets. In contrast to everything we’ve seen, however, they do not have finite support (equivalently, they do not have a finite number of h’s) — but they are useful nevertheless.

So, we will see splines again.

Posted in math time series, wavelets. Tags: mathematics, wavelets. Leave a Comment »

	rip on Color: decomposing the RGB A t…
	rip on the matrix exponential: 1 of…
	Evan on the matrix exponential: 1 of…
	rip on The dyadic expansion of Daubec…
	Bill Maier on The dyadic expansion of Daubec…
	rip on 12 pentagons!
	Daniel Lichtblau on 12 pentagons!
	william on books added 21 June
	Wavelet properties: … on Wavelets: semi-orthogonal, fro…
	rip on transpose matrix and adjoint o…

Rip’s Applied Mathematics Blog

Pages

Categories

Meta

Tags