Definition 7.1:

Multiresolutions. A sequence {V_j}_j∈ of closed subspaces of L²() is a multiresolution approximation if the following six properties are satisfied:

(7.1)

(7.2)

(7.3)

(7.4)

(7.5)

and there exists θ such that {θ(t – n)}_n∈ is a Riesz basis of V₀.

Let us give an intuitive explanation of these mathematical properties. Property (7.1) means that V_j is invariant by any translation proportional to the scale 2^j. As we shall see later, this space can be assimilated to a uniform grid with intervals 2^j, which characterizes the signal approximation at the resolution 2^−j. The inclusion (7.2) is a causality property that proves that an approximation at a resolution 2^−j contains all the necessary information to compute an approximation at a coarser resolution 2^−j–1. Dilating functions in V_j by 2 enlarges the details by 2 and (7.3) guarantees that it defines an approximation at a coarser resolution 2^−j–1. When the resolution 2^−j goes to 0 (7.4) implies that we lose all the details of f and

(7.6)

On the other hand, when the resolution 2^−j goes +∞, property (7.5) imposes that the signal approximation converges to the original signal:

(7.7)

When the resolution 2^−j increases, the decay rate of the approximation error depends on the regularity of f. In Section 9.1.3 we relate this error to the uniform Lipschitz regularity of f.

The existence of a Riesz basis {θ(t – n)}_n∈ of V₀ provides a discretization theorem as explained in Section 3.1.3. The function θ can be interpreted as a unit resolution cell; Section 5.1.1 gives the definition of a Riesz basis. It is a family of linearly independent functions such that there exist B ≥ A > 0, which satisfy

(7.8)

This energy equivalence guarantees that signal expansions over {θ(t – n)}_n∈ are numerically stable. One may verify that the family is a Riesz basis of V_j with the same Riesz bounds A and B at all scales 2^j. Theorem 3.4 proves that {θ(t – n)}_n∈ is a Riesz basis if and only if

(7.9)

Theorem 7.1.

Let {V}^j∈ be a multiresolution approximation and φ be the scaling function having a Fourier transform

(7.12)

Let us denote

The family {φ_{j, n}}_n∈ is an orthonormal basis of V_j for all j ∈ .

Proof.

To construct an orthonormal basis, we look for a function φ ∈ V₀. Thus, it can be expanded in the basis {θ(t – n)}_n∈:

which implies that

where â is a 2π periodic Fourier series of finite energy. To compute â we express the orthogonality of {φ(t – n)}_n∈ in the Fourier domain. Let . For any (n, p) ∈ ²,

(7.13)

Thus, {φ(t – n)}_n∈ is orthonormal if and only if . Computing the Fourier transform of this equality yields

(7.14)

Indeed, the Fourier transform of is , and we proved in (33) that sampling a function periodizes its Fourier transform. The property (7.14) is verified if we choose

We saw in (7.9) that the denominator has a strictly positive lower bound, so â is a 2π periodic function of finite energy.

Theorem 7.2.

Mallat, Meyer. Let φ ∈ L²() bean integrable scaling function. The Fourier series of h[n] = 〈2^−1/2ϕ(t/2), ϕ(t – n)〉 satisfies

(7.29)

and

(7.30)

Conversely, if ĥ(ω) is 2π periodic and continuously differentiable in a neighborhood of ω = 0, if it satisfies (7.29) and (7.30) and if

(7.31)

then

(7.32)

is the Fourier transform of a scaling function ϕ ∈ L²().

Proof.

This theorem is a central result and its proof is long and technical. It is divided in several parts.

Proof of the necessary condition (7.29). The necessary condition is proved to be a consequence of the fact that is orthonormal. In the Fourier domain, (7.14) gives an equivalent condition:

(7.33)

Inserting yields

Since ĥ(ω) is 2π periodic, separating the even and odd integer terms gives

Inserting (7.33) for ω′ = ω/2 and ω′ = ω/2 + π proves that

