Subscribe Now Subscribe Today
Research Article
 

A PSO Method for Wavelet Approximation



Hongmin Li, Yigang He and Yichuang Sun
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

For implementing wavelet transform in analog hardware systems with very low power consumption and small size, a particle swarm optimization method is employed in the approximating of wavelet functions. First, utilizing the least-squares error criterion, a general mathematical model for approximating wavelet functions is established. Then the technique of L2 approximation based on Particle Swarm Optimization (PSO) is presented, which is more attractive. These techniques are compared by means of a worked example, involving some wavelet approximation. The L2 approximation approach based on PSO is shown to exhibit superior performance.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Hongmin Li, Yigang He and Yichuang Sun, 2014. A PSO Method for Wavelet Approximation. Information Technology Journal, 13: 661-668.

DOI: 10.3923/itj.2014.661.668

URL: https://scialert.net/abstract/?doi=itj.2014.661.668
 
Received: September 03, 2013; Accepted: December 15, 2013; Published: February 15, 2014



INTRODUCTION

The Wavelet Transform (WT) is a merited technique for analysis of non-stationary signals like cardiac signals. Being a multiscale analysis technique, it offers the possibility of selective noise filtering and reliable parameter estimation. Often WT systems employ the discrete wavelet transform, implemented in a digital signal processor. However, in ultra low-power applications such as biomedical implantable devices, it is not suitable to implement the WT by means of digital circuitry due to the high power consumption associated with the required A/D converter. For power consumption considerations it therefore is preferable to perform WT in the analog domain.

Low-power analog realization of the wavelet transform with the technique of analog circuits (Karel et al., 2005, 2012; Gurrola-Navarro et al., 2010; Haddad et al., 2005) has been introduced. The quality of such implementations depends on the accuracy of the corresponding wavelet approximations. Previous approaches reported for wavelet approximations include mainly pade approximation method (Haddad et al., 2005) and L2 approximation method (Karel et al., 2005; Haddad et al., 2005). The Laplace transforms of wavelet functions were approximated by rational functions in the Laplace domain with Pade approximation (Baker, 1975; Bultheel and Barel, 1986). However, there are some problems which limit the practical applicability of Pade approximation. One important issue concerns stability. The stabile transfer function of wavelet filter does not automatically result from the Pade approximation technique. If the selection of the point s0 is improper, the result of approximation will be unstable. Some poles of the Morlet wavelet transfer function obtained by this method in Haddad et al. (2005) lie in the right half of the s-plane, which indicates the transfer function is not stable. Another important drawback is: the quality of the approximation of the wavelet is not measured directly in the time domain but in the Laplace domain, which results in a larger error of approximation. The performance of implementing WT in analog domain depends largely on the accuracy of the approximations involved in this approach. Karel et al. (2005), an alternative approach, based on L2 approximation that works directly in the time domain, was introduced. A drawback of this approach is that the numerical optimization of objective function usually ends in local, non-global optimization when a starting point is not exactly selected. To find a good starting point for L2 approximation, a method involving high-order FIR approximation and balance-and-truncate model reduction is used. However, it is a computational complex method and limited to approximate such low order wavelet functions as the Gaussian and Daubechies. This method has also some convergence problems when one tries to approximate a function with many oscillations (high order wavelet), such as the Morlet wavelet. So far, there is a lack of the effective method to approximate various low or high order wavelet functions, which is an obstacle for implementing WT in analog domain.

In this study, we focus on the wavelet approximation for implementation in analog circuits. The innovative aspect of the present work is threefold. First, by extending pioneering work (Karel et al., 2005; Hongmin et al., 2008; Li et al., 2010; Gurrola-Navarro et al., 2010), we propose a generalized optimization mathematical model of approximating various wavelet functions, which is based on the L2 approximation. Second, the Particle Swarm Optimization (PSO) (Kennedy and Eberhart, 1995) algorithm is introduced to solve the optimization problem. The PSO algorithm is one of the most powerful methods for solving global optimization problems and is effective, efficient and fairly robust to initial conditions. This method overcomes these shortcomings of approximation technique in Haddad et al. (2005) and Karel et al. (2005). Using PSO algorithm, we have successfully approximated various wavelet functions, especially the Morlet wavelet (a high order wavelet).

