A Construction of Wavelets

Peter Z. Daffer

Information Systems Planning and Analysis

1100 Circle 75 Parkway, Suite 900 Atlanta, Georgia 30339

Hideaki Kaneko

Department of Mathematics and Statistics Old Dominion University Norfolk, Virginia 23529-0077

A CONSTRUCTION OF WAVELETS

Peter Z. Daffer and Hideaki Kaneko

Abstract In this note, given a multiresolution analysis, we construct a class of four-coefficient scaling filters using only elementary algebraic operations. The method of construction also reveals that the sum conditions ∑ a_{even} = ∑ a_{odd} = 1 can also be verified without referring to the vanishing moment property.

1 A Review of Construction of Wavelets

We begin this note by recalling the definition of a multiresolution analysis.

Definition A multiresolution analysis ⋯ ⊆ V_{−1} ⊆ V_{0} ⊆ V_{1} ⊆ ⋯ with scaling function φ is an increasing sequence of subspaces of L^{2}(R) satisfying the following four conditions:

1. (density) ∪_{j}V_{j} is dense in L^{2}(R),

2. (separation) ∩_{j}V_{j} = {0},

3. (scaling) f(x) ∈ V_{j} ⇔ f(2^{−j}x) ∈ V_{0},

4. (orthonormality) {φ(x − γ)}_{γ∈Z} is an orthonormal basis for V_{0}.

First of all, {2^{j/2}φ(2^{j}x − γ)}_{γ∈Z} forms an orthonormal basis for V_{j}. This is evident from the definition. In order to form an orthonormal basis for L^{2}(R), the density condition 1 seems to suggest, at first, to combine all the orthonormal bases {2^{j/2}φ(2^{j}x − γ)}_{γ∈Z} of V_{j}. But this does not work since there are distinct elements from two orthonormal bases, {2^{j/2}φ(2^{j}x − γ)}_{γ∈Z} for V_{j} and {2^{(j+1)/2}φ(2^{j+1}x − γ)}_{γ∈Z} for V_{j+1}, that are not orthogonal to each other. What is required at this point is the construction of an orthonormal basis for the orthogonal complement W_{0} of V_{0} in V_{1}. More generally, we need to find an orthonormal basis for W_{j} where

V_{j+1} = V_{j} ⊕ W_{j},

for j = 0, 1, … The function ψ for which {ψ(x − γ)}_{γ∈Z} is an orthonormal basis for W_{0} is the wavelet generator . Once ψ is found, then {2^{j/2}ψ(2^{j}x − γ)}_{γ∈Z} form an orthonormal basis for W_{j} and as

L^{2}(R) = V_{0} ⊕ (⊕_{j=0}^{∞}W_{j}) = ⊕_{j∈Z}W_{j},

{φ(x−γ)}_{γ∈Z} ∪{2^{j/2}ψ(2^{j}x−γ)}_{γ∈Z,j≥0} or {2^{j/2}ψ(2^{j}x−γ)}_{γ∈Z,j≥0} form an orthonormal wavelet basis for L^{2}(R).

Since φ ∈ V_{0} ⊆ V_{1}, we must have the following scaling identity ,

φ(x) = ∑_{γ∈Z} a_{γ}φ(2x − γ).  (1.1)

It is well known [1] that the conditions that must be met by the coefficients a_{i}’s are the following:

∑_{γ∈Z} |a_{γ}|^{2} = 2,  (1.2)
∑_{γ′∈Z} a_{γ′}a_{2γ+γ′} = 2δ(γ, 0),  (1.3)

and

∑_{γ∈Z} a_{γ} = 2.  (1.4)

Equation (1.2) is a consequence of the scaling identity and of the fact that ∥φ∥_{2} = 1. Equation (1.3) is obtained from condition 4 of the definition, -i.e.,

∫ φ(x − γ)φ(x) dx = δ(γ, 0),

upon substituting the scaling identities for φ(x − γ) and φ(x). Equation (1.4) is obtained also from the scaling identity with additional condition that ∫ φ(x)dx ≠ 0. Namely, integrate both sides of (1.1) and make a change of variable. Note that (1.2) is a special case of (1.3). Clearly, the scaling function determines a multiresolution analysis, but not conversely. A construction of wavelets involves reversing the procedure. In other words, we need a characterization of a function that satisfies the scaling identity (1.1) and that generates a multiresolution analysis. In order to better explain the content of the present note which is described in the next section, let us review below in five steps how a general construction of wavelets is done. We refer the reader to [1] and [3] for a more complete descriptions of these steps.