Proof of the necessary condition(7.30). We prove that ĥ(0) = √2 by showing that . Indeed, we know that . More precisely, we verify that is a consequence of the completeness property (7.5) of multiresolution approximations.

The orthogonal projection of f ∈ L²() on V_j is

(7.34)

Property (7.5) expressed in the time and Fourier domains with the Plancherel formula implies that

(7.35)

To compute the Fourier transform , we denote . Inserting the convolution expression (7.17) in (7.34) yields

The Fourier transform of is . A uniform sampling has a periodized Fourier transform calculated in (33), and thus,

(7.36)

Let us choose . For j > 0 and ω ∈ [–π, π], (7.36) gives . The mean-square convergence (7.35) implies that

Since φ is integrable, is continuous and thus

We now prove that the function φ, having a Fourier transform given by (7.32), is a scaling function. This is divided in two intermediate results.

Proof that is orthonormal. Observe first that the infinite product (7.32) converges and that because (7.29) implies that . The Parseval formula gives

Verifying that is orthonormal is equivalent to showing that

This result is obtained by considering the functions

and computing the limit, as k increases to +∞, of the integrals

First, let us show that I_k[n] = 2πδ[n] for all k ≥ 1. To do this, we divide I_k[n] into two integrals:

Let us make the change of variable ω′ = ω + 2^kπ in the first integral. Since ĥ(ω) is 2π periodic, when p < k, then . When k = p the hypothesis (7.29) implies that

For k > 1, the two integrals of I_k[n] become

(7.37)

Since is 2^kπ periodic we obtain I_k[n] = I_k–1 [n], and by induction I_k[n] = I₁[n]. Writing (7.37) for k = 1 gives

which verifies that I_k[n] = 2πδ[n], for all k ≥ 1.

We shall now prove that . For all ω ∈ ,

The Fatou lemma (A.1) on positive functions proves that

(7.38)

because I_k[0] = 2π for all k ≥ 1. Since

we finally verify that

(7.39)

by applying the dominated convergence theorem (A.1). This requires verifying the upper-bound condition (A.1). This is done in our case by proving the existence of a constant C such that

(7.40)

Indeed, we showed in (7.38) that is an integrable function.

The existence of C > 0 satisfying (7.40) is trivial for |ω| > 2^kπ since . it follows that

Therefore, to prove (7.40) for |ω| ≤ 2^kπ, it is sufficient to show that for ω ∈ [–π, π].

Let us first study the neighborhood of ω = 0. Since ĥ(ω) is continuously differentiable in this neighborhood and since |ĥ(ω)|² ≤ 2 = |ĥ(0)|², the functions |ĥ(ω)|² and log_e |ĥ(ω)|² have derivatives that vanish at ω = 0. It follows that there exists ε > 0 such that

Thus, for |ω| ≤ ε

(7.41)

Now let us analyze the domain |ω| > ε. To do this we take an integer l such that 2^−l π < ε. Condition (7.31) proves that K = inf_{ω∈[–π/2}, _π/2] |ĥ(ω)| > 0, so if |ω| ≤ π,

This last result finishes the proof of inequality (7.40). Applying the dominated convergence theorem (A.1) proves (7.39) and that {φ(t – n)}_n∈ is orthonormal. A simple change of variable shows that {φ_j,n}_n∈ is orthonormal for all j ∈ .

Proof that {V_j}_j∈ is a multiresolution approximation. To verify that φ is a scaling function, we must show that the spaces V_j generated by define a multiresolution approximation. The multiresolution properties (7.1) and (7.3) are clearly true. The causality V_j+1 ⊂ V_j is verified by showing that for any p ∈ ,

This equality is proved later in (7.107). Since all vectors of a basis of V_j+1 can be decomposed in a basis of V_j, it follows that V_j+1 ⊂ V_j.

To prove the multiresolution property (7.4) we must show that any f ∈ L²(R) satisfies

(7.42)

Since is an orthonormal basis of V_j,

Suppose first that f is bounded by A and has a compact support included in [2^J, 2^J]. The constants A and J may be arbitrarily large. It follows that