WAVELET TRANSFORM

The wavelet transform provides a time-frequency representation of the signal (Mallat, 1999; Walnut, 2004). It was developed to overcome the short coming of the Short Time Fourier Transform (STFT), which can also be used to analyze non-stationary signals. While STFT gives a constant resolution at all frequencies, the wavelet transform uses multi-resolution technique by which different frequencies are analyzed with different resolutions.

The definition of the Continuous Wavelet Transform (CWT) for a real valued time signal x (t) is given as (Mallat, 1999):

Image for - A PSO Method for Wavelet Approximation
(1)

where, a is scale parameter (a∈ (0, R)) and τ is translation parameter (τ∈R). The base function Ψ (t) (Ψ (t)∈L(R)2) is called the mother wavelet. The mother wavelet used to generate all the basis functions is designed based on some desired characteristics associated with that function. The translation parameter τ relates to the location of the wavelet function as it is shifted through the signal. Thus, it corresponds to the time information in the Wavelet Transform. The scale parameter α is defined as |1/frequency| and corresponds to frequency information. Scaling either dilates (expands) or compresses a signal. Large scales (low frequencies) dilate the signal and provide detailed information hidden in the signal, while small scales (high frequencies) compress the signal and provide global information about the signal. The above equation shows that the wavelet transform performs the convolution operation of the signal and the basis function.

The mother wavelet must satisfy two restriction conditions. One is:

Image for - A PSO Method for Wavelet Approximation
(2)

This ensures the mother wavelet has no DC component and is fast in decaying rate. The other is the admissibility condition, i.e,:

Image for - A PSO Method for Wavelet Approximation
(3)

where, Ψ (w) is the Fourier transform of the mother wavelet ι (t). The second restriction in Eq. 3 is stronger than the first one. The reason for requiring this condition is to guarantee that the reconstruction of the original time signal from the continuous wavelet transform is possible. Wavelet transforms usually cannot be implemented exactly in analog electronic hardware. If a time signal x (t) is passed through a linear system, then x (t) is convolved with the impulse response h (t) of that linear system, producing the output signal:

Image for - A PSO Method for Wavelet Approximation

On the other hand, from the definition of WT given by Eq. 1, the analog computation of WTx (a, t) (scale a) can be achieved through the implementation of a linear filter of which the impulse response satisfies:

Image for - A PSO Method for Wavelet Approximation
(4)

For obvious physical reasons only the hardware implementation of (strictly) causal stable filters is feasible. In other words, a linear filter will have a (strictly) proper rational transfer function H (s) that has all its poles in the complex left half plane. Because the h (t) will then be zero for negative t, any mother wavelet Ψ (t) which does not have this property must be time-shifted to facilitate an accurate approximation of its (correspondingly time-shifted) wavelet transform WTx (a, t). This may result in a truncation error for a wavelet that does not have compact support, such as the Gaussian wavelet. Note that an approximation error will also be due to the fact that a wavelet does not usually possess a rational Laplace transform.

L2 APPROXIMATION OF WAVELET FUNCTIONS BASED ON PSO ALGORITHM