Step 1: This step consists of producing solutions to algebraic identities (1.2)-(1.4).

Step 2: Once a_{i}’s are determined, a possible scaling function φ is defined. This can be done, for instance, by finding a fixed point of the linear transformation

Sf(x) = ∑_{γ∈Z} a_{γ}f(2x − γ)

by iterations

φ = lim_{n→∞} S^{n}f

with an appropriate initial function f. Step 3: Now, we must verify that the function φ, defined in Step 2, generates a multiresolution analysis. To this end, we let

A_{0}(ξ) = \frac{1}{2} ∑_{γ∈Z} a_{γ}e^{2πiγξ}.

It turns out that the following condition (1.5) along with (1.2)-(1.4) serve as sufficient conditions for the orthonomality of {φ(x − γ)}_{γ∈Z}.

A_{0}(ξ) ≠ 0  for |ξ| ≤ \frac{1}{4}.  (1.5)

Step 4: This step is to study those conditions that are necessary to construct wavelets. Let ψ_{0} = φ and ψ_{1} = ψ, a wavelet generator to be determined. Also, let a_{γ}^{0} = a_{γ}, the solutions of (1.2)-(1.4). Since {ψ_{k}(x − γ)}_{γ∈Z,k=0,1} must be an orthonormal basis for V_{1} = V_{0} ⊕ W_{0}, noting that {φ(2x − γ)}_{γ∈Z} is an orthonormal basis for V_{1},

ψ_{k}(x) = ∑_{γ∈Z} a_{γ}^{k}φ(2x − γ),  k = 0, 1.  (1.6)

Equation (1.6) with k = 0 is the scaling identity (1.1). The condition that ψ_{0} ⊥ ψ_{1}, or more precisely, with j, k ∈ {0, 1}, γ ∈ Z,

∫ ψ_{j}(x − γ)ψ_{k}(x)dx = δ(j, k)δ(γ, 0),

leads to, upon replacing ψ_{0} and ψ_{1} by the corresponding expressions in (1.6),

∑_{γ′∈Z} a_{γ′}^{j}a_{2γ+γ′}^{k} = 2δ(j, k)δ(γ, 0).  (1.7)

Equation (1.7) contains (1.2) and (1.3) as special cases. We can not expect the wavelet generator ψ to satisfy ∫ ψ(x)dx ≠ 0, so we do not have an equivalent condition to (1.4) for a_{γ}^{1}. Hence, we can only use (1.4), restated below in the current notation as

∑_{γ∈Z} a_{γ}^{0} = 2.  (1.8)

At this point, we have reduced the problem of constructing wavelets to the solution of algebraic identities (1.7) and (1.8), together with condition (1.5), which was to guarantee the orthonomality condition 4 for φ. In summary, we have (Theorem 4.3, [3]) that

Theorem 1.1 Suppose φ generates a multiresolution analysis and a_{γ}^{k} satisfy (1.7) and (1.8) with ψ_{k} defined by (1.6) and ψ_{0} = φ. Then the functions {2^{j/2}ψ_{1}(2^{j}x − γ)} for j ∈ Z, γ ∈ Z form an orthonormal basis of L^{2}(R).

Step 5: This step completes the task that began in Step 4. Namely, we need to produce the solutions of (1.7) and (1.8) that satisfy (1.5). The function A_{0} defined earlier can be written as

A_{0}(ξ) = \frac{1}{2} ∑_{γ∈Z} a_{γ}^{0}e^{2πiγξ}.

Similarly, we define

A_{1}(ξ) = \frac{1}{2} ∑_{γ∈Z} a_{γ}^{1}e^{2πiγξ}.

In terms of A_{0} and A_{1}, equations (1.7) and (1.8) can be shown to be equivalent to

∑_{p=1}^{2} A_{k}(ξ + η_{p})A_{j}(ξ + η_{p}) = δ(j, k),  (1.9)

and

A_{0}(0) = 1,  (1.10)

respectively [1] where η_{1} = 0 and η_{2} = \frac{1}{2}. One method of construction presented by Daubechies is to first solve for {a_{γ}^{0}} using

A_{0}(0) = 1

|A_{0}(ξ)|^{2} + |A_{0}(ξ + \frac{1}{2})|^{2} = 1