Applying the Cauchy-Schwarz inequality to 1 × |φ(2^−jt – n)| yields

with S_j = ∪_n∈[n − 2^J–j, n + 2^J–j] for j > J. For , we obviously have 0 for j→ +∞. The dominated convergence theorem (A.1) applied to proves that the integral converges to 0 and thus,

Property (7.42) is extended to any f ∈ L²() by using the density in L²() of bounded function with a compact support, and Theorem A.5.

To prove the last multiresolution property (7.5) we must show that for any f ∈ L²(),

(7.43)

We consider functions f that have a Fourier transform that has a compact support included in [–2^Jπ, 2^Jπ] for J large enough. We proved in (7.36) that the Fourier transform of is

If j < –J, then the supports of are disjoint for different k, so

(7.44)

We have already observed that |φ(ω)| ≤ 1 and (7.41) proves that if ω is sufficiently small then |φ(ω)| ≥ e^−|ω|, so

Since and , one can apply the dominated convergence theorem (A.1), to prove that

(7.45)

The operator is an orthogonal projector, so . With (7.44) and (7.45), this implies that and thus verifies (7.43). This property is extended to any f ∈ L²() by using the density in L²() of functions having compactly supported Fourier transforms and the result of Theorem A.5.

Discrete filters that have transfer functions that satisfy (7.29) are called conjugate mirror filters. As we shall see in Section 7.3, they play an important role in discrete signal processing; they make it possible to decompose discrete signals in separate frequency bands with filter banks. One difficulty of the proof is showing that the infinite cascade of convolutions that is represented in the Fourier domain by the product (7.32) does converge to a decent function in L²(). The sufficient condition (7.31) is not necessary to construct a scaling function, but it is always satisfied in practical designs of conjugate mirror filters. It cannot just be removed as shown by the example ĥ(ω) = cos(3ω/2), which satisfies all other conditions. In this case, a simple calculation shows that φ = 1/3 1_{[–3/2, 3/2]}. Clearly {φ(t – n)}_n∈ is not orthogonal, so φ is not a scaling function. However, the condition (7.31) may be replaced by a weaker but more technical necessary and sufficient condition proved by Cohen [16, 167].

Proof.

Let us prove first that can be written as the product (7.52). Necessarily, ψ(t/2) ∈ W₁ ⊂ V₀. Thus, it can be decomposed in {φ(t – n)}_n∈, which is an orthogonal basis of V₀:

(7.54)

with

(7.55)

The Fourier transform of (7.54) yields

(7.56)

Lemma 7.1 gives necessary and sufficient conditions on for designing an orthogonal wavelet.

Lemma 7.1.

The family {ψ_j,n}_n∈ is an orthonormal basis of W_j if and only if

(7.57)

and

(7.58)

The lemma is proved for j = 0 from which it is easily extended to j ≠ 0 with an appropriate scaling. As in (7.14), one can verify that {ψ(t – n)}_n∈ is orthonormal if and only if

(7.59)

Since and is 2π periodic,

We know that , so (7.59) is equivalent to (7.57).

The space W₀ is orthogonal to V₀ if and only if {ϕ(t – n)}_n∈ and {ψ(t – n)}_n∈ are orthogonal families of vectors. This means that for any n ∈ ,

The Fourier transform of . The sampled sequence is zero if its Fourier series computed with (33) satisfies

(7.60)

By inserting and in this equation, since , we prove as before that (7.60) is equivalent to (7.58).

We must finally verify that V_–1 = V₀ + W₀. Knowing that {√2ϕ(2t – n)}_n∈ is an orthogonal basis of V_–1, it is equivalent to show that for any a[n] ∈ ²() there exist b[n] ∈ ²() and c[n] ∈ ²() such that

(7.61)

This is done by relating and to â(ω). The Fourier transform of (7.61) yields

Inserting and in this equation shows that it is necessarily satisfied if

(7.62)

Let us define

and

When calculating the right side of (7.62), we verify that it is equal to the left side by inserting (7.57), (7.58), and using