Generalized optimization model of l2 approximation of wavelet functions: The theory of L2 approximation (Karel et al., 2005) provides an alternative framework for studying the problem of wavelet approximation which offers a number of advantages. On the conceptual level it is quite appropriate to use the L2 norm to measure the quality of an approximation h (t) of the function Image for - A PSO Method for Wavelet Approximation. Indeed, the very definition of the wavelet transform itself involves the L2 inner product between the signal x (t) and the mother wavelet Ψ (t). It is also desirable that the approximation h (t) of Image for - A PSO Method for Wavelet Approximation (t) behaves equally well for all time instances t since h (t) is used as a convolution kernel with any arbitrary shift. This property holds naturally for L2 approximation but it is not supported by the Pade approximation approach. Another advantage of L2 approximation is that it allows for a description in the time domain as well as in the Laplace domain, so that both frameworks can be exploited to develop further insight. According to Parseval’s equality the squared L2 norm of the difference between Image for - A PSO Method for Wavelet Approximation (t) and h (t) can be expressed as:

Image for - A PSO Method for Wavelet Approximation
(5)

Minimization of Image for - A PSO Method for Wavelet Approximation is therefore equivalent to minimization of the L2 norm of the difference between the Laplace transforms Image for - A PSO Method for Wavelet Approximation (t) and H (s) over the imaginary axis s = iw.

Particularly in the case of low order approximation, the L2 approximation problem can be approached in a simple and straightforward way in the time domain. As is well known from linear systems theory any strictly causal linear filter of finite order n can be represented in the time domain by the impulse response function h (t) (its Laplace transform H (s)). For the generic situation of stable systems with distinct poles, the impulse response function h (t) is a linear combination of damped exponentials and exponentially damped harmonics. For low order systems, this makes it possible to propose an explicitly parameterized class of impulse response functions among which to search for a good approximation of Image for - A PSO Method for Wavelet Approximation (t). For instance, if a Nth order approximation is attempted, this parameterized class of functions h (t) may typically have the following form:

Image for - A PSO Method for Wavelet Approximation
(6)

where, the parameters bi and dj must be strictly negative for reasons of stability. When the expression of wavelet functions includes sine term A cos(Ωt), such as the Morlet Wavelet, the h (t) may be given by:

Image for - A PSO Method for Wavelet Approximation
(7)

Note that wavelets typically are oscillatory functions so that a good fit requires the contribution of sufficiently many damped harmonics, which further explains the structure of this class. Given the explicit form of the wavelet Image for - A PSO Method for Wavelet Approximation (t) and the parameterized class of functions h (t), the L2 norm of the difference Image for - A PSO Method for Wavelet Approximation can now be minimized in a straightforward way using standard numerical optimization techniques and software. The negativity constraints on bi and dj which enforce stability are not difficult to handle.

One common property of a wavelet function Image for - A PSO Method for Wavelet Approximation (t) that wasn’t discussed so far is that its integral is usually equal to zero:

Image for - A PSO Method for Wavelet Approximation

If this property is not shared by the approximation h (t), this will cause an unwanted bias in the approximation of the wavelet transform. So we have that:

Image for - A PSO Method for Wavelet Approximation
(8)

This yields the explicit nonlinear condition, if such an extra nonlinear condition is not conveniently handled by the optimization software, then it can easily be used to eliminate one of the variables from the problem. Based on the analysis above, a generalized optimization mathematical model of approximating various wavelet functions is then given by:

Image for - A PSO Method for Wavelet Approximation
(9)

This is a typical nonlinear and constrained optimization question. It is difficult to obtain the global optimal solution using common numerical optimization techniques, which in general provide no global optimality guarantee and give different local optima with different starting points.

Particle swarm optimization (PSO) algorithm: The PSO algorithm is one of the most powerful methods for solving global optimization problems and is effective, efficient and fairly robust to initial conditions. In order to optimize parameters of h (t), we use the Particle Swarm Optimization (PSO) algorithm to solve the optimization question in (9), search the whole parameters space effectively and globally.

