![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
Drawing inspiration from the construction of tight wavelet frames generated by the Walsh polynomials, we introduce the notion of minimum-energy wavelet frames generated by the Walsh polynomials on positive half-line using unitary extension principles and present its equivalent characterizations in terms of their framelet symbols. Moreover, based on polyphase components of the Walsh polynomials, we obtain a necessary and sufficient condition for the existence of minimum-energy wavelet frames in
. Finally, we derive the minimum-energy wavelet frame decomposition and reconstruction formulae which are quite similar to those of orthonormal wavelets on local fields of positive characteristic.
Public Interest Statement
Wavelet frames are different from the orthonormal wavelets because of redundancy. By sacrificing orthonormality and allowing redundancy, the wavelet frames become much easier to construct than the orthonormal wavelets. Wavelet frames and their promising features in applications have attracted a great deal of interest and effort in recent years. Although wavelet frames have many desirable features but the computational complexity and numerical instability during the course of decomposition and reconstruction of functions always remains a debate of discussion. In this study, we introduce a new concept called minimum-energy wavelet frames generated by the Walsh polynomials on a positive half-line. Our results will be mostly used by that part of mathematical society who works in wavelet analysis and their applications. Most prominent among them are the theory of signal processing, image processing, data transmission with erasures, quantum computing, medicine, representation theory, and algebraic geometry.
1. Introduction
The notion of frames was first introduced by Duffin and Schaeffer (Citation1952) in connection with some deep problems in nonharmonic Fourier series. Frames are basis-like systems that span a vector space but allow for linear dependency, which can be used to reduce noise, find sparse representations, or obtain other desirable features unavailable with orthonormal bases. The idea of Duffin and Schaeffer did not generate much interest outside nonharmonic Fourier series until the seminal work by Daubechies, Grossmann, and Meyer (Citation1986). They combined the theory of continuous wavelet transforms with the theory of frames to introduce wavelet (affine) frames for . After their work, the theory of frames began to be studied widely and deeply. Today, the theory of frames has become an interesting and fruitful field of mathematics with abundant applications in signal processing, image processing, harmonic analysis, Banach space theory, sampling theory, wireless sensor networks, optics, filter banks, quantum computing, medicine, and so on. An introduction to the frame theory and its applications can be found in Christensen (Citation2003), Daubechies (Citation1992), Debnath and Shah (Citation2015), Dong, Ji, Li, Shen, and Xu (Citation2012). The following are the standard definitions on frames in Hilbert spaces. A sequence
of elements of a Hilbert space
is called a frame for
if there exist constants
such that for all
(1.1)
(1.1)
The largest constant A and the smallest constant B satisfying (1.1) are called the lower and upper frame bound, respectively. A frame is a tight frame if A and B are chosen so that and is called a Parseval frame or normalized tight frame if
.
An important example about frame is wavelet frame, which is obtained by translating and dilating a finite family of functions. One of the most useful methods to construct wavelet frames is through the concept of unitary extension principle (UEP) introduced by Ron and Shen (Citation1997) and were subsequently extended by Daubechies, Han, Ron, and Shen (Citation2003) in the form of the oblique extension principle (OEP). They give sufficient conditions for constructing tight and dual wavelet frames for any given refinable function which generates a multiresolution analysis. The resulting wavelet frames are based on multiresolution analysis, and the generators are often called framelets. The advantages of MRA-based wavelet frames and their promising features in applications have attracted a great deal of interest and effort in recent years. To mention only a few references on wavelet frames, the reader is referred to Chui and He (Citation2000), Dong et al. (Citation2012), Farkov, Lebedeva, and Skopina (Citation2015), Gao and Cao (Citation2008), Han (Citation2012), Huang and Cheng (Citation2007), Huang, Li, and Li (Citation2012), Zhu, Li, and Huang (Citation2013) and many references therein.
The past decade has also witnessed a tremendous interest in the problem of constructing compactly supported orthonormal scaling functions and wavelets with an arbitrary dilation factor (see Debnath & Shah, Citation2015). The motivation comes partly from signal processing and numerical applications, where such wavelets are useful in image compression and feature extraction because of their small support and multifractal structure. Lang (Citation1996) constructed several examples of compactly supported wavelets for the Cantor dyadic group by following the procedure of Daubechies (Citation1992) via scaling filters and these wavelets turn out to be certain lacunary Walsh series on the real line. Kozyrev (Citation2002) found a compactly supported p-adic wavelet basis for
which is an analog of the Haar basis. The concept of multiresolution analysis on a positive half-line
was recently introduced by Farkov (Citation2009). He pointed out a method for constructing compactly supported orthogonal p-wavelets related to the Walsh functions, and proved necessary and sufficient conditions for scaling filters with
many terms (
to generate a p-MRA in
. Subsequently, dyadic wavelet frames on the positive half-line
were constructed by Shah and Debnath (Citation2011a) using the machinery of Walsh–Fourier transforms. They have established a necessary and sufficient conditions for the system
to be a frame for
. Wavelet packets and wavelet frame packets related to the Walsh polynomials were deeply investigated in a series of papers by the author in Shah (Citation2009,Citation2012,CitationXXXX), Shah and Debnath (Citation2011b). Recent results in this direction can also be found in Farkov, Maksimov, and Stroganov (Citation2011), Meenakshi, Manchanda, and Siddiqi (Citation2012), Shah (Citation2015), Sharma and Manchanda (Citation2013) and the references therein.
A constructive procedure for constructing tight wavelet frames generated by the Walsh polynomials using extension principles was first reported by one of the authors by Shah (Citation2013). He provided a sufficient condition for finite number of functions to form a tight wavelet frame for
. Although wavelet frames have many desirable features but the computational complexity and numerical instability during the course of decomposition and reconstruction of functions always remains a debate of discussion (see Dong et al., Citation2012; Han, Citation2012). Therefore, in order to reduce the computational complexity and maintain the numerical stability, we shall introduce the concept of minimum-energy wavelet frames associated with the Walsh polynomials on
by extending the above-described method (Shah, Citation2013). More precisely, we present an equivalent characterizations of minimum-energy wavelet frames in terms of their framelet symbols (Walsh polynomials). Further, based on the polyphase representation of the framelet symbols, a necessary and sufficient condition for minimum-energy wavelet frames related to Walsh polynomials is also given. Finally, we derive the minimum-energy wavelet frame decomposition and reconstruction formulas which are quite similar to those of orthonormal wavelets on positive half-line
.
The paper is structured as follows. In Section 2, we introduce some notations and preliminaries related to the operations on positive half-line including the definitions of the Walsh–Fourier transform, p-multiresolution analysis and minimum-energy wavelet frame related to the Walsh polynomials. In Section 3, we construct minimum-energy wavelet frames generated by the Walsh polynomials and establish a necessary and sufficient condition for the existence of minimum-energy wavelet frames in
. Section 4, deals with the decomposition and reconstruction algorithms of the minimum-energy wavelet frames on a half-line
.
2. Walsh–Fourier analysis and MRA-based wavelet frames
We start this section with certain results on Walsh–Fourier analysis. We present a brief review of generalized Walsh functions, Walsh–Fourier transforms, and its various properties.
As usual, let and
. Denote by [x] the integer part of x. Let p be a fixed natural number greater than 1. For
and any positive integer j, we set
(2.1)
(2.1)
where . It is clear that for each
, there exist
in
such that
.
Consider on the addition defined as follows:
with where
and
are calculated by (2.1). As usual, we write
if
where
denotes subtraction modulo p in
.
For , let
is given by
where . The extension of the function
to
is given by the equality
. Then, the generalized Walsh functions
are defined by
where They have many properties similar to those of the Haar functions and trigonometric series, and form a complete orthogonal system. Further, by a Walsh polynomial we shall mean a finite linear combination of Walsh functions.
For let
(2.2)
(2.2)
where are given by (2.1).
We observe that
and
where and
is p-adic irrational. It is well known that systems
and
are orthonormal bases in
[0,1] (see Golubov, Efimov, & Skvortsov, Citation1991).
The Walsh–Fourier transform of a function is defined by
(2.3)
(2.3)
where is given by (2.2). The Walsh–Fourier operator
, extends uniquely to the whole space
. The properties of the Walsh–Fourier transform are quite similar to those of the classic Fourier transform (see Golubov et al., Citation1991; Schipp, Wade, & Simon, Citation1990). In particular, if
then
and
By p-adic interval of range n, we mean intervals of the form
The p-adic topology is generated by the collection of p-adic intervals and each p-adic interval is both open and closed under the p-adic topology (see Schipp et al., Citation1990). The family forms a fundamental system of the p-adic topology on
. Therefore, for each
the Walsh function
is piecewise constant and hence continuous. Thus
for
.
Let be the space of p-adic entire functions of order n, that is, the set of all functions which are constant on all p-adic intervals of range n. Thus, for every
, we have
(2.4)
(2.4)
Clearly each Walsh function of order belong to
. The set
of p-adic entire functions on
is the union of all the spaces
. It is clear that
is dense in
and each function in
is of compact support.
Next, we give a brief account of the MRA-based wavelet frames generated by the Walsh polynomials on a positive half-line . Following the unitary extension principle, one often starts with a refinable function or even with a refinement mask to construct desired wavelet frames. A compactly supported function
is called a refinable function, if it satisfies an equation of the type
(2.5)
(2.5)
where are complex coefficients. Applying the Walsh–Fourier transform, we can write this equation as
(2.6)
(2.6)
where(2.7)
(2.7)
is a generalized Walsh polynomial, which is called the or
of the refinable function
and is of course a p-adic step function. Observe that
. Hence, letting
in (2.6) and (2.7), we obtain
. Since
is compactly supported and in fact
, therefore
and hence as a result
for all
as
. Moreover, if
represents the values of the mask
on p-adic intervals, i.e.
(2.8)
(2.8)
then(2.9)
(2.9)
and, conversely, equalities (2.8) follow from (2.9). These discrete transforms can be realized by the fast Vilenkin–Chrestenson transform (see Golubov et al., Citation1991). Using Parseval’s relation for the discrete transforms, Equations (2.8) and (2.9) can be written as(2.10)
(2.10)
For a compactly supported refinable function , let
be the closed shift invariant space generated by
and
. Then, it is proved in Farkov (Citation2009) that the closed subspaces
forms a p-multiresolution analysis (p-MRA) for
. Recall that a p-MRA is a family of closed subspaces
of
that satisfies: (i)
(ii)
is dense in
and (iii)
.
Given an p-MRA generated by a compactly supported refinable function , one can construct a set of basic tight framelets
satisfying
(2.11)
(2.11)
where(2.12)
(2.12)
are the generalized Walsh polynomials in and are called the framelet symbols or wavelet masks.
With as the Walsh polynomials (wavelet masks), we formulate the matrix
as:
(2.13)
(2.13)
The so-called unitary extension principle (UEP) provides a sufficient condition on such that the wavelet system
(2.14)
(2.14)
forms a tight frame of . In this connection, Shah (Citation2013) gave an explicit construction scheme for the construction of tight wavelet frames generated by the Walsh polynomials using unitary extension principles in the following way.
Theorem 2.1
Let be a compactly supported refinable function and
. Then, the wavelet system
given by (2.14) constitutes a normalized tight wavelet frame in
provided the matrix
as defined in (2.13) satisfies
(2.15)
(2.15) where
Motivated and inspired by the construction of tight wavelet frames generated by the Walsh polynomials (Shah, Citation2013), we extend this concept to minimum-energy wavelet frames on the positive half-line using the machinery of unitary extension principles. Note that, in this paper, we suppose that any symbol function is a Walsh polynomial, and scaling function and wavelet functions are compactly supported.
Definition 2.1
Let satisfies
and
is continuous at 0, and
. Suppose that
generates a sequence of nested closed subspaces
. Then, a finite family
is called a minimum-energy wavelet frame associated with
, if for all
(2.16)
(2.16)
By Parseval’s identity, minimum-energy wavelet frame must be a tight frame for
with frames bound equal to 1. At the same time, formula (2.16) is equivalent to
(2.17)
(2.17)
3. Construction of minimum-energy wavelet frames
In this section, we give a complete characterization of minimum-energy wavelet frames associated with some given refinable functions in terms of their framelet symbols. More precisely, we present a necessary and sufficient condition for the existence of minimum-energy wavelet frames generated by Walsh polynomials.
The following theorem presents the equivalent characterizations of the minimum-energy wavelet frame associated with given compactly supported refinable function .
Theorem 3.1
Suppose that every element of the framelet symbols, , in (2.7) and (2.12) is a Walsh polynomial, and the compactly supported function
associated with
generates a nested subspace
. Then the following statements are equivalent:
(1) |
| ||||
(2) |
| ||||
(3) |
|
Proof
By using the functional Equations (2.5) and (2.11) and notation , Equation (2.17) can be written as
(3.3)
(3.3)
On the other hand, formula (3.1) can be reformulated as(3.4)
(3.4)
which is equivalent to
or
The above system is equivalent to
The above system can be further expressed as(3.5)
(3.5)
Multiply the identities of (3.5) with , we obtain
(3.6)
(3.6)
Therefore, the system (3.5) can be written as
This system of equations can be written in time domain as
On the reformulation of above system, we obtain(3.7)
(3.7)
Using (2.5) and its corresponding wavelet equation, we can rewrite formula (3.7) as(3.8)
(3.8)
Thus, the UEP condition (3.1) is equivalent to (3.8). In conclusion, the proof of the theorem reduces to the proof of the equivalence of (3.2), (3.3), and (3.8).
It is obvious that (3.2) implies (3.8) which implies (3.3). In order to prove , we assume that f be a function of compact support, i.e.
. By using the properties that for every fixed m,
except for finitely many n, the functional
just has finite nonzero’s for . Since
is nontrivial function, by taking the Fourier transform of (3.3), it follows that the polynomial
is identically zero. Obviously,
. In other words, we say that
Thus, the series in the above equation is a finite sum and hence represents a compactly supported function in . By choosing f to be this function, it follows that
which implies that the polynomial is identically equal to 0 so that
. This completes the proof of the theorem.
Now we shall present a necessary condition for minimum-energy wavelet frames generated by the Walsh polynomials in terms of their wavelet masks.
Theorem 3.2
Let be a compactly supported refinable function with refinement mask
such that
is continuous at 0 and
. If
is the minimum-energy wavelet frame associated with
, then
(3.9)
(3.9)
Proof
Let be the first column of the modulation matrix
, as defined in (2.13). Then,
, where
(3.10)
(3.10)
and
Therefore, the condition (3.1) can be reformulated as
or equivalently,
Since is a Hermitian matrix, the matrix
is positive semi-definite, so that
and this gives
In fact, we have
Therefore
and it gives . The proof of the Theorem 3.2 is completed.
According to the Theorem 3.2, there may not exist minimum-energy wavelet frame associated with a given compactly supported refinable function and in case if it exist, then the refinement mask must satisfy (3.9). In this context, we provide a sufficient condition for minimum-energy wavelet frames related to the Walsh polynomials based on the polyphase representation of the wavelet masks
.
The polyphase representation of the refinement mask can be derived by using the properties of Walsh polynomials as
where(3.11)
(3.11)
Similarly, the wavelet masks , as defined in (2.12) can be splitted into polyphase components as
(3.12)
(3.12)
where(3.13)
(3.13)
With the polyphase components given by (3.11) and (3.13), we formulate the polyphase matrix as:
Therefore, the modulation matrix can be expressed as
(3.14)
(3.14)
where is the Walsh matrix given by
Thus, we have
and, hence we conclude that
or equivalently, we say that
Since the Walsh matrix is a unitary matrix, therefore, we have
(3.15)
(3.15)
which implies that(3.16)
(3.16)
Therefore, it follows from (3.9) and (3.16) that(3.17)
(3.17)
which further yields(3.18)
(3.18)
where . Since the polynomial
is constant on the intervals
, so the polyphase components
can also be written as
(3.19)
(3.19)
where(3.20)
(3.20)
Now, if there exists such that
(3.21)
(3.21)
then, we have the following theorem which provides a sufficient condition for minimum-energy wavelet frames generated by the Walsh polynomials in .
Theorem 3.3
Let be the refinement mask of a compactly supported refinable function
and satisfy inequality (3.17). Furthermore, if there exist
of the form (3.21), then there exists a minimum-energy wavelet frame associated with
.
Proof
Under the given assumptions, it is easy to verify that(3.22)
(3.22)
is a unit vector, where T stands for the transpose of a given vector. By multiplying the diagonal matrix to the left side of (3.22), we obtain
where , with
and
. It is also clear that
is a unit vector as
and consequently, .
Consider the Householder matrix
(3.23)
(3.23)
where , with
, and the
and
signs are so chosen that
. Then
By the orthogonal property of the Householder matrix, we have
Using previous equation, it follows that the first component of is 0. Since
, therefore, we can construct a diagonal matrix
such that
is also a unit vector and
Similarly, we define the Householder matrix(3.24)
(3.24)
where , and
such that
is also a unit vector and Since every component of
is a finite sum, we repeat this procedure finite times to get some unitary matrices
such that
(3.25)
(3.25)
Therefore, it is clear that is the first column of the unitary matrix
By setting,
It is immediate that satisfies the equality
. Further, if we choose polyphase representation of wavelet masks
as defined by (3.13) or even (3.19) in Equation (2.13), then we can obtain the UEP condition (2.15). Therefore, Theorem 3.1 implies that
generates a minimum-energy wavelet frame for
. This completes the proof of the Theorem 3.3.
4. Decomposition and reconstruction algorithms
Suppose is the minimum-energy wavelet frame associated with the compactly supported refinable function
. Then, for each
, we consider
(4.1)
(4.1)
Thus,(4.2)
(4.2)
Note that decomposition (4.2) is not a direct sum decomposition since in general Thus, it follows from (4.1) and (4.2) that any
can be expressed as
(4.3)
(4.3)
where(4.4)
(4.4)
(4.5)
(4.5)
are the projection and detailed operators defined on and
, respectively. The importance of this frame expansion as compared to any other expansion
(4.6)
(4.6)
of the same is that the energy in (4.5) is minimum in the sense that
(4.7)
(4.7)
Therefore, by using (4.5) and (4.6), we have(4.8)
(4.8)
and this derives
This inequality means that the coefficients of the error term in (4.5) have minimal
-norm among all sequences
which satisfy (4.6).
We now discuss the decomposition and reconstruction algorithms associated with minimum-energy wavelet frames on positive half-line. For any , we consider
(4.9)
(4.9)
Then, by two scale relations (2.5) and the corresponding wavelet equation, we obtain(4.10)
(4.10)
By taking the inner products with f on both sides of the two equations in (4.10), we have a tight minimum-energy wavelet frame decomposition:(4.11)
(4.11)
Using the fact that and relations (2.4) and wavelet equation, from (4.3) we also have
(4.12)
(4.12)
By taking the inner products with f on both sides of (4.12), we have a tight minimum-energy wavelet frame reconstruction:(4.13)
(4.13)
Acknowledgements
The authors thank the referees for numerous suggestions which helped to improve the paper considerably.
Additional information
Funding
Notes on contributors
Sunita Goyal
Sunita Goyal received her MSc and MPhil degrees in pure mathematics from the University of Rothak, Haryana, India. Currently, she is perusing PhD at the Department of Mathematics, JJT University, Rajasthan, India. Her research interests are focused on different aspects of wavelet analysis including wavelet frames, shift invariant spaces, wavelet packets and their applications in Economics and Finance.
Firdous A. Shah
Firdous A. Shah is a senior assistant professor in the Department of Mathematics at University of Kashmir, India. His primary research interests include basic theory of wavelets and their applications in differential and integral equations, Economics and Finance, and Computer Networking. He has authored/co-authored over 50 research papers in international journals of high repute. He has recently co-authored a book on wavelets entitled Wavelet Transforms and Their Applications, Springer, New York, 2015.
References
- Christensen, O. (2003). An introduction to frames and Riesz bases. Boston, MA: Birkh\"auser.
- Chui, C. K., & He, W. (2000). Compactly supported tight frames associated with refinable functions. Applied Computational and Harmonic Analysis, 8, 293–319.
- Daubechies, I. (1992). Ten lectures on wavelets. Philadelphia, PA: SIAM.
- Daubechies, I., Grossmann, A., & Meyer, Y. (1986). Painless non-orthogonal expansions. Journal of Mathematical Physics, 27, 1271–1283.
- Daubechies, I., Han, B., Ron, A., & Shen, Z. (2003). Framelets: MRA-based constructions of wavelet frames. Applied Computational and Harmonic Analysis, 14, 1–46.
- Debnath, L., & Shah, F. A. (2015). Wavelet transforms and their applications. New York, NY: Birkh\"auser.
- Dong, B., Ji, H., Li, J., Shen, Z., & Xu, Y. (2012). Wavelet frame based blind image inpainting. Applied Computational and Harmonic Analysis, 32, 268–279.
- Duffin, R. J., & Shaeffer, A. C. (1952). A class of nonharmonic Fourier series. Transactions of American Mathematical Society, 72, 341–366.
- Farkov, Y. A. (2009). On wavelets related to Walsh series. Journal of Approximation Theory, 161, 259–279.
- Farkov, Y. A., Maksimov, A. Y., & Stroganov, S. A. (2011). On biorthogonal wavelets related to the Walsh functions. International Journal of Wavelets, Multiresolution and Information Processing, 9, 485–499.
- Farkov, Y. A., Lebedeva, E. A., & Skopina, M. A. (2015). Wavelet frames on Vilenkin groups and their approximation properties. International Journal of Wavelets, Multiresolution and Information Processing, 13(5), 19 p., 1550036.
- Gao, X., & Cao, C. H. (2008). Minimum-energy wavelet frame on the interval. Science in China F, 51, 1547–1562.
- Golubov, B. I., Efimov, A. V., & Skvortsov, V. A. (1991). Walsh series and transforms: Theory and applications. Dordrecht: Kluwer.
- Han, B. (2012). Wavelets and framelets within the framework of non-homogeneous wavelet systems. In M. Neamtu & L. Schumaker (Eds.), Approximation theory XIII (pp. 121–161). Springer.
- Huang, Y., & Cheng, Z. (2007). Minimum-energy frames associated with refinable function of arbitrary integer dilation factor. Chaos, Solitons and Fractals, 32, 503–515.
- Huang, Y., Li, Q., & Li, M. (2012). Minimum-energy multiwavelet frames with arbitrary integer dilation factor. Mathematical Problems in Engineering, 37 p., 640789.
- Kozyrev, S. V. (2002). Wavelet analysis as a p-adic spectral analysis. Izvestiya: Mathematics, 66, 149–158.
- Lang, W. C. (1996). Orthogonal wavelets on the Cantor dyadic group. SIAM Journal of Mathematical Analysis, 27, 305–312.
- Meenakshi, M. P., & Siddiqi, A. H. (2012). Wavelets associated with nonuniform multiresolution analysis on positive half-line. International Journal of Wavelets, Multiresolution and Information Processing, 12(2), 27 p., 1250018.
- Ron, A., & Shen, Z. (1997). Affine systems in L\textsuperscript{2} The analysis of the analysis operator. Journal of Functional Analysis, 148, 408–447.
- Schipp, F., Wade, W. R., & Simon, P. (1990). Walsh series: An introduction to Dyadic harmonic analysis. Bristol: Adam Hilger.
- Shah, F. A. (2009). Construction of wavelet packets on p-adic field. International Journal of Wavelets, Multiresolution and Information Processing, 7, 553–565.
- Shah, F. A. (2012). Biorthogonal wavelet packets related to the Walsh polynomials. Journal of Classical Analysis, 1, 135–146.
- Shah, F. A. (2013). Tight wavelet frames generated by the Walsh polynomials. International Journal of Wavelets, Multiresolution and Information Processing, 11(6), 15 p., 1350042.
- Shah, F. A. (2015). p-Frame multiresolution analysis related to the Walsh functions. International Journal of Analysis and Applications, 7, 1–15.
- Shah, F. A., & Debnath, L. (2011a). Dyadic wavelet frames on a half-line using the Walsh--Fourier transform. Integral Transforms and Special Functions, 22, 477–486.
- Shah, F. A. (XXXX). Non-orthogonal p-wavelet packets on a half-line. Analysis in Theory and Applications, 28, 385–396.
- Shah, F. A., & Debnath, L. (2011b). p-Wavelet frame packets on a half-line using the Walsh--Fourier transform. Integral Transforms and Special Functions, 22, 907–917.
- Sharma, V., & Manchanda, P. (2013). Wavelet packets associated with nonuniform multiresolution analysis on positive half-line. Asian-European Journal of Mathematics, 6(1), 16 p., 1350007.
- Zhu, F., Li, Q., & Huang, Y. (2013). Minimum-energy bivariate wavelet frame with arbitrary dilation matrix. Journal of Applied Mathematics, 10 p., 896050.