A_{0}(ξ) ≠ 0 for |ξ| ≤ \frac{1}{4},

and subsequently incorporate the remaining equations from (1.9) to find A_{1}(ξ) which in turn gives {a_{γ}^{1}}. The remaining equations are

|A_{1}(ξ)|^{2} + |A_{1}(ξ + \frac{1}{2})|^{2} = 1,  (1.11)

and

A_{0}(ξ)A_{1}(ξ) + A_{0}(ξ + \frac{1}{2})A_{1}(ξ + \frac{1}{2}) = 0.  (1.12)

It is shown [1] that

A_{1}(ξ) = e^{2πiξ}A_{0}(ξ + \frac{1}{2})

solves (1.11) and (1.12) and this amounts to setting

a_{γ}^{1} = (−1)^{γ+1}a_{1−γ}^{0}.  (1.13)

2 A Construction of Scaling Functions and Their Wavelets

In this section, we present a method of constructing a class of four-coefficient scaling filters using only elementary algebraic operations. Particularly, we are interested in obtaining the solutions a_{γ} ≡ a_{γ}^{0} of equations (1.2), (1.3) and (1.4). Recall from the previous section, each solution will generate a multiresolution analysis provided that condition (1.5) holds. Formulas for constructing four-coefficient scaling filters already exist. An elegant approach of Daubechie is well documented in [1]. Therefore, we do not claim that the results obtained in this section are new. But rather, the purpose of the present note is to shed another perspective in constructions of scaling filters and to demonstrate the fact that the sum condition ∑ a_{even} = ∑ a_{odd} = 1 can be derived without referring to the vanishing moment property. The fact that the sum condition is a consequence of (2.1), which will be established in this section, appears to be new. We do not discuss a complete construction of wavelets in this note. However, once a_{γ} ≡ a_{γ}^{0} are found, the associated wavelets can be generated simply from (1.13).

We consider the case where only a_{0}, a_{1}, a_{2} and a_{3} are the terms which could possibly be nonzero. We also assume that they are real. Equations (1.2), (1.4) and (1.3) become respectively,

\begin{aligned}a_{0}^{2} + a_{1}^{2} + a_{2}^{2} + a_{3}^{2} & = 2 \\ a_{0} + a_{1} + a_{2} + a_{3} & = 2 \\ a_{0}a_{2} + a_{1}a_{3} & = 0. \end{aligned}  (2.1)

If a_{3} ≠ 0, then a_{1} = −\frac{a_{0}a_{2}}{a_{3}} , and substituting, we get

\begin{aligned}a_{0}^{2} + \frac{a_{0}^{2}a_{2}^{2}}{a_{3}^{2}} + a_{2}^{2} + a_{3}^{2} & = 2 \\ a_{0} − \frac{a_{0}a_{2}}{a_{3}} + a_{2} + a_{3} & = 2. \end{aligned}

Let x ≡ a_{0}, y ≡ a_{2} and c ≡ \frac{1}{a_{3}} , thereby obtaining

\begin{aligned}x^{2} + c^{2}x^{2}y^{2} + y^{2} & = 2 − \frac{1}{c^{2}} \\ x − cxy + y & = 2 − \frac{1}{c}. \end{aligned}  (2.2)

Assuming 1 − cx ≠ 0, (2.2) yields

y = \frac{2 − \frac{1}{c} − x}{1 − cx} and y^{2} = \frac{2 − \frac{1}{c^{2}} − x^{2}}{1 + c^{2}x^{2}} .  (2.3)

Squaring the first equation and equating it to the second equation yields

2c^{2}x^{4} − 4c^{2}x^{3} + (2c^{2} − 4c + 4)x^{2} + 4(c − 1)x + 2 − \frac{4}{c} + \frac{2}{c^{2}} = 0.  (2.4)

In order to study the solutions of (2.4), let

f(x) = 2c^{2}x^{4} − 4c^{2}x^{3} + (2c^{2} − 4c + 4)x^{2} + 4(c − 1)x + 2 − \frac{4}{c} + \frac{2}{c^{2}} .

First, we observe that, for every c ≠ 0,

f′(\frac{1}{2}) = 0,  (2.5)

and that

f(x + \frac{1}{2}) = 2c^{2}x^{4} + (4 − 4c − c^{2})x^{2} + \frac{1}{8}c^{2} + c + 1 − \frac{4}{c} + \frac{2}{c^{2}} .  (2.6)

