American Journal of Computational Mathematics
Vol. 2 No. 2 (2012) , Article ID: 20052 , 6 pages DOI:10.4236/ajcm.2012.22011
Nonstationary Wavelets Related to the Walsh Functions
Department of Mathematics, Russian State Geological Prospecting University, Moscow, Russia
Email: farkov@list.ru
Received March 29, 2012; revised April 25, 2012; accepted May 2, 2012
Keywords: Walsh Functions; Nonstationary Dyadic Wavelets; Fractal Functions; Adapted Multiresolution Analysis
ABSTRACT
Using the Walsh-Fourier transform, we give a construction of compactly supported nonstationary dyadic wavelets on the positive half-line. The masks of these wavelets are the Walsh polynomials defined by finite sets of parameters. Application to compression of fractal functions are also discussed.
1. Introduction
As usual, let be the positive half-line,
be the set of all nonnegative integers, and let
be the set of all positive integers. The first examples of orthogonal wavelets on
related to the Walsh functions and the corresponding wavelets on the Cantor dyadic group have been constructed in [1]; then, in [2] and [3], a multifractal structure of this wavelets is observed and conditions for wavelets to generate an unconditional basis in
-spaces for all
have been found. These investigations are continued in [4-10] where among other subjects the algorithms to construct orthogonal and biorthogonal wavelets associated with the generalized Walsh functions are studied. In the present paper, using the Walsh-Fourier transform, we construct nonstationary dyadic wavelets on
(cf. [11-13], [14, Ch.8]).
Let us denote by the integer part of
. For every
, we set
where
. Then
.
The dyadic addition on is defined as follows
.
Further, we introduce the notations
where
. Then the Walsh function
of order
is
(see, e.g., [15]).
The Walsh-Fourier transform of every function that belongs to
is defined by
,
.
and extent to the whole space in a standard way. The intervals
,
are called the dyadic intervals of range
. The dyadic topology on
is generated by the collection of dyadic intervals. A subset
of
which is compact in the dyadic topology will be called W-compact.
For any we define
and
by the following algorithm:
Step 1. For each choose
, and
,
, such that
(1)
for all
Step 2. Define the masks
(2)
with the coefficients
so that
for all
(cf. [15, Sect. 9.7]).
Step 3. For each put
, (3)
so that
. (4)
Step 4. Define by the formula
. (5)
Further, let us define subspaces and
in
as follows
,
for all.
We say that a polynomial satisfies the modified Cohen condition if there exists a W-compact subset
of
such that
and
. (6)
Theorem. Suppose that the masks satisfy the modified Cohen condition with a subset
and there exists
such that
for all
,
. (7)
Then for any the following properties hold:
a) and
;
b) and
are orthonormal basis in
and
, respectively;
c),
.
Moreover, we have
.
Corollary. The system
is an orthonormal basis in.
We prove this theorem in the next section. Then using the notion of an adapted multiresolution analysis suggested by Sendov [12], we discuss an application of the nonstationary dyadic wavelets to compression of the Weierstrass function and the Swartz function.
2. Proof of the Theorem
At first we prove the orthonormality of. In view of
let us show that
,
.
Denote by the characteristic function of
. For each
we define
for Since
and, for all
,
in some neighbourhood of zero, we obtain from Equation (3)
for all
. (8)
Let
where
,
. Letting
, we have
that yields. By induction, we obtain
According to Equation (8), by Fatou’s lemma, we have
(9)
Consequently, and, in view of Equation (5),
. It is known that if
is constant on dyadic intervals of range
, then
(see [16, Sect. 6.2]). Therefore, each function
is constant on
,
, which implies
.
In view of Equation (7), there exists such that
for all
,
.
Hence, for,
.
It follows from Equation (6) that for some
for
.
Since
,
.
We have
.
or, taking into account Equation (3),
,
for,
.
Applying the dominated convergence theorem we obtain
which means that is an orthonormal system.
Now, let us prove an orthonormality of. For any
denote
. Then
. (10)
Since
We have
Then from Equation (10)
,
. (11)
Let us define
.
Denote. Under the unitarity of the matrices
We can write
Using the inverse Fourier-Walsh transform, we have
or,
.
With Equation (11) it yields
To conclude the proof it remains to show that
. (12)
Note, that by Equation (7) for any there exist
such that
and, consequently,
. (13)
For any the subspace
is invariant with respect to the shift
. Actually, an arbitrary
can be approximated by fractions
, with arbitrary large
. Besides, each
is invariant with respect to the shifts
. By Equation (4) it is clear that
.
Let. There exist
such that
and hence for all
. The continuity of
implies that
. If
, then approximating
with
from
and using the invariance of a norm with respect to the shift, we obtain
.
Denote by the set of all
such that
. By the Weiner’s theorem we can write
, for some measurable
. It is clearly that
and, in view of Equation (13), we have
. Hence, the Equation (12) holds. The theorem is proved.
3. Numerical Experiments
For any, let
,
. According to [12] an adapted multiresolution analysis (AMRA) of rank
in
is a collection of closed subspaces
,
, which satisfies the following conditions:
1) for all
;
2);
3) for every there is a function
in
with a finite support
such that
is an orthonormal basis of
;
4) for every there exists a filter
such that
,
. (14)
The sequence from condition (4) is called a scaling sequence for given an AMRA. The corresponding a wavelet sequence
can be defined by
. (15)
Denote by the orthogonal complement of
in
. It is known that, under some conditions, the system
is an orthonormal basis of
(for more details, see, e.g., [14, Sect. 8.1]). Moreover, if
denotes the projection of a function
on the subset
, then
and
. (16)
Let us denote
and
.
For a given array
the direct non-stationary discrete wavelet transform
maps it into
and
.
The inverse transform is defined as follows
and reconstructs by
and
. According to [12] in order to choose the filter
to maximize
in Equation (16), we must solve the following problem.
Problem 1. Let be the subset of the 2n-dimensional Euclidean space
, which consists of the points
satisfying the conditions
. (17)
for. Find a point
for which
, (18)
where is a
symmetric matrix.
Problem 1 has a solution since is a compact. But, as noted in [12], the numerical solution of this problem is not trivial even for
.
Concerning the standard Haar and Daubechies (with 4 coefficients) discrete transforms see, e.g., [17]; we will denote them as SWTH and SWTD, respectively. We write NSWTH for the simplest case of a multiresolution analysis of rank 1 which is considered in [12, Sect. 3] (see also [13]). The nonstationary Daubechies discrete wavelet transform which corresponds an AMRA of rank are defined in [12] and we will use the symbol NSWTDN to denote this transform (see NSWTD1 and NSWTD2 in the tables below).
Method A associated with one of the mentioned above discrete wavelet transforms (cf. [17, Chap.7]) consists of the following steps:
Step 1. Apply the discrete wavelet transform times to an input array
and get the sequence
.
Step 2. Allocate a certain percentage of the wavelet coefficients with lagest absolute value (we choose 10%) and nullify the remaining coefficients.
Step 3. Apply the inverse wavelet transform to the modified arrays of the wavelet coefficients.
Step 4. Calculate, where
is a reconstructed array.
In Method B the second step is replaced on the uniform quantization and the forth step is replaced on the calculation of the entropy of a vector, obtained in the third step.
We recall that is a vector uniform quantization for given vector
, if
where is the length of the quantization interval.
The value will be calculated by
The Shannon entropy of is defined by the formula
where
is frequency of the value
.
Let us consider a similar approach associated with the following problem:
Problem 2. Let. Denote by
the set of all points
such that
For every we define
for. Find a point
for which
(19)
where is a
symmetric matrix.
Given an array, we define the matrix
in Problem 1 and Problem 2 by
and
respectively. Here
for
. Suppose that
is a solution of Equation (19). Then the direct and inverse nonstationary discrete dyadic wavelet transforms are defined by
,
,
where
and
. We
Table 1. Values of the square error corresponding to Method A.
Table 2. Values of the entropy obtained by Method B.
denote these discrete transforms as NSWTL1 if and as NSWTL2 if
.
Let us recall that the Weierstrass function is defined as
and the Swartz function is defined as
where
. We will consider arrays
with elements a8,k =
or a8,k =
,
. Then we use the Matlab function fminsearch to solve the optimization problems in Equations (18) and (19). The results of these numerical experiments are presented in Tables 1 and 2. We see that in several cases the introduced nonstationary dyadic wavelets have an advantage over the classical Haar and Daubechies wavelets.
REFERENCES
- W. C. Lang, “Orthogonal Wavelets on the Cantor Dyadic Group,” SIAM Journal on Mathematical Analysis, Vol. 27, No. 1, 1996, pp. 305-312. doi:10.1137/S0036141093248049
- W. C. Lang, “Wavelet Analysis on the Cantor Dyadic Group,” Houston Journal of Mathematics, Vol. 24, No. 3, 1998, pp. 533-544.
- W. C. Lang, “Fractal Multiwavelets Related to the Cantor Dyadic Group,” International Journal of Mathematics and Mathematical Sciences, Vol. 21, No. 2, 1998, pp. 307-317. doi:10.1155/S0161171298000428
- Y. A. Farkov, “Orthogonal Wavelets with Compact Support on Locally Compact Abelian Groups,” Izvestiya: Mathematics, Vol. 69, No. 3, 2005, pp. 623-650. doi:10.1070/IM2005v069n03ABEH000540
- Y. A. Farkov, “Wavelets and Frames in Walsh Analysis,” In: M. del Valle, Ed., Wavelets: Classification, Theory and Applications, Chapter 11, Nova Science Publishers, New York, 2012, pp. 267-304.
- Y. A. Farkov and E. A. Rodionov, “Estimates of the Smoothness of Dyadic Orthogonal Wavelets of Daubechies Type,” Mathematical Notes, Vol. 82, No. 6, 2007, pp. 407-421. doi:10.1134/S0001434609090144
- Y. A. Farkov, A. Yu. Maksimov and S. A. Stroganov, “On Biorthogonal Wavelets Related to the Walsh Functions,” International Journal of Wavelets, Multiresolution and Information Processing, Vol. 9, No. 3, 2011, pp. 485- 499. doi:10.1142/S0219691311004195
- Y. A. Farkov and E. A. Rodionov, “Algorithms for Wavelet Construction on Vilenkin Groups,” P-Adic Numbers, Ultrametric Analysis, and Applications, Vol. 3, No. 3, 2011, pp. 181-195. doi:10.1134/S2070046611030022
- Y. A. Farkov, “Periodic Wavelets on the p-Adic Vilenkin Group,” P-Adic Numbers, Ultrametric Analysis, and Applications, Vol. 3, No. 4, 2011, pp. 281-287. doi:10.1134/S2070046611040030
- Y. A. Farkov and M. E. Borisov, “Periodic Dyadic Wavelets and Coding of Fractal Functions,” Russian Mathematics (Izvestiya VUZ. Matematika), No. 9, 2012, pp. 54- 65.
- I. Y. Novikov, “On the Construction of Nonstationary Orthonormal Infinitely differentiable Compactly Supported Wavelets,” Proceedings of the 12th International Association for Pattern Recognition, Jerusalem, 9-13 October 1994, pp. 214-215. doi:10.1109/ICPR.1994.577164
- B. Sendov, “Adapted Multiresolution Analysis,” Proceedings of Alexits Memorial Conference Functions, Series, Operators, Budapest, 9-14 August 1999, pp. 23-38.
- B. Sendov, “Adaptive Multiresolution Analysis on the Dyadic Topological Group,” Journal of Approximation Theory, Vol. 96, No. 2, 1998, pp. 21-45. doi:10.1006/jath.1998.3234
- I. Y. Novikov, V. Y. Protasov and M. A. Skopina, “Wavelet Theory,” American Mathematical Society, Providence, 2011.
- F. Schipp, W. R. Wade and P. Simon, “Walsh Series: An Introduction to Dyadic Harmonic Analysis,” Adam Hilger, Bristol, 1990.
- B. I. Golubov, A. V. Efimov and V. A. Skvortsov, “Walsh Series and Transforms,” Kluwer, Dordrecht, 1991.
- S. Welstead, “Fractal and Wavelet Image Compression Techniques,” SPIE Optical Engineering Press, Bellingham, 2002.