Particle swarm optimization algorithms (Kennedy and Eberhart, 1995) are evolutionary computation. The particle swarm optimizer algorithms find optimal regions of complex search space through the interaction of individuals in a population of particles. The rapid speed of calculation and simple realization are its excellent performance. Precision is not good. PSO is a population-based, bio-inspired optimization method. It was originally inspired in the way crowds of individuals move towards predefined objectives, but it is better viewed using a social metaphor. PSO is similar to the other evolutionary algorithms in that the system is initialized with a population of random solutions. However, each potential solution is also assigned a randomized velocity and the potential solutions, call particles, corresponding to individuals. Each particle in PSO flies in the D-dimensional problem space with a velocity which is dynamically adjusted according to the flying experiences of its own and its colleagues. The location of the ith particle is represented as Xi = (xi1, …, xid, …, xiD), where xid ∈ [ld, ud], d ∈ [1, D], ld, ud are the lower and upper bounds for the dth dimension, respectively. The best previous position (which giving the best fitness value) of the ith particle is recorded and represented as Pi = (pi1,…, pid, …, piD), which is also called pbest. The index of the best particle among all the particles in the population is represented by the symbol g. The location Pg is also called gbest. The velocity for the ith particle is represented as Vi = (vi1, …, vid, …, viD), is clamped to a maximum velocity Vmax = (vmax1, …, vmaxd, …, vmaxD), which is specified by the user. The particle swarm optimization concept consists of, at each time step, changing the velocity and location of each particle toward its pbest and gbest locations according to the Eq. 10 and 11, respectively:

Image for - A PSO Method for Wavelet Approximation
(10)

xid = xid+vid
(11)

where, w is inertia weight, c1 and c2 are acceleration constants and rand() is a random function in the range [0, 1]. For Eq. 10, the first part represents the inertia of pervious velocity; the second part is the “cognition” part, which represents the private thinking by itself; the third part is the “social” part, which represents the cooperation among the particles. If the sum of accelerations would cause the velocity vid on that dimension to exceed vmaxd, then vid is limited to vmaxd.

APPROXIMATION OF THE COMMON WAVELET FUNCTIONS

Approximation of gaussian and morlet wavelet: To demonstrate the proposed method, we first discuss how to approximate Marr wavelet base. Marr wavelet is a favorite choice in many signal processing applications. The Marr wavelet Ψ (t) is the second derivative of a Gaussian probability density function:

Image for - A PSO Method for Wavelet Approximation
(12)

Select the time-shift t0 = 4, get time-reversed and time-shifted Marr wavelet Ψ (4-t). Let h (t) be the impulse response of Marr wavelet filter to be designed and the order of wavelet filter N be 9, then the parameterized class of functions h (t) given by:

Image for - A PSO Method for Wavelet Approximation
(13)

Note that choice of order of wavelet filter involves an important trade-off between optimal solution and complexity of filter circuits. If N is chosen too small, the h (t) may be far away from the versatile wavelet. On the other hand, if N is chosen too large, a more complex analog IC is demanded to realize wavelet transform. We define the distance between h (t) and Ψ (t-4):

Image for - A PSO Method for Wavelet Approximation
(14)

where, a = (a1, a2, a3, …, a18)T is an undetermined parameter vector. To sample D (a), the fitness function is given:

Image for - A PSO Method for Wavelet Approximation
(15)

The optimization model of approximating Marr wavelet function is described as:

Image for - A PSO Method for Wavelet Approximation
(16)

This is a nonlinear constrained optimization question. Using the proposed hybrid algorithm to solve Eq. 16, the parameters for PSO are set as: Population size i = 100, Inertia weight factor wmin = 0.4, wmax = 0.9, acceleration constant c1 = c2 = 2, maximum iteration N = 9000. The position and the velocity of the i th particle and the fitness function of corresponding sampling point in the nth iteration are denoted by Image for - A PSO Method for Wavelet Approximation. Its local best position and the global best position of the particle swarm are denoted as Pi and Pg , respectively. The PSO optimization program is run in MATLAB 7.1 and the search process of PSO is shown in Fig. 1. Because PSO is a stochastic algorithm, it is difficult to guarantee a global optimal solution only by a certain experiment. Here, the number of experiments is set to 25. After finishing many times test, the best global solution are selected, which is shown in Table 2. To replace the parameters in Eq. 13 with a in Table 1, the following Marr wavelet filter transfer function can be obtained:

Table 1: Optimum a for Marr wavelet approximation
Image for - A PSO Method for Wavelet Approximation

Table 2: Optimum a for Morlet wavelet approximation
Image for - A PSO Method for Wavelet Approximation

Image for - A PSO Method for Wavelet Approximation
Fig. 1: Search process of PSO for approximating Marr wavelet

Image for - A PSO Method for Wavelet Approximation
(17)

Image for - A PSO Method for Wavelet Approximation
Fig. 2: Approximation of the Marr wavelet

Image for - A PSO Method for Wavelet Approximation
(18)

where, H (s) is the wavelet filter to realize WtxA (1, τ) under scale 1. By the theory of Laplace transform, the transfer function of analog wavelet filter under certain scale a is expressed as Image for - A PSO Method for Wavelet Approximation. The ime-domain waveform of approximated Marr wavelet in Fig. 2 it inherits the excellent qualities of Mar wavelet.

Now, we consider approximation of the Morlet wavelet. Morlet wavelet Ψ (t) is defined:

Image for - A PSO Method for Wavelet Approximation
(19)

Choosing the time-shift t0 = 3, this gives rise to the following time-reversed and time-shifted wavelet function:

Image for - A PSO Method for Wavelet Approximation
(20)

To obtain a stable 10th order approximation of Image for - A PSO Method for Wavelet Approximation (t), the L2 approximation technique was applied using the parameterized class of functions h (t) given by Eq. (7):

Image for - A PSO Method for Wavelet Approximation
(21)

where, the parameters a2, a4 and a8 must be strictly negative for reasons of stability. Given the explicit form of Image for - A PSO Method for Wavelet Approximation (t) and the parameterized class of functions h (t), the squared L2 norm of the difference between Image for - A PSO Method for Wavelet Approximation (t) and h (t) is expressed as:

Image for - A PSO Method for Wavelet Approximation
(22)

where, a = (a1, a2, a3, …, a10)T is parameter vector. The sum of squares error of nonlinear functions is expressed by E (a):

Image for - A PSO Method for Wavelet Approximation
(23)

where, the sampling time interval equal 0.01 (ΔT = 0.01). The optimization problem is described as:

Image for - A PSO Method for Wavelet Approximation
(24)

From:

Image for - A PSO Method for Wavelet Approximation

this yields the constrained condition:

Image for - A PSO Method for Wavelet Approximation
(25)

Using the Particle Swarm Optimization (PSO) algorithm to solve Eq. 26, the parameters for carrying out PSO are: Population size I = 80, Inertia weight factor wmin = 0.4, wmax = 0.9, acceleration constants c1 = c2 = 2, maximum iteration N = 6000. The optimum parameter a = (a1, a2, a3, …, a10)T was obtained in Table 2.

The following filter was obtained:

Image for - A PSO Method for Wavelet Approximation
(26)

The corresponding wavelet approximation h (t) is shown in Fig. 3, yielding an L2 approximation error equal to 0.0015.

APPROXIMATION PERFORMANCE COMPARISON

To determine the quality of the wavelet approximations obtained with the three kinds of techniques: pade approximation (Haddad et al., 2005), L2 approximation (Karel et al., 2005) and L2 approximation based on PSO, one may resort to the computation of their L2 approximation errors. L2 approximation errors have been calculated for three different wavelet approximations: the approximation of Gaussian wavelet, the approximation of Marr wavelet and the approximation of Morlet wavelet.

Table 3: Comparison of approximation performance
Image for - A PSO Method for Wavelet Approximation

Image for - A PSO Method for Wavelet Approximation
Fig. 3: Approximation of the Morlet wavelet

