Back
 JAMP  Vol.9 No.2 , February 2021
Chebyshev Biorthogonal Multiwavelets and Approximation
Abstract: In this paper, we construct Chebyshev biorthogonal multiwavelets, and use this multiwavelets to approximate signals (functions). The convergence rate for signal approximation is derived. The fast signal decomposition and reconstruction algorithms are presented. The numerical examples validate the theoretical analysis.

1. Introduction

Since 1988 the wavelet theory has been applied in several fields of science and industry, for instance, in signal processing, image processing, and numerical analysis [1] - [6]. However, the multiwavelets theory and application are less developed. For instance, some authors use Legendre wavelets or Chebyshev wavelets to solve the differential equations [7] [8] [9] [10]. But these wavelets do not have the property of vanishing moments, which is characteristic for wavelets. Actually, they are multiscaling functions of the Legendre multiwavelets [11] [12] or Chebyshev multiwavelets in the following. Besides, there are not fast decomposition and reconstruction algorithm for approximating a function. Recently the biorthogonal Jacobi multiwavelet basis for the weighted space L ω 2 ( [ 0,1 ] ) is defined, and applied to solve a class of prototypical initial and boundary value problems of fractional differential equations of general order [13]. The complete approximating algorithm is not presented in this paper.

The purpose of this paper is to define Chebyshev biorthogonal multiscaling functions and multiwavelet functions based on Chebyshev polynomials. Although Chebyshev polynomials can be considered a special case of Jacobi polynomials P n ( α , β ) with α = β = 1 2 , they need to be treated independently since usually the condition ( n + α + β ) is imposed on Jacobi polynomials P n ( α , β ) [13]. We will also provide the approximation method for signals (functions) by using the multiscaling functions and wavelets, which is essential to a complete decomposition algorithm. Using the same framework one may construct other biorthogonal multiwavelets based on some orthogonal polynomials like Laguerre polynomials and Hermite polynomials, etc.

The remainder of this paper is organized as follows: We construct Chebyshev biorthogonal multiwavelets in Section 2, and derive the convergence rate for the projection of a signal (function) on the subspace V n of L ω 2 ( [ 0,1 ] ) and the computation formula in Section 3. Finally we give the numerical examples and conclusion remarks in Section 4.

2. Chebyshev Biorthogonal Multiwavelets

We will define Chebyshev multiscaling functions and multiwavelets, and obtain two approximations to the functions in the weighted space L ω 2 ( [ 0,1 ] ) , which can be converted each other by the fast decomposition and reconstruction algorithms.

2.1. Chebyshev Multiscaling Functions

Classical Chebyshev polynomials can be defined by the formula

T n ( x ) = cos ( n ( arccos ( x ) ) ) , x [ 1,1 ] ( n = 0,1,2, ) (1)

They are orthogonal with respect to the weight function ( 1 x 2 ) 1 2 on the interval [ 1,1 ] :

1 1 T i ( x ) T j ( x ) ( 1 x 2 ) 1 2 d x = 0, i j . (2)

T n ( x ) is a polynomial of order n, and is the one among all polynomials of order n with leading coefficient 2 n 1 which has the minimal error to zero max 1 x 1 | T n ( x ) 0 | . It has all its zeros in the interval [ 1,1 ] :

x k = cos 2 k 1 2 n π , k = 1 , 2 , , n . (3)

We define Chebyshev multiscaling functions by

