# A Class of Algorithms for Continuous Wavelet Transform Based on the Circulant Matrix
## 1 Introduction  
In recent years, different Time-frequency representations, such as, empirical mode decomposition [1], wavelet transform [2] and its variants, empirical wavelet transform [3, 4], synchrosqueezed wavelet transforms [5], have been used for analyzing nonlinear and non-stationary signals. To name only a few, the method of fused empirical mode decomposition and wavelets is applied to detection-location of damage in a truss-type structure [6]; Wavelet transform is used for the pattern recognition for diagnosis, condition monitoring and fault detection [7, 8, 9]. It is also used to design an algorithm for Brain-computer interfacing [10], to detect the exact onset of chipping of the cutting tool from the workpiece profile [11], to determine the length of piles [12]; Synchrosqueezed wavelet transform is used for global and local health condition assessment of structures [13], for modal parameters identification of smart civil structures [14]. This paper gives priority to the computation of continuous wavelet transform (CWT) for Morlet-type wavelets. However, for this type of wavelets, it is not possible to use a multiresolution framework for the computation of CWT [15]. [PERSON] [16] used Exponentials or B-spline window to approximate Gabor window, which can achieve \(\mathcal{O}(N)\) complexity per scale. Another kind of method for the computation of CWT with Morlet-type wavelets concerns directly discretizing theintegral expression of Wavelet transform. These methods allow us to use arbitrary values for the scale variable, and require the explicit expression of wavelet function and cannot deal with those wavelets without analytic expressions such as Daubechies wavelets [17]. This kind of method include Time-domain methods [17] and Frequency-domain methods [18]. Frequency-domain methods for CWT are also widely used in the freewares such as JLAB (available online [[http://www.jmlilly.net](http://www.jmlilly.net)]([http://www.jmlilly.net](http://www.jmlilly.net))), Wavelab (available online [[http://www-stat.stanford.edu/](http://www-stat.stanford.edu/)]([http://www-stat.stanford.edu/](http://www-stat.stanford.edu/))$~sim$wavelab), which can achieve satisfactory precision while the edge effect, defined in [18], may occur and the complexity of those methods is \(\mathcal{O}(N\log(N))\) where \(N\) is the length of the signal. The function _cwt_ in wavelet toolbox of MATLAB, which has poorer precision than Frequency-domain methods mentioned above, is a representation of the Time-domain method [17]. For the details of the comparison of the different methods, we refer to [17]. The computation of linear convolution can be realized by using the circular convolution, while the computation of circular convolution can be computed by using the FFT-based fast method [19]. In this paper, a novel and simple method is given to prove the FFT-based fast method of linear convolution by exploiting the structures of circulant matrix. After introducing Equivalent Condition of Time-domain and Frequency-domain Algorithms of CWT, a class of algorithms for continuous wavelet transform are proposed and analyzed, which can cover the algorithms in JLAB and WaveLab, as well as the other existing methods such as the _cwt_ function in the toolbox of MATLAB. In this framework, two theoretical issues for the computation of CWT are analyzed. Firstly, by using Equivalent Condition of Time-domain and Frequency-domain Algorithms of CWT to design Frequency-domain Algorithm, the edge effect, defined in [18], can be avoided. To be specific, in [18], the time series is padded with sufficient zeroes to bring the total length \(N\) up to the next-higher power of two, thus limiting the edge effects and speeding up the Fourier transform. In fact, the same number of zeros is padded for all scales in [18], which may cause some troubles, for example, increasing the amount of data to process, and consequently the computational complexity. In this article, the time series (the data) is padded with \(2 aT\) zeros while \(a\) is the scale.