(7.63)

Since and are 2π periodic they are the Fourier series of two sequences b[n] and c[n] that satisfy (7.61). This finishes the proof of the lemma.

The formula (7.53)

satisfies (7.57) and (7.58) because of (7.63). Thus, we derive from Lemma 7.1 that is an orthogonal basis of W_j.

We complete the proof of the theorem by verifying that is an orthogonal basis of L²(). Observe first that the detail spaces {W_j}_j∈ are orthogonal. Indeed, W_j is orthogonal to V_j and W_l ⊂ V_l–1 ⊂ V_j for j < l. Thus, W_j and W_l are orthogonal. We can also decompose

(7.64)

Indeed, V_j–1 = W_j ⊕ V_j, and we verify by substitution that for any L > J,

(7.65)

Since {V_j}_j∈ is a multiresolution approximation, V_L and V_J tend, respectively, to L²() and {0} when L and J go, respectively, to –∞ and +∞, which implies (7.64). Therefore, a union of orthonormal bases of all W_j is an orthonormal basis of L²().

The proof of the theorem shows that g is the Fourier series of

(7.66)

which are the decomposition coefficients of

(7.67)

Calculating the inverse Fourier transform of (7.53) yields

(7.68)

This mirror filter plays an important role in the fast wavelet transform algorithm.

Theorem 7.4:

Vanishing Moments. Let ψ and ϕ be a wavelet and a scaling function that generate an orthogonal basis. Suppose that and . The four following statements are equivalent:

Proof.

The decay of |φ(t)| and |ψ(t)| implies that and (ω) are p times continuously differentiable. The k^th-order derivative is the Fourier transform of (–it)^k ψ(t). Thus,

We derive that (1) is equivalent to (2).

Theorem 7.3 proves that

Since , by differentiating this expression we prove that (2) is equivalent to (3).

Let us now prove that (4) implies (1). Since ψ is orthogonal to {φ(t – n)}_n∈, it is also orthogonal to the polynomials q_k for 0 ≤ k < p. This family of polynomials is a basis of the space of polynomials of degree at most p − 1. Thus, ψ is orthogonal to any polynomial of degree p − 1 and in particular to t^k for 0 ≤ k < p. This means that ψ has p vanishing moments.

To verify that (1) implies (4) we suppose that ψ has p vanishing moments, and for k < p, we evaluate q_k(t) defined in (7.70). This is done by computing its Fourier transform:

Let δ^(k) be the distribution that is the k^th-order derivative of a Dirac, defined in Section A.7 in the Appendix. The Poisson formula (2.4) proves that

(7.71)

With several integrations by parts, we verify the distribution equality

(7.72)

where a^k_m,l is a linear combination of the derivatives .

For l ≠ 0, let us prove that a^k_m,l = 0 by showing that if 0 ≤ m < p. For any P > 0, (7.27) implies

(7.73)

Since ψ has p vanishing moments, we showed in (3) that ĥ(ω) has a zero of order p at ω = ±π. But ĥ(ω) is also 2π periodic, so (7.73) implies that in the neighborhood of ω = 2lπ, for any l ≠ 0. Thus,

Since a^k_m,l = 0 and φ(2lπ) = 0 when l ≠ 0, it follows from (7.72) that

The only term that remains in the summation (7.71) is l = 0, and inserting (7.72) yields

The inverse Fourier transform of δ^(m)(ω) is (2π)⁻¹(– it)^m, and Theorem 7.2 proves that . Thus, the inverse Fourier transform q_k of is a polynomial of degree k.

The hypothesis (4) is called the Fix-Strang condition [446]. The polynomials {q_k}_0≤k<p define a basis of the space of polynomials of degree p − 1. The Fix-Strang condition proves that ψ has p vanishing moments if and only if any polynomial of degree p − 1 can be written as a linear expansion of {ϕ(t – n)}_n∈. The decomposition coefficients of the polynomials q_k do not have a finite energy because polynomials do not have a finite energy.

Theorem 7.5.