The calculated results are listed in Table 3. From the results in Table 3, the approximation errors using L2 approximation based on PSO are the least. One major advantage of the L2 approximation based on PSO is that it can approximate excellently various wavelet functions. In the pade approximation (Haddad et al., 2005), this improper selection of the point s0 = 0 resulted in an unstable transfer function of Morlet wavelet. With a longer running time, L2 approximation (Karel et al., 2005) algorithm is capable of finding the global optimal parameters for low order wavelets. However, this method has some convergence problems when one tries to approximate a function with many oscillations (high order wavelet), such as the Morlet wavelet. From the comparison, it is obvious that the L2 approximation based on PSO method is superior to Pade approximation and L2 approximation.

CONCLUSION

For implementing wavelet transforms in analog circuits, a novel method to approximate various wavelet functions is proposed. To approximate a wavelet with this method, an optimization mathematical model based on the L2 approximation must be given. Then, the Particle Swarm Optimization (PSO) algorithm is used to solve the optimization problem. Because the PSO algorithm is one of the most powerful methods for solving global optimization problems and is effective, efficient and fairly robust to initial conditions, the proposed method overcomes these shortcomings of approximation technique in Haddad et al. (2005) and Karel et al. (2005). With proposed approach it can approximate wavelets that can not be approximated sufficiently well with an acceptable order in a straightforward way with the Pade approach or L2 approximation.

ACKNOWLEDGMENTS

The authors thank the Natural Science Foundation of Hunan Province of China (Grant No. 11JJ3078), China Postdoctoral Science Foundation (Grant No. 2012M521215) and National Natural Science Funds of China for Distinguished Young Scholar under (Grant No. 50925727).

REFERENCES

1:  Karel, J.M.H., S.A.P. Haddad, S. Hiseni and R.L. Westra, 2012. Implementing wavelets in continuous-time analog circuits with dynamic range optimization. IEEE Trans. Circuits Syst. I: Regul. Pap., 59: 229-242.
CrossRef  |  

2:  Gurrola-Navarro, M.A. and G. Espinosa-Flores-Verdad, 2010. Analogue wavelet transform with single biquad stage per scale. Electron. Lett., 46: 616-618.
CrossRef  |  

3:  Haddad, S.A.P., S. Bagga and W.A. Serdijn, 2005. Log-domain wavelet bases. IEEE Trans. Circuits Syst. I: Regul. Pap., 52: 2023-2032.

4:  Karel, J.M.H., R.L.M. Peeters, R.L. Westra, S.A.P. Haddad and W.A. Serdijn, 2005. An L2-based approach for wavelet approximation. Proceedings of the 44th IEEE Conference on Decision and Control, 2005 and 2005 European Control Conference, December, 12-15, 2005, Portugal, pp: 7882-7887
CrossRef  |  

5:  Baker Jr., G.A., 1975. Essentials of Pade Approximants. Academic Press, New York

6:  Bultheel, A. and M.V. Barel, 1986. Pade techniques for model reduction in linear system theory: A survey. J. Comput. Applied Math., 14: 401-438.

7:  Kennedy, J. and R. Eberhart, 1995. Particle swarm optimization. Proc. IEEE Int. Conf. Neural Networks, 4: 1942-1948.
CrossRef  |  Direct Link  |  

8:  Mallat, S., 1999. A Wavelet Tour of Signal Processing. 2nd Edn., Academic Press, San Diego, California, USA.

9:  Walnut, D.F., 2004. An Introduction to Wavelet Analysis. Birkhauser Press, Boston

10:  Hongmin, L., H. Yigang and Y. Sun, 2008. Detection of cardiac signal characteristic point using log-domain wavelet transform circuits. Circuits Syst. Signal Process., 27: 683-698.
CrossRef  |  

11:  Li, H., H. Gang, G. Zhang and G. Guo, 2010. Log-domain implementation of analog wavelet filters. Proceedings of the International Conference on Intelligent Control and Information Processing (ICICIP), August 13-15, 2010, Dalian, pp: 187-190
CrossRef  |  

©  2022 Science Alert. All Rights Reserved