Equation (2.6) shows that the graph of f is symmetric about the line x = \frac{1}{2}. Let f̃(x) ≡ f(x+ \frac{1}{2}). Then f̃′(x) = 0 has roots

0 and ± \frac{1}{2}\sqrt{1 + \frac{4}{c} − \frac{4}{c^{2}}} .

When ±\frac{1}{2} \sqrt{1 + \frac{4}{c} − \frac{4}{c^{2}}} are real, -i.e., for

c < −2 − 2\sqrt{2} or c > −2 + 2\sqrt{2},  (2.7)

f̃ attains its minimum at ±\frac{1}{2} \sqrt{1 + \frac{4}{c} − \frac{4}{c^{2}}} . For the values of c specified in (2.7), we have f̃(±\frac{1}{2} \sqrt{1 + \frac{4}{c} − \frac{4}{c^{2}}} ) = 0. Translating back into f, we conclude that

\frac{1}{2} ± \frac{1}{2}\sqrt{1 + \frac{4}{c} − \frac{4}{c^{2}}} ,  (2.8)

are the roots of f(x) = 0. Each is a double root of the quartic f(x) = 0. If we denote two roots in (2.8) by x_{1} and x_{2}, then notice that x_{2} = 1 − x_{1}. This, of course, is a rehash of the fact that the graph of f is symmetric about x = \frac{1}{2}. The following theorem serves as the first step toward establishing the algorithm that generates many wavelets.

Theorem 2.1 Consider the equations in (2.1) and let x ≡ a_{0}, y ≡ a_{2} and c ≡ \frac{1}{a_{3}} . Then x + y = 1.

Proof: Since x_{1} = \frac{1}{2} + \frac{1}{2} \sqrt{1 + \frac{4}{c} − \frac{4}{c^{2}}} and x_{2} = \frac{1}{2} − \frac{1}{2} \sqrt{1 + \frac{4}{c} − \frac{4}{c^{2}}} are two roots of f(x) = 0,

(x − \frac{1}{2} − \frac{1}{2}\sqrt{1 − \frac{4}{c^{2}} + \frac{4}{c}})(x − \frac{1}{2} − \frac{1}{2}\sqrt{1 − \frac{4}{c^{2}} + \frac{4}{c}}),

are two linear factors of f(x), and upon multiplying and simplifying, we obtain x^{2} − x + \frac{1}{c^{2}} − \frac{1}{c}. If x = x_{1} or x = x_{2}, then x^{2} − x + \frac{1}{c^{2}} − \frac{1}{c} = 0, which reduces

cx − 1 = cx^{2} + \frac{1}{c} − 2.  (2.9)

But we have, from (2.3) and (2.9),

x + y = x + \frac{2 − \frac{1}{c} − x}{1 − cx} = \frac{−cx^{2} − \frac{1}{c} + 2}{1 − cx} = 1.

□ Note that from (2.1) and Theorem 2.1, we obtain

a_{0} + a_{2} = 1 and a_{1} + a_{3} = 1.  (2.10)

Note also that (1.13) implies A_{0}(\frac{1}{2}) = 0 and A_{1}(0) = 0, which is the well known vanishing moment condition for wavelets. A_{0}(\frac{1}{2}) = 0 is satisfied by (2.10). And this is what is done generally for construction of wavelets. More specifically, (2.1) and (1.13), and hence (2.10), are solved together to get the complete descriptions of scaling filters as well as wavelets. As pointed out earlier, the task of this note has been different. We examined the solutions of (2.1) independently, and derived (2.10) without referring to (1.13). In [2] (p. 296), it is noted that “the sum condition ∑ a_{even} = ∑ a_{odd} = 1 is always imposed”. Theorem 2.1 tells us that, with wavelets whose scaling relation involves four terms, it is necessary that ∑ a_{even} = ∑ a_{odd} = 1. Some other immediate consequences of Theorem 2.1 are:

\begin{aligned}(a_{0} − \frac{1}{2})^{2} + (a_{1} − \frac{1}{2})^{2} & = \frac{1}{2} \\ (a_{2} − \frac{1}{2})^{2} + (a_{2} − \frac{1}{2})^{2} & = \frac{1}{2} \\ (a_{0} − \frac{1}{2})^{2} + (a_{3} − \frac{1}{2})^{2} & = \frac{1}{2} \\ (a_{2} − \frac{1}{2})^{2} + (a_{3} − \frac{1}{2})^{2} & = \frac{1}{2} \\ a_{1}^{2} − a_{1} − a_{0}a_{2} & = 0 \\ a_{3}^{2} − a_{3} − a_{0}a_{2} & = 0. \end{aligned}