Compact Support. The scaling function φ has a compact support if and only if h has a compact support and their supports are equal. If the support of h and φ is [N₁, N₂], then the support of ψ is [(N₁ – N₂ + 1)/2, (N₂ – N₁ + 1)/2].

Proof.

If φ has a compact support, since

we derive that h also has a compact support. Conversely, the scaling function satisfies

(7.74)

If h has a compact support then one can prove [194] that ϕ has a compact support. The proof is not reproduced here.

To relate the support of ϕ and h, we suppose that h[n] is nonzero for N₁ ≤ n ≤ N₂ and that ϕ has a compact support [K₁, K₂]. The support of ϕ(t/2) is [2K₁, 2K₂]. The sum at the right of (7.74) is a function with a support of [N₁ + K₁, N₂ + K₂]. The equality proves that the support of ϕ is [K₁, K₂] = [N₁, N₂].

Let us recall from (7.68) and (7.67) that

If the supports of ϕ and h are equal to [N₁, N₂], the sum on the right side has a support equal to [N₁ – N₂ + 1, N₂ – N₁ + 1]. Thus, ψ has a support equal to [(N₁ – N₂ + 1)/2, (N₂ – N₁ + 1)/2].

If h has a finite impulse response in [N₁, N₂], Theorem 7.5 proves that ψ has a support of size N₂ – N₁ centered at 1/2. To minimize the size of the support, we must synthesize conjugate mirror filters with as few nonzero coefficients as possible.

Proof.

This result is proved by showing that there exist C₁ > 0 and C₂ > 0 such that for all ω ∈

(7.76)

(7.77)

The Lipschitz regularity of ϕ and ψ is then derived from Theorem 6.1, which shows that if , then f is uniformly Lipschitz α.

We proved in (7.32) that . One can verify that

thus,

(7.78)

Let us now compute an upper bound for . At ω = 0, we have ĥ(0) = √2 so . Since ĥ(ω) is continuously differentiable at ω = 0, is also continuously differentiable at ω = 0. Thus, we derive that there exists ε > 0 such that if |ω| < ε, then . Consequently,

(7.79)

If |ω| > ε, there exists J ≥ 1 such that 2^J–1 ε ≤ |ω| ≤ 2^J ε, and we decompose

(7.80)

Since , inserting (7.79) yields for |ω| > ε

(7.81)

Since 2^J ≤ ε⁻¹ 2|ω|, this proves that

Equation (7.76) is derived from (7.78) and this last inequality. Since , (7.77) is obtained from (7.76).

This theorem proves that if B < 2^p–1, then α₀ > 0. It means that ϕ and ψ are uniformly continuous. For any m > 0, if B < 2^p–1–m, then α₀ > m, so ψ and ϕ are m times continuously differentiable. Theorem 7.4 shows that the number p of zeros of ĥ(ω) at π is equal to the number of vanishing moments of ψ. A priori, we are not guaranteed that increasing p will improve the wavelet regularity since B might increase as well. However, for important families of conjugate mirror filters such as splines or Daubechies filters, B increases more slowly than p, which implies that wavelet regularity increases with the number of vanishing moments. Let us emphasize that the number of vanishing moments and the regularity of orthogonal wavelets are related but it is the number of vanishing moments and not the regularity that affects the amplitude of the wavelet coefficients at fine scales.

Theorem 7.7.

Daubechies. A real conjugate mirror filter h, such that ĥ(ω) has p zeroes at ω = π, has at least 2p nonzero coefficients. Daubechies filters have 2p nonzero coefficients.

Proof.

The proof is constructive and computes Daubechies filters. Since h[n] is real, |ĥ(ω)|² is an even function and can be written as a polynomial in cos ω. Thus, |R(e ^−iw)|² defined in (7.91) is a polynomial in cos ω that we can also write as a polynomial P(sin² (ω/2)),

(7.93)

The quadrature condition (7.92) is equivalent to

(7.94)

