A SCHEME TO ELEVATE THE DEGREE OF BIORTHOGONAL WAVELETS

Wei-Chang Shann ��� Jeng-Nan Tzeng ���

National Central University, Taiwan Dec 16, 1996

• Motivation

• Techniques

• Merits

• Pictures and Algorithms

• Things to Do

CMS Annual Meeting, 1996, NCUE.

\underline{Motivation}

In order to design efficient numerical schemes for the solution of differential equations, especially those with mixed large and small scales of motion, we wish to have a system of basis functions with the nice properties from both sides of finite elements and wavelets. The wish list goes as follows.

• Basis of H_{0}^{1}(0, 1).

• Compactly supported, simply structured.

• Contains low order polynomials (at least locally).

• Easy to localize in both frequency and time domains.

• Fast transformation between high and low resulotions. Last but not least, we wish the basis functions can produce stiffness matrices with with nice condition numbers. Specifically, we wish • The derivatives of the basis functions are orthonormal. This is the frontier.

Developments in this direction

On the side of spline finite elements, there are multigrid and domain decomposition schemes. The former localize in frequency, the later localize in space.

[Xu, Shann, 1992] Used modified anti-derivatives of orthonormal scaling functions and wavelets in place of finite element basis. Contained piecewise linear hierarchical basis (a particular implementation of multigrid) as a special case (when wavelet order p = 1).

[Jawerth, Sweldens, 1993] Derived a scheme to construct specific scaling functions that diagonalize the stiffness matrix corresponding to the elliptic operator \frac{d}{dx}(p(x)\frac{d}{dx}). Contained piecewise linear hierarchical basis as a special case (when coefficient p(x) = 1).

[Chern, Shann, 1994] Derived difference wavelets, lead to a fast direct method for solving linear systems and became an efficient IIR (infinite impulse response) filter. Contained cyclic reduction method as a special case.

[Liandrat, Tchamitchian, 1993], [Ponenti, Liandrat, 1996] Derived biorthogonal Riesz bases from {L^{−1}ψ(x−k)} and {L^{∗}ψ(x−k)}.

\underline{Techniques}

[Xu, Shann, 1992] suggested that

Φ(x) = ∫_{−∞}^{x} ϕ(ξ) − ϕ(ξ − 1) dξ.

In the summer of 1996, Tzeng found

• Φ(x) = χ_{[0,1]}∗ ϕ(x).

• ∑ Φ(x − k) = 1.

• If {ϕ(x−k)} spans polynomials up to degree p, then {Φ(x−k)} spans polynomials up to degree p + 1.

• {Φ(x − k)} forms a Riesz basis and it generates a multiresolution analysis of L^{2}(R).

• The corresponding wavelet Ψ(x) can be derived by following the steps of [Chui, Wang, 1993]. And {Ψ(x − k)} also forms a Riesz basis.

• A biorthogonal system {Φ(x), Ψ(x), Φ̃(x), Ψ̃(x)} can be derived by following the steps of [Cohen, Daubechies, Feauveau, 1992] (CDF).

Techniques (continued)

• It turned out that χ_{[0,1]}∗ Φ̃(x) = ϕ^{}˜ (x), where ϕ^{}˜ = ϕ in the orthonormal case. It explains, as the regularity of Φ is raised by 1, that of Φ̃ is lowered by 1. We saw that in CDF biorthogonal systems.

• With the help of lifting scheme [Sweldens, 1995], the elevation scheme can construct from splines to all CDF biorthogonal systems.

• If we start with spline of order 1, the elevation scheme derives the linear hierarchical basis again.

\underline{Merits}

In Fall 1996, with help from Yen, we noticed

\frac{d}{dx}Ψ(x) = ψ(x).

To sum up with: If the original {ϕ(x), ψ(x)} are orthonormal scaling functions and wavelets with compact supports, then

• Φ(x) and Ψ(x) are in H^{1}(R).

• suppΦ = suppϕ + 1, suppΦ̃ = suppϕ − 1, suppΨ = suppΨ̃ = suppψ.

• The biorthogonal scaling coefficients {h_{k}, g_{k}, h_{k}^{}˜ , g_{k}^{}˜ } are of finite length, and they are simply constructed from the original scaling coefficients {c_{k}}.

• If ψ(x) has p − 1 vanishing moments, Ψ(x) has p.

• the multiresolution analysis structure enables the efficient localization in both time and frequency domains.

Merits (continued)

• The biorthogonal structure enables the O(N) fast algorithm for wavelet decomposition and reconstruction, it is an efficient way to traverse the high and low resolutions.

• The derivatives of Φ(x) are not orthonormal, but

∫ Φ′(x) Φ′(x − k) dx = {…, 0, −1, 2, −1, 0, …}.

• {Ψ′(x − k)} is orthonormal and Ψ′(x) ⊥ Φ′(x).

• The mass matrix is always well conditioned. The compact supportedness of {Φ(x), Ψ(x)} ensures the matrix is sparse.

• The stiffness matrix will be sparse and shall be well conditioned, or easily conditioned by a diagonal conditioner.

• The biorthogonal structure makes easy the change of bases between {Φ_{Jk}}_{k} and {Ψ_{jk}}_{j,k}, therefore simplifies the construction of the stiffness matrix.

Pictures and Algorithms

Daubechies scaling function and wavelet of order p = 1, namely, the characteristic function and the Haar function:

The elevated scaling function and wavelet from those of Daubechies of order p = 1. Similar to the piecewise linear hierarchical basis, and to the difference wavelets of order 1.

Daubechies scaling function of order p = 1 and the lifted wavelet by s(ω) = −i/4 sin ω; same as the CDF (N, N^{}˜ ) = (1, 3) biorthogonal pair.

Lift the orthonormal wavelet of p = 1, then elevate it. Same as the CDF (N, N^{}˜ ) = (2, 2) biorthogonal pair.

Daubechies scaling function and wavelet of order p = 2:

Elevate the orthonormal wavelet of p = 2, now it has the approximation degree of 3. Note that suppϕ = [0, 4], suppψ = [0, 3].

\underline{Algorithm}

Let {c_{k}} be the scaling coefficients of an orthonormal ϕ(x).

h_{k} = \frac{c_{k−1} + c_{k}}{2}

Then {h_{k}} is the scaling coefficients of the elevated Φ(x).

h_{k}^{}˜ = 2c_{k−1} − h_{k−1}^{}^{˜ h_{0}^{}˜ = 0}

Then {h_{k}^{}˜ } is the scaling coefficients of the biorthogonal Φ̃(x).

• The high pass filter coefficients {g_{k}, g_{k}^{}˜ } can be obtained by the normal procedure.

Example

For the Φ(x) elevated from orthonormal wavelets of order 2, the biorthogonal coefficients are:

h_{0} = ^{\frac{1 + \sqrt{3}}{8}}  h_{1} = ^{\frac{2 + \sqrt{3}}{4}}  h_{2} = \frac{3}{4}
h_{3} = \frac{2 − \sqrt{3}}{4}  h_{4} = \frac{1 − \sqrt{3}}{8}
h_{1}^{}˜ = \frac{1 + \sqrt{3}}{2}  h_{2}^{}˜ = 1  h_{3}^{}˜ = \frac{1 − \sqrt{3}}{2}
g_{−2} = −h_{3}^{}˜  g_{−1} = h_{2}^{}˜  g_{0} = −h_{1}^{}˜
g_{−3}^{}˜  = h_{4}  g_{−2}^{}˜  = −h_{3}  g_{−1}^{}˜  = h_{2}
g_{0}^{}˜ = −h_{1}  g_{1}^{}˜ = h_{0}

The wavelet decomposition and reconstruction algorithms can be derived from the following identities (as before).

Φ(x) = ∑ h_{k}Φ(2x − k)
Ψ(x) = ∑ g_{k}Φ(2x − k)
Φ(2x) = ∑ h_{−2k}^{}˜  Φ(x − k) + ∑ g_{−2k}^{}˜  Ψ(x − k)
Φ(2x − 1) = ∑ h_{1−2k}^{}˜  Φ(x − k) + ∑ g_{1−2k}^{}˜  Ψ(x − k)

\underline{Things to Do}

• Numerical experiments on simple test problems to verify the theory.

• Jusitifications of Φ̃(x) and Ψ̃(x) in function spaces.

• To tackle the real problems.

• There seems an algorithm to decompose a signal of length 2n − 1 to the high resolution part of length n+1 and low resolution part of length n− 2. Therefore, there seems a way to design an algorithm to decompose a signal, or image, of any size without modifications of the original signal.

For details, check out the updates of Tzeng’s master paper in http://www.math.ncu.edu.tw/^{}˜ shann/students.html