φ m ( x ) : = { T m 1 ( α , β ) ( 2 x 1 ) / γ m 1 , x [ 0 , 1 ] , 0 , x [ 0 , 1 ] , m 1 (4)

where

γ 0 = π , γ n = π 2 , n 1. (5)

then { φ m ( x ) } m = 1 are orthonormal with respect to the weight function ω ( x ) = [ ( 1 x ) x ] 1 2 :

0 1 φ i ( x ) φ j ( x ) ω ( x ) d x = δ i j . (6)

If we denote for m 1

p i m : = m 2 γ m 1 j = 0 [ m i 2 ] ( m j j ) ( m 2 j j ) 2 m 2 j + i , (7)

then the polynomials φ m ( x ) can be expressed by

φ m ( x ) = i = 0 m 1 p i m x i . (8)

Let r 1 be an integer, then the first r multiscaling functions φ 1 , φ 2 , , φ r form an orthonormal base of the function space

V 0 = span { φ 1 , φ 2 , , φ r } (9)

which is composed of all linear combination of the functions φ 1 , φ 2 , , φ r .

For an integer j 0 , and for k = 0 , 1 , , 2 j 1 , we denote φ j k m ( x ) the dilates and translates of φ m ( x )

φ j , k m ( x ) : = 2 j / 2 φ m ( 2 j x k ) ( 1 m r ) (10)

which is supported on the interval I j , k : = [ k 2 j , k + 1 2 j ] [ 0 , 1 ] . We define the function space

V j , k : = span { φ j , k 1 , φ j , k 2 , , φ j , k r } , (11)

then φ j , k 1 , φ j , k 2 , , φ j , k r form an orthonormal base of this space with respect to the inner product , j , k which is defined by

f , g j , k : = I j , k f ( x ) g ( x ) ω ( 2 j x k ) d x . (12)

Furthermore, we define a function space

V j : = V j , 0 V j , 1 V j , 2 j 1 (13)

where denotes the orthogonal direct sum, and an inner product , j on V j as following:

f , g j : = k = 0 2 j 1 f k , g k j , k , (14)

where f k , g k V j , k and f ( x ) = k = 0 2 j 1 f k ( x ) , g ( x ) = k = 0 2 j 1 g k ( x ) , then the functions { φ j , k m ( x ) , k = 0 , 1 , , 2 j 1 ; m = 1 , 2 , , r } form an orthonormal base of V j , and any f ( x ) V j can be expressed as

f ( x ) = k = 0 2 j 1 m = 1 r c j , k m φ j , k m ( x ) = k = 0 : 2 : 2 j 2 m = 1 r ( c j , k m φ j , k m ( x ) + c j , k + 1 m φ j , k + 1 m ( x ) ) . (15)

2.2. Chebyshev Multiwavelet Functions

Since V 0 V 1 , we denote W 0 the orthonormal complement of V 0 in V 1 , V 1 = V 0 W 0 , then an orthonormal base ψ 1 , ψ 2 , , ψ r of W 0 can be constructed by the Gram-Schmidt process [1] [2]. These functions are called Chebyshev multiwavelet functions, they have r vanishing moments:

0 1 ψ m ( x ) x i d x = 0 , i = 0 , 1 , , r 1 ( m = 1 , 2 , , r ) . (16)

Let g m , i = φ 1 , 0 m , φ i ω , g m , r + i = φ 1 , 0 m , ψ i ω , g r + m , i = φ 1 , 1 m , φ i ω , g r + m , r + i = φ 1 , 1 m , ψ i ω ( i = 1 , , r ) , then we have

φ 1 , 0 m ( x ) = i = 1 r g m , i φ i ( x ) + i = 1 m g m , r + i ψ i ( x ) , φ 1 , 1 m ( x ) = i = 1 r g r + m , i φ i ( x ) + i = 1 m g r + m , r + i ψ i ( x ) , ( m = 1 , 2 , , r ) . (17)

Following the line of (10)-(14), we denote ψ j , k m ( x ) the dilates and translates of ψ m ( x ) , the support of ψ j , k m is I j , k , and then we define the function spaces W j , k and W j . It follows that the functions { ψ j k m ( x ) , k = 0 , 1 , , 2 j 1 ; m = 1 , 2 , , r } form an orthonormal base of W j with respect to the inner product , j .

Equation (17) can be easily generalized to the equations for integers j 1 :

φ j k m = i = 1 r g m , i φ j 1 , k / 2 i + i = 1 m g m , r + i ψ j 1 , k / 2 i φ j , k + 1 m = i = 1 r g r + m , i φ j 1 , k / 2 i + i = 1 m g r + m , r + i ψ j 1 , k / 2 i ( k = 0 , 2 , , 2 j 2 ; m = 1 , 2 , , r ) (18)

Conversely, we have the dilation equations

φ j , k i = m = 1 r h i , m φ j + 1 , 2 k m + m = 1 r h i , r + m φ j + 1 , 2 k + 1 m ψ j , k i = m = 1 r h r + i , m φ j + 1 , 2 k m + m = 1 r h r + i , r + m φ j + 1 , 2 k + 1 m ( k = 0 , 1 , , 2 j 1 ; i = 1 , 2 , , r ) (19)

The above two Equations (18)-(19) mean that V j = V j 1 W j 1 for any j 1 , and any function f ( x ) V j as in (15) can also be expressed as

f ( x ) = k = 0 2 j 1 1 i = 1 r ( c j 1 , k i φ j 1 , k i ( x ) + d j 1 , k i ψ j 1 , k i ( x ) ) . (20)

We have decomposition algorithm by (18)

c j 1 , k i = m = 1 r ( g m , i c j , 2 k m + g r + m , i c j , 2 k + 1 m ) d j 1 , k i = m = 1 r ( g m , r + i c j , 2 k m + g r + m , r + i c j , 2 k + 1 m ) ( k = 0 , 1 , , 2 j 1 1 ; i = 1 , 2 , , r ) (21)

and the reconstruction algorithm by (19)

c j k m = i = 1 r ( h i , m c j 1 , k / 2 i + h r + i , m d j 1 , k / 2 i ) c j , k + 1 m = i = 1 r ( h i , r + m c j 1 , k / 2 i + h r + i , r + m d j 1 , k / 2 i ) ( k = 0 , 2 , , 2 j 2 ; m = 1 , 2 , , r ) (22)

From V j = V j 1 W j 1 , j 1 , we inductively obtain

V n = V 0 W 0 W 1 W n 1 . (23)

For a function f L ω 2 ( [ 0,1 ] ) , its orthogonal projection Q n r f on V n can be expanded in the orthonormal bases { φ n k i ( x ) } :

( Q n r f ) ( x ) = k = 0 2 n 1 m = 1 r c n , k m φ n , k m ( x ) = k = 0 2 n 1 m = 1 r f , φ n , k m n , k φ n , k m ( x ) (24)

By virtue of (23), it can also be expanded in the multiwavelet bases { φ i } i = 1 r j = 0 n 1 { ψ j , k i , k = 0 , 1 , , 2 j 1 , i = 1 , , r } ( ψ 0 , 0 i = ψ i ) :

( Q n r f ) ( x ) = i = 1 r c 0 , 0 i φ i ( x ) + j = 0 n 1 k = 0 2 j 1 i = 1 r d j , k i ψ j , k i ( x ) . (25)

As in [13], a biorthogonal dual bases { ψ ˜ j , k m ( x ) , j = 1 , 0 , , n 1 ; k = 0 , 1 , , 2 j 1 ; m = 1 , , r } (where ψ ˜ 1 , k m : = φ ˜ 0 , 0 m ) to the Chebyshev multiwavelet bases { φ i } i = 1 r j = 1 n 1 { ψ j , k i , k = 0 , 1 , , 2 j 1 , i = 1 , , r } of V n with respect to the inner product , n can be defined. Therefore the expansion (25) can be reformulated as

( Q n r f ) ( x ) = i = 1 r f , φ ˜ 0 , 0 i n φ i ( x ) + j = 1 n 1 k = 0 2 j 1 i = 1 r f , ψ ˜ j , k i n ψ j , k i ( x ) . (26)

3. The Function Approximation Error in L ω 2 ( [ 0 , 1 ] )

Let L ω 2 ( [ 0,1 ] ) be the weighted function space defined with inner product and norm

u , v ω = 0 1 u ( x ) v ( x ) ω ( x ) d x , u ω = u , u ω 1 / 2 . (27)

For a function f L ω 2 ( [ 0,1 ] ) , a positive integer r, and n = 0 , 1 , 2 , , we define the orthogonal projection Q n r f of f (with respect to inner product , n as defined in (14)) onto V n by the formula

( Q n r f ) ( x ) = k = 0 2 n 1 m = 1 r c n , k m φ n , k m ( x ) = k = 0 2 n 1 m = 1 r f , φ n , k m n , k φ n , k m ( x ) (28)

The projection Q n r f converges (in the mean) to f as n . If the function f is serval times differentiable, we can bound the error, as established by the following lemma.

Theorem 3.1 Suppose that the function f : [ 0,1 ] is r times differentiable, f C r ( [ 0,1 ] ) . Then Q n r f approximates f with error bounded as follows:

Q n r f f ω 2 r n 2 π 4 r r ! sup x [ 0,1 ] | f ( r ) ( x ) | (29)

Proof. We divide the interval [ 0,1 ] into subintervals { I n , k } , the restriction of Q n r f to one such subinterval I n , k is the polynomial of degree less than r that approximates f with minimal mean error. We then use the maximum error estimate for the polynomial which interpolates f at Chebyshev nodes of order r on I n , k . We define I n , k = [ 2 n k ,2 n ( k + 1 ) ] for k = 0 , 1 , , 2 n 1 , and obtain

Q n r f f ω 2 = 0 1 [ ( Q n r f ) ( x ) f ( x ) ] 2 ω ( x ) d x = k = 0 2 n 1 I n , k [ ( Q n r f ) ( x ) f ( x ) ] 2 ω ( x ) d x k = 0 2 n 1 I n , k [ ( S n , k r f ) ( x ) f ( x ) ] 2 ω ( x ) d x k = 0 2 n 1 I n , k ( 2 1 r n 4 r r ! sup x [ 0,1 ] | f ( r ) ( x ) | ) 2 ω ( x ) d x ( 2 1 r n 4 r r ! sup x [ 0,1 ] | f ( r ) ( x ) | ) 2 0 1 x 1 2 ( 1 x ) 1 2 d x

and by taking square roots we have the bound (29). Here S n , k r f denotes the polynomial of degree r, which agrees with f at the Chebyshev nodes of order r on I n , k , and we have used the well-known maximum error bound for Chebyshev interpolation (see [1] ).

The number of coefficients in the expressions (24) or (25) is 2 n r , thus the above theorem predicts a convergence rate r for the approximation Q n r f ( x ) if f ( x ) is sufficiently smooth. Besides, this convergence rate can be achieved by using the polynomial S n , k r f from above proof. The Chebyshev nodes of order r for φ r + 1 ( x ) on [0, 1] are (see (3)-(4))

x i = cos 2 2 i 1 4 r π , i = 1 , 2 , , r . (30)

Then the nodes on the interval I n , k are ( x i + k ) / 2 n . Plugging them into

S n , k r f ( x ) = m = 1 r c n , k m φ n , k m ( x ) = 2 n 2 m = 1 r c n , k m φ m ( 2 n x k )

leads to the linear system of equations

m = 1 r φ m ( x i ) c n , k m = 2 n 2 f ( x i + k 2 n ) , i = 1 , 2 , , r . (31)

Let A = ( φ m ( x i ) ) be the r × r coefficient matrix, which is independent of k. Therefore, the cost for calculating all coefficients { c n , k m } of (28) is only O ( 2 n r ) as n . Then the coefficients of multiwavelet expansion (25) are obtained from the decomposition algorithm (21).

Table 1. Numerical error results for Example 1.

Table 2. Numerical error results for Example 2.

4. Numerical Examples and Conclusion

We present some numerical examples and give the conclusions in this last section.

Example 4.1 We take f ( x ) = 1 + x + cos x , which is a smooth function. For illustration we fix r = 3 or r = 5 , and compute Q n r f ( x ) for n = 0 , 1 , 2 , 3 , 4 , 5 . The numerical results are summarized in Table 1. The convergence rate on this table is defined by the formula

Cvge . rate = log ( f Q n 1 r f L 2 ( [ 0 , 1 ] ) f Q n r f L 2 ( [ 0 , 1 ] ) ) / log ( 2 ) (32)

We see in the table clearly that Cvge. rates are close to 3.00 for r = 3 and 5.00 for r = 5 . This result is in accordance with the error estimates of Theorem 3.1 since when the signal f(x) is smooth, Theorem 3.1 predicts a convergence rate of r = 3 or r = 5 .

Example 4.2 We take f ( x ) = e x + x 2 x 5 2 , fix r = 2 or r = 3 , and compute Q n r f ( x ) for n = 0 , 1 , 2 , 3 , 4 , 5 . The numerical results are summarized in Table 2, which is in accordance with the error estimates of Theorem 3.1 since the signal f(x) is only two times differentiable, the convergence rate is less than r if r > 2 .

5. Concluding Remarks

In this paper we defined Chebyshev biorthogonal multiwavelet basis for the weighted space L ω 2 ( [ 0,1 ] ) , and showed how to use this basis to approximate functions. The algorithm is efficient, accurate and stable. Thus we set a foundation for its further applications in numerical methods for partial differential equations. As well-known, when the multiwavelets are applied instead of multiscaling functions (or wavelets as named in several papers), the resulting linear system of algebraic equations will have a bounded condition number ( [14] [15] ). Other applications may include signal processing and computational geometry.

Funding

This work is subsidized by Tan Kah Kee College scientific research incubation project 2018L06.

Acknowledgements

The author wishes to express the sincere thanks to the anonymous referees for valuable suggestions that helped improve the quality of this paper.

Cite this paper: Zhou, X. and Lin, Q. (2021) Chebyshev Biorthogonal Multiwavelets and Approximation. Journal of Applied Mathematics and Physics, 9, 233-241. doi: 10.4236/jamp.2021.92017.
References

[1]   Albert, B.K. (1993) A Class of Basis in L2 for the Sparse Representation of Integral Operators. SIAM Journal on Mathematical Analysis, 24, 246-262.
https://doi.org/10.1137/0524016

[2]   Alpert, B., Beylkin, G., Gines, D. and Vozovoi, L. (2002) Adaptive Solution of Partial Differential Equations in Multiwavelet Basis. Journal of Computational Physics, 182, 149-190.
https://doi.org/10.1006/jcph.2002.7160

[3]   Chen, Z. and Wu, B. (2007) Wavelet Analysis. Science Press, Beijing.

[4]   Daubechis, I. (1992) Ten Lectures on Wavelets. Book Code: CB61, CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics, Philadelphia.
https://doi.org/10.1137/1.9781611970104

[5]   Mallat, S. (1999) A Wavelet Tour of Signal Processing. 2nd Edition, Academic Press, Cambridge.
https://doi.org/10.1016/B978-0-12-466606-1.X5000-4

[6]   Shapiro, J.M. (1993) Embedded Image Coding Using Zerotrees of Wavelet Coefficients. IEEE Trans on Signal Processing, 41, 3445-3462.
https://doi.org/10.1109/78.258085

[7]   Heydari, M.H., Hooshmandsl, M.R., and Maalek Ghaini, F.M. (2014) A New Approach of the Chebyshev Wavelets Method for Partial Differential Equations with Boundary Conditions of the Telegraph Type. Applied Mathematical Modeling, 38, 1597-1606.
https://doi.org/10.1016/j.apm.2013.09.013

[8]   Li, Y.L. (2010) Solving a Nonlinear Fractional Differential Equation Using Chebyshev Wavelets. Communications in Nonlinear Science and Numerical Simulation, 15, 2284-2292.
https://doi.org/10.1016/j.cnsns.2009.09.020

[9]   Mohammadi, F., Hosseini, M.M. and Mohyud-Din, S.T. (2011) Legendre Wavelet Galerkin Method for Solving Ordinary Differential Equations with Non-Analytic Solution. International Journal of Systems Science, 42, 579-585.
https://doi.org/10.1080/00207721003658194

[10]   Wei, X.H., Li, X.N., Feng, J.T. and Zhang, Q.M. (2016) Numerical Solution of Nonlinear Age-Structured Population Models by Chebyshev Wavelets. Mathematics in Practice and Theory, 46, 176-181.

[11]   Ling, J. (1998) Regularization-Wavelet Method for Solving the Integral Equation of the First Kind and Its Numerical Experiments. Numerical Mathematics, 12, 158-179.

[12]   Zhou, X. (2014) Legendre Multiwavelet Galerkin Methods for Differential Equations. Journal of applied mathematics & informatics, 32, 267-284.
https://doi.org/10.14317/jami.2014.267

[13]   Zhou, X. and Lin, Q. (2021) Jacobi Biorthogonal Multiwavelets and Their Applications to Fractional-Order Differential Equations. (Submitted)

[14]   Deng, W.H., Lin, Y. and Zhang, Z.J. (2014) Wavelet Galerkin Method for Fractional Elliptic Differential Equations. arXiv:1405.6856v1.
https://arxiv.org/abs/1405.6856

[15]   Xu, J.S. and Shann, W.C. (1992) Galerkin-Wavelet Methods for Two-Point Boundary Value Problems. Numerische Mathematik, 63, 123-144.
https://doi.org/10.1007/BF01385851

 
 
Top