for any y = sin²(ω/2) ∈[0, 1]. To minimize the number of nonzero terms of the finite Fourier series ĥ(ω), we must find the solution P(y) ≥ 0 of minimum degree, which is obtained with the Bezout theorem on polynomials.

Theorem 7.8.

Bezout. Let Q₁(y) and Q₂(y) be two polynomials of degrees n₁ and n₂ with no common zeroes. There exist two unique polynomials P₁(y) and P₂(y) of degrees n₂ − 1 and n₁ − 1 such that

(7.95)

The proof of this classical result is in [19]. Since Q₁(y) = (1 – y)^p and Q₂(y) = y^p are two polynomials of degree p with no common zeros, the Bezout theorem proves that there exist two unique polynomials P₁ (y) and P₂ (y) such that

The reader can verify that P₂(y) = P₁(1 – y) = P(1 – y) with

(7.96)

Clearly, P(y) ≥ 0 for y ∈ [0, 1]. Thus, P(y) is the polynomial of minimum degree satisfying (7.94) with P(y) ≥ 0.

Now we need to construct a minimum-degree polynomial

such that |R(e ^−iω)|² = P(sin²(ω/2)). Since its coefficients are real, R* (e ^−iω) = R(e^iω), and thus,

(7.97)

This factorization is solved by extending it to the whole complex plane with the variable z = e ^−iw:

(7.98)

Let us compute the roots of Q(z). Since Q(z) has real coefficients if c_k is a root, then c*_k is also a root, and since it is a function of z + z⁻¹ if c_k is a root, then 1/c_k and thus 1/c*_k are also roots. To design R(z) that satisfies (7.98), we choose each root a_k of R(z) among a pair (c_k, 1/c_k) and include a*_k as a root to obtain real coefficients. This procedure yields a polynomial of minimum degree m = p − 1, with r²₀ = Q(0) = P(1/2) = 2^p–1. The resulting filter h of minimum size has N = p + m + 1 = 2p nonzero coefficients.

Among all possible factorizations, the minimum-phase solution R(e^iω) is obtained by choosing a_k among (c_k, 1/c_k) to be inside the unit circle |a_k| ≤ 1 [51]. The resulting causal filter h has an energy maximally concentrated at small abscissa n ≥ 0. It is a Daubechies filter of order p.

The constructive proof of this theorem synthesizes causal conjugate mirror filters of size 2p. Table 7.2 gives the coefficients of these Daubechies filters for 2 ≤ p ≤ 10. Theorem 7.9 derives that Daubechies wavelets calculated with these conjugate mirror filters have a support of minimum size.

Table 7.2 Daubechies Filters for Wavelets with p Vanishing Moments

	n	hp[n]
p = 2	0	0.482962913145
	1	0.836516303738
	2	0.224143868042
	3	−0.129409522551
p = 3	0	0.332670552950
	1	0.806891509311
	2	0.459877502118
	3	−0.135011020010
	4	−0.085441273882
	5	0.035226291882
p = 4	0	0.230377813309
	1	0.714846570553
	2	0.630880767930
	3	−0.027983769417
	4	−0.187034811719
	5	0.030841381836
	6	0.032883011667
	7	−0.010597401785
p = 5	0	0.160102397974
	1	0.603829269797
	2	0.724308528438
	3	0.138428145901
	4	−0.242294887066
	5	−0.032244869585
	6	0.077571493840
	7	−0.006241490213
	8	−0.012580751999
	9	0.003335725285
p = 6	0	0.111540743350
	1	0.494623890398
	2	0.751133908021
	3	0.315250351709
	4	−0.226264693965
	5	−0.129766867567
	6	0.097501605587
	7	0.027522865530
	8	−0.031582039317
	9	0.000553842201
	10	0.004777257511
	11	−0.001077301085
p = 7	0	0.077852054085
	1	0.396539319482
	2	0.729132090846
	3	0.469782287405
	4	−0.143906003929
	5	−0.224036184994
	6	0.071309219267
	7	0.080612609151
	8	−0.038029936935
	9	−0.016574541631
	10	0.012550998556
	11	0.000429577973
	12	−0.001801640704
	13	0.000353713800
p = 8	0	0.054415842243
	1	0.312871590914
	2	0.675630736297
	3	0.585354683654
	4	−0.015829105256
	5	−0.284015542962
	6	0.000472484574
	7	0.128747426620
	8	−0.017369301002
	9	−0.04408825393
	10	0.013981027917
	11	0.008746094047
	12	−0.004870352993
	13	−0.000391740373
	14	0.000675449406
	15	−0.000117476784
p = 9	0	0.038077947364
	1	0.243834674613
	2	0.604823123690
	3	0.657288078051
	4	0.133197385825
	5	−0.293273783279
	6	−0.096840783223
	7	0.148540749338
	8	0.030725681479
	9	−0.067632829061
	10	0.000250947115
	11	0.022361662124
	12	−0.004723204758
	13	−0.004281503682
	14	0.001847646883
	15	0.000230385764
	16	−0.000251963189
	17	0.000039347320
p = 10	0	0.026670057901
	1	0.188176800078
	2	0.527201188932
	3	0.688459039454
	4	0.281172343661
	5	−0.249846424327
	6	−0.195946274377
	7	0.127369340336
	8	0.093057364604
	9	−0.071394147166
	10	−0.029457536822
	11	0.033212674059
	12	0.003606553567
	13	−0.010733175483
	14	0.001395351747
	15	0.001992405295
	16	−0.000685856695
	17	−0.000116466855
	18	0.000093588670
	19	−0.000013264203

Theorem 7.9.

Daubechies. If ψ is a wavelet with p vanishing moments that generates an orthonormal basis of L²(), then it has a support of size larger than or equal to 2p − 1. A Daubechies wavelet has a minimum-size support equal to [–p + 1, p]. The support of the corresponding scaling function ϕ is [0, 2p − 1].

This theorem is a direct consequence of Theorem 7.7. The support of the wavelet, and that of the scaling function, are calculated with Theorem 7.5. When p = 1 we get the Haar wavelet. Figure 7.10 displays the graphs of ϕ and ψ for p = 2, 3, 4.

The regularity of ϕ and ψ is the same since ψ(t) is a finite linear combination of ϕ(2t – n). However, this regularity is difficult to estimate precisely. Let B = sup_ω∈ |R(e ^−iω)| where R(e ^−iω) is the trigonometric polynomial defined in (7.91). Theorem 7.6 proves that ψ is at least uniformly Lipschitz α for α < p – log₂ B − 1. For Daubechies wavelets, B increases more slowly than p, and Figure 7.10 shows indeed that the regularity of these wavelets increases with p. Daubechies and Lagarias [198] have established a more precise technique that computes the exact Lipschitz regularity of ψ. For p = 2 the wavelet ψ is only Lipschitz 0.55, but for p = 3 it is Lipschitz 1.08, which means that it is already continuously differentiable. For p large, ϕ and ψ are uniformly Lipschitz α, for α of the order of 0.2 p [168].

Theorem 7.10:

Mallat. At the decomposition,

(7.102)

(7.103)

At the reconstruction,

(7.104)

Proof of (7.102).

Any can be decomposed in the orthonormal basis {ϕ_{j, n}}_n∈ of V_j:

(7.105)

With the change of variable t′ = 2^−jt − 2p, we obtain

(7.106)

Thus, (7.105) implies that

(7.107)

Computing the inner product of f with the vectors on each side of this equality yields (7.102).

Proof of (7.103).

Since , it can be decomposed as

As in (7.106), the change of variable t′ = 2^−jt − 2p proves that

(7.108)

and thus,

(7.109)

Taking the inner product with f on each side gives (7.103).

Proof of (7.104).

Since W_j+1 is the orthogonal complement of V_j+1 in V_j, the union of the two bases {ψ_{j + 1, n}}_n∈ and {ϕ_{j + 1, n}}_n∈ is an orthonormal basis of V_j. Thus, any ϕ_{j, p} can be decomposed in this basis:

Inserting (7.106) and (7.108) yields

Taking the inner product with f on both sides of this equality gives (7.104).

Theorem 7.10 proves that a_j+1 and d_j+1 are computed by taking every other sample of the convolution of a_j with and , respectively, as illustrated by Figure 7.12. The filter removes the higher frequencies of the inner product sequence a_j, whereas is a high-pass filter that collects the remaining highest frequencies. The reconstruction (7.104) is an interpolation that inserts zeroes to expand a_j+1 and d_j+1 and filters these signals, as shown in Figure 7.12.

An orthogonal wavelet representation of a_L = 〈f, ϕ_{L, n}〉 is composed of wavelet coefficients of f at scales 2^L < 2^j ≤ 2^J, plus the remaining approximation at the largest scale 2^J:

(7.110)

It is computed from a_L by iterating (7.102) and (7.103) for L ≤ j < J. Figure 7.7 gives a numerical example computed with the cubic spline filter of Table 7.1. The original signal a_L is recovered from this wavelet representation by iterating the reconstruction (7.104) for J > j ≥ L.

Theorem 7.11:

Vetterli. The filter bank performs an exact reconstruction for any input signal if and only if

(7.116)

and

(7.117)

Proof.

We first relate the Fourier transform of a₁ and d₁ to the Fourier transform of a₀. Since h and g are real, the transfer functions of and are, respectively, and . By using (7.114), we derive from the definition (7.112) of a₁ and d₁ that

(7.118)

(7.119)

The expression (7.113) of ã₀ and the zero insertion property (7.115) also imply

(7.120)

Thus,

To obtain a₀ = ã₀ for all a₀, the filters must cancel the aliasing term â₀(ω + π) and guarantee a unit gain for â₀(ω), which proves equations (7.116) and (7.117).

Theorem 7.11 proves that the reconstruction filters and are entirely specified by the decomposition filters h and g. In matrix form, it can be rewritten

(7.121)

The inversion of this 2 × 2 matrix yields

(7.122)

where Δ(ω) is the determinant

(7.123)

The reconstruction filters are stable only if the determinant does not vanish for all ω ∈ [–π, π]. Vaidyanathan [469] has extended this result to multirate filter banks with an arbitrary number M of channels by showing that the resulting matrices of filters satisfy paraunitary properties [68].

Theorem 7.12.

Perfect reconstruction filters satisfy

(7.124)

For finite impulse-response filters, there exist a ∈ and l ∈ such that

(7.125)

Proof.

Equation (7.122) proves that

(7.126)

Thus,

(7.127)

The definition (7.123) implies that Δ(ω + π) = –Δ(ω). Inserting (7.127) in (7.117) yields (7.124).

The Fourier transform of finite impulse-response filters is a finite series in exp(± inω). Therefore, the determinant Δ(ω) defined by (7.123) is a finite series. Moreover, (7.126) proves that Δ⁻¹ (ω) must also be a finite series. A finite series in exp(± inω) that has an inverse that is also a finite series must have a single term. Since Δ(ω) = –Δ(ω + π) the exponent n must be odd. This proves that there exist l ∈ and a ∈ such that

(7.128)

Inserting this expression in (7.126) yields (7.125).

The factor a is a gain that is inverse for the decomposition and reconstruction filters and l is a reverse shift. We generally set a = 1 and l = 0. In the time domain (7.125) can then be rewritten as

(7.129)

The two pairs of filters (h, g) and (, ) play a symmetric role and can be inverted.

Proof.

To prove that these families are biorthogonal we must show that for all n ∈

(7.135)

(7.136)

and

(7.137)

For perfect reconstruction filters, (7.124) proves that

In the time domain, this equation becomes

(7.138)

which verifies (7.135). The same proof as for (7.124) shows that

In the time domain, this equation yields (7.136). It also follows from (7.122) that

and

The inverse Fourier transforms of these two equations yield (7.137).

To finish the proof, one must show the existence of Riesz bounds. The reader can verify that this is a consequence of the fact that the Fourier transform of each filter is bounded.