Now, we are ready to present the algorithm for the solution of our problem:

ALGORITHM:

1. Choose a_{3} ∈ (\frac{1}{−2−2\sqrt{2}}, \frac{1}{−2+2\sqrt{2}}).

2. Find a_{0} = \frac{1}{2} ± \frac{1}{2} \sqrt{1 + 4a_{3} − 4a_{3}^{2}}.

3. Get a_{2} = 1 − a_{0}.

4. Get a_{1} = 1 − a_{3}.

The corresponding scaling function φ can be derived by finding a fixed point of the mapping

Sf(x) = a_{0}f(2x) + a_{1}f(2x − 1) + a_{2}f(2x − 2) + a_{3}f(2x − 3),

by iteration with a reasonable starting function, f^{0}, -i.e.,

φ(x) = lim_{n→∞} S^{n}f^{0}(x).

To install p accuracy condition on wavelets, -i.e., to establish the p vanishing moment properties of wavelets, it is required [2] that

∑(−1)^{k}k^{m}a_{k} = 0,  for m < p.  (2.11)

By (2.10), (2.11) is satisfied with m = 0. Therefore, the algorithm, when a_{3} is taken in the range specified, will generates a family of wavelets whose accuracy order is 1. If we want the second order accuracy in wavelets, then we must also have equation (2.11) with m = 1. In our case, this is

−a_{1} + 2a_{2} − 3a_{3} = 0.  (2.12)

Since a_{1} = 1 − a_{3} and a_{0} = 1 − a_{2}, substituting into (2.12), we obtain 2a_{0} = 1 − 2a_{3}. Replacing a_{0} by \frac{1}{2} ± \frac{1}{2} \sqrt{1 + 4a_{3} − 4a_{3}^{2}} and solving for a_{3}, we obtain a_{3} = \frac{1±\sqrt{3}}{4}. If we take a_{3} = \frac{1−\sqrt{3}}{4}, then the following wavelet is generated by the algorithm;

a_{0} = \frac{1 + \sqrt{3}}{4}, a_{1} = \frac{3 + \sqrt{3}}{4}, a_{2} = \frac{3 − \sqrt{3}}{4}, a_{3} = \frac{1 − \sqrt{3}}{4}.

Of course, this is one of Daubechies wavelets. It is important to note that our approach can be extended to any scaling function that involves four nonzero coefficients. For instance, consider the case;

φ(x) = a_{−1}φ(2x + 1) + a_{0}φ(2x) + a_{1}φ(2x − 1) + a_{2}φ(2x − 2).

Then the algorithm is modified to

1. Choose a_{2} ∈ (\frac{1}{−2−2\sqrt{2}}, \frac{1}{−2+2\sqrt{2}}).

2. Find a_{−1} = \frac{1}{2} ± \frac{1}{2} \sqrt{1 + 4a_{2} − 4a_{2}^{2}}.

3. Get a_{1} = 1 − a_{−1}.

4. Get a_{0} = 1 − a_{2}.

Arguing as before to obtain the second order accuracy in the wavelet, we get once again the coefficients,

a_{−1} = \frac{1 + \sqrt{3}}{4}, a_{0} = \frac{3 + \sqrt{3}}{4}, a_{1} = \frac{3 − \sqrt{3}}{4}, a_{2} = \frac{1 − \sqrt{3}}{4}.

The support of the scaling function is [−1, 2]. Also, we note that choosing a_{2} = 0 and the minus sign for a_{−1} in the algorithm, yields a_{−1} = a_{2} = 0, a_{0} = a_{1} = 1. These values yield the scaling function φ for the classical Haar wavelets.

References

[1] Ingrid Daubechies, Ten Lectures on Wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Phil. PA (1992).

[2] Gilbert Strang, Wavelet transforms versus Fourier transforms,Bull. AMS, Vol. 28, No. 2, (1993), pp. 288-305.

[3] Robert S. Strichartz, How to make wavelets, Monthly of MAA, Vol.100, No.6, June-July (1993), pp. 539-556.