157 General Case of Wavelet Transform with Reducible Rational Dilation Factor © Oleg Chertov1[0000-0003-0087-1028] and © Volodymyr Malchykov1[0000-0002-1710-9171] 1 National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, Ukraine mavr2k@gmail.com Abstract. Datasets of different nature can be effectively analyzed with the help of wavelet analysis. There are two types of discrete wavelet transforms – dyadic and non-dyadic. The latter one allows for more accurate detection and separation of features that are present in analyzed data. A lot of methods use the irreducible fractions as a dilation factor for rational wavelet transform. In this paper the gen- eral case of reducible rational dilation factor will be considered. The procedure for building filters will be shown as well as the perfect reconstruction condition. Also, an approach for selecting the best reducible rational dilation factor will be proposed. Keywords: Wavelet Transform, Non-Dyadic Wavelet, Dilation Factor. 1 Introduction Wavelet transform (WT) is widely used to analyze datasets of various types. WT has proved its efficiency in analysis of medical signals [1], processing of multimedia data [2], speech and image recognition, etc. According to the value of dilation factor discrete WT are classified into dyadic, where dilation factor equals 2, and non-dyadic in other cases. Dyadic WT are often used, but non-dyadic wavelet transform can be more suitable for precise localization of signal singularities and similar tasks. Various authors proposed their own approaches to non-dyadic WT. Their properties and main features are shortly described in previous work [3]. Rational multiresolution analysis [4] looks like the simplest, but the most effective method among all others. 2 Problem Formulation Usually, the irreducible dilation factor is used in rational wavelet transforms. But in some cases, using the reducible dilation factor can improve the quality of wavelet anal- ysis. Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 158 The conditions for building filters for the dilation factor that equals 6/4 were shown earlier [3, 5]. The purpose of the current work is to generalize these conditions to the arbitrary reducible fraction. Also, authors will generalize the perfect reconstruction condition for this case. The criteria for selecting the best value of rational dilation factor from a set of pro- portional fractions will be introduced. 3 Problem Solution 3.1 Conditions for Filters Coefficients Let’s take arbitrary reducible fraction as a dilation factor of rational wavelet trans- form 𝑝 𝑁 , 𝑝 𝛼∙𝑝 , 𝑞 𝛼 ∙ 𝑞 , 𝛼 ∈ ℕ, 𝛼 2 𝑞 where fraction 𝑝 𝑞 is irreducible. We have function 𝑝 𝜑 ∈ 𝑉 𝑉 𝑆𝑝𝑎𝑛 𝜑 ∙ 𝑛 𝑞 that can be represented as 𝑝 𝑝 𝜑 𝑥 ℎ 𝜑 𝑥 𝑛 𝑞 𝑞 Let’s define set of functions 𝑝 𝑝 𝑝 𝑝 𝜑 𝑥 𝑞𝑙 ℎ 𝜑 𝑥 𝑞𝑙 𝑛 ℎ 𝜑 𝑥 𝑝𝑙 𝑛 𝑞 𝑞 𝑞 𝑞 𝑝 𝑝 ℎ 𝜑 𝑥 𝑘 𝑞 𝑞 This set of functions has to be orthonormal, then 159 𝛿 〈𝜑 𝑥 , 𝜑 𝑥 𝑞𝑙 〉 𝜑 𝑥 ∙𝜑 𝑥 𝑞𝑙 𝑑𝑥 ℝ 𝑝 𝑝 𝑝 𝑝 ℎ 𝜑 𝑥 𝑛 ℎ 𝜑 𝑥 𝑘 𝑑𝑥 𝑞 𝑞 𝑞 𝑞 ℝ 𝑝 𝑝 𝑝 ℎ ℎ 𝜑 𝑥 𝑛 ∙𝜑 𝑥 𝑘 𝑑𝑥 ℎ ℎ 𝑞 𝑞 𝑞 ℝ So, orthonormality of the set of functions 𝜑 ∙ 𝑞𝑙 implies the condition ℎ ℎ 𝛿 Let’s take functions 𝜑 𝑥 1 , 𝜑 𝑥 2 , …, 𝜑 𝑥 𝑞 2 , 𝜑 𝑥 𝑞 1 from the same V0. Due to this fact we can write each of these functions as 𝑝 𝑝 𝜑 𝑥 𝑗 ℎ ∙𝜑 𝑥 𝑛 , 𝑗 1…𝑞 1 𝑞 𝑞 Then for each function 𝜑 𝑥 𝑗 we define a set of functions 𝜑 ∙ 𝑞𝑙 𝑗 as 𝑝 𝑝 𝜑 𝑥 𝑞𝑙 𝑗 ℎ 𝜑 𝑥 𝑞𝑙 𝑛 𝑞 𝑞 𝑝 𝑝 𝑝 𝑝 ℎ 𝜑 𝑥 𝑝𝑙 𝑛 ℎ 𝜑 𝑥 𝑘 𝑞 𝑞 𝑞 𝑞 Each such set of functions has to be orthonormal, so 𝛿 〈𝜑 𝑥 𝑗 ,𝜑 𝑥 𝑞𝑙 𝑗 〉 𝜑 𝑥 𝑗 ∙𝜑 𝑥 𝑞𝑙 𝚥 𝑑𝑥 ℝ 𝑝 𝑝 𝑝 𝑝 ℎ 𝜑 𝑥 𝑛 ℎ 𝜑 𝑥 𝑘 𝑑𝑥 𝑞 𝑞 𝑞 𝑞 ℝ 160 𝑝 𝑝 𝑝 ℎ ℎ 𝜑 𝑥 𝑛 ∙𝜑 𝑥 𝑘 𝑑𝑥 ℎ ℎ 𝑞 𝑞 𝑞 ℝ This gives us q-1 conditions for filter coefficients: ℎ ∙ℎ 𝛿 , 𝑗 1…𝑞 1 Also, all sets of functions 𝜑 ∙ 𝑞𝑙 𝑗 , 𝑗 0…𝑞 1 have be mutually orthogonal 0 〈𝜑 𝑥 𝑗 ,𝜑 𝑥 𝑞𝑙 𝚥̃ 〉 𝜑 𝑥 𝑗 ∙𝜑 𝑥 𝑞𝑙 𝚥̃ 𝑑𝑥 ℝ 𝑝 𝑝 𝑝 ̃ 𝑝 ℎ 𝜑 𝑥 𝑛 ℎ 𝜑 𝑥 𝑘 𝑑𝑥 𝑞 𝑞 𝑞 𝑞 ℝ 𝑝 ̃ 𝑝 𝑝 ̃ ℎ ℎ 𝜑 𝑥 𝑛 ∙𝜑 𝑥 𝑘 𝑑𝑥 ℎ ℎ 𝑞 𝑞 𝑞 ℝ where 𝑗, 𝚥̃ 0…𝑞 1, 𝑗 𝚥̃ This gives us next conditions: ̃ ℎ ∙ℎ 0, 𝑗, 𝚥̃ 0…𝑞 1, 𝑗 𝚥̃ Finally, we have next conditions for low-pass filter coefficients: ⎧ ℎ ∙ℎ 𝛿 , 𝑗 1…𝑞 1 ⎪ ⎨ ℎ ∙ℎ ̃ 0, 𝑗, 𝚥̃ 0…𝑞 1, 𝑗 𝚥̃ ⎪ ⎩ Now let’s denote the Fourier transform of function 𝜑 𝑥 as 𝜑 𝜔 . Applying the Fourier transform to the 𝑝 𝑝 𝜑 𝑥 𝑗 ℎ ∙𝜑 𝑥 𝑛 , 𝑗 0…𝑞 1 𝑞 𝑞 161 we will get 𝑝 𝑞 𝑞 𝑞 𝑞 𝜑 𝜔 ∙𝑒 ℎ ∙ 𝜑 𝜔 ∙𝑒 ℎ ∙𝑒 ∙𝜑 𝜔 𝑞 𝑝 𝑝 𝑝 𝑝 that can be rewritten as 𝑞 𝑞 𝜑 𝜔 ∙𝑒 𝑚 𝜔 ∙𝜑 𝜔 𝑝 𝑝 where functions 𝑚 𝜔 are defined according to 𝑚 𝜔 ∑ ℎ ∙𝑒 (1) Next, we define p-q wavelet functions 𝑝 𝑝 𝜓 𝑥 𝑔 ∙𝜑 𝑥 𝑛 , 𝑗 1…𝑝 q 𝑞 𝑞 From the orthonormality of these functions and their orthogonality to the functions  we get next conditions: ⎧ 𝑔 ∙𝑔 𝛿 , 𝑗 1…p 𝑞 ⎪ ⎪ ̃ 𝑔 ∙𝑔 0, 𝑗, 𝚥̃ 1…p 𝑞, 𝑗 𝚥̃ ⎨ ⎪ ⎪ ̃ 𝑔 ∙ℎ 0, 𝑗 1…p 𝑞, 𝚥̃ 0…𝑞 1 ⎩ Based on wavelet functions we build functions 𝑚 𝜔 ∑ 𝑔 ∙𝑒 , 𝑗 1…𝑝 𝑞 (2) that satisfy 𝑞 𝑞 𝜓 𝜔 𝑚 𝜔 ∙𝜓 𝜔 , 𝑗 1…𝑝 𝑞 𝑝 𝑝 where 𝜓 𝜔 , 𝑗 1…𝑝 𝑞 are the Fourier transform of the corresponding wavelet functions. 162 3.2 Perfect Reconstruction Condition Let’s define matrix M() based on introduced functions 𝑚 𝜔 and 𝑚 𝜔 : 𝑚 𝜔 .. 𝑚 𝜔 𝑚 𝜔 .. 𝑚 𝜔 ⎛ 𝑚 𝜔 .. 𝑚 𝜔 𝑚 𝜔 .. 𝑚 𝜔 ⎞ ⎜ .. .. .. .. .. .. ⎟ ⎜ .. .. .. .. .. .. ⎟ ⎜𝑚 𝜔 .. 𝑚 𝜔 𝑚 𝜔 .. 𝑚 𝜔 ⎟ ⎝𝑚 𝜔 .. 𝑚 𝜔 𝑚 𝜔 .. 𝑚 𝜔 ⎠ where arguments 𝜔 , 𝑘 0…𝑛 1 are defined according to the formula: 𝑘 𝜔 𝜔 2𝜋 , 𝑘 0…𝑛 1 𝑝 Matrix A is defined as 𝐀 𝐌∗ 𝜔 ∙ 𝐌 𝜔 where 𝐌 ∗ 𝜔 is a complex conjugate of the transposition of 𝐌 𝜔 . Let’s show that matrix A satisfies the condition 𝐀 𝑞∙𝐈 (3) where 𝐈 is a unit matrix of dimension p. In [6] Li shows that for the irreducible dilation factor of rational wavelet transform such expression gives a necessary and suf- ficient condition for perfect reconstruction. For this purpose, we will calculate elements of matrix A. Diagonal elements of this matrix can be written as ⎧ 2𝜋 2𝜋 ⎪ 𝑚 𝜔 𝑙∙ ∙𝑚 𝜔 𝑙∙ , 𝑗 1…𝑞 𝑝 𝑝 𝑎 ⎨ 2𝜋 2𝜋 ⎪ 𝑚 𝜔 𝑙∙ ∙𝑚 𝜔 𝑙∙ , 𝑗 𝑞 1…𝑝 ⎩ 𝑝 𝑝 After substituting expressions (1) and (2), multiplying sums and grouping of similar elements we get ⎧𝑞 ⎪𝑝 ℎ ∙ℎ ∙𝑒 ∙ 𝑒 , 𝑗 1…𝑞 𝑎 ⎨𝑞 ⎪ 𝑔 ∙𝑔 ∙𝑒 ∙ 𝑒 , 𝑗 𝑞 1…𝑝 ⎩𝑝 163 Let’s take a look at the last multiplier. After substituting n-k by m it can be written as 𝑢 𝑚 𝑒 1 𝑒 ⋯ 𝑒 𝑒 After denoting 𝜌 ≡ 𝑒 we can write this expression as 𝑢 𝑚 1 ρ ⋯ 𝜌 𝜌 If  does not equal to one, then we can multiply last expression by 1- and get 𝑢 𝑚 1 𝜌 1 ρ ⋯ 𝜌 𝜌 1 𝜌 1 𝜌 ∙ Due to the fact that 𝜌 𝑒 𝑒 1 we get that in this case 1 𝜌 𝑢 𝑚 0 1 ρ If  equals one, i.e. for the values of m that are multiplies of the numerator, then from the definition of the function it immediately follows that in this case 𝑢 𝑚 1 So, now we can write the values of the diagonal elements of matrix A as ⎧𝑞 ℎ ∙ℎ ∙𝑒 , 𝑗 1…𝑞 ⎪ 𝑎 ⎨𝑞 𝑔 ∙𝑔 ∙𝑒 , 𝑗 𝑞 1…𝑝 ⎪ ⎩ that, after taking into account conditions for filters coefficients, gives us 𝑎 𝑞, 𝑗 1…𝑝 It can be easily shown in a similar way that all extradiagonal elements of the matrix A are zeros. So, matrix A satisfies condition (3). This means that it can be looked as a condition for the perfect reconstruction in the case of reducible dilation factor of rational wavelet transform. 3.3 Dilation Factor Selecting Criterion In order to select optimal value from the set of reducible fractions that all are the mul- tipliers of the same irreducible rational number authors propose to use entropy-based criterion. Entropy is usually understood as a measure of uncertainty or unpredictability of in- formation [7]. In [7, 8] entropy was proposed to use in order to find the optimal signal 164 decomposition. In their previous work [9] authors also used entropy for selecting an optimal irreducible dilation factor. Calculation of entropy for the rational wavelet decomposition at the level N of the signal is based on relative energy. First, it is necessary to find the energy Ej at the level j of the decomposition 1 𝐸 𝑑, 𝑁 where dj,k are the detailed coefficients at this level and Nj is the whole number of the coefficients. Next, the relative energy Pj that shows the distribution of energy by levels is calcu- lated 𝐸 𝑃 ∑ 𝐸 And at last entropy is calculated according to the expression 𝐸𝑛𝑡𝑟 𝑃 ∙ 𝑙𝑛 𝑃 3.4 Experimental Results We will illustrate the process of selecting the reducible dilation factor by the decompo- sition of signal of the spontaneous electromagnetic emission of the Earth. The whole set of data was measured by “Yugneftegazgeologiya” company during the experiments on the September, 2012 in Bazeliyivka, Ukraine. Fig. 1 shows the first second of the X channel record made by one of the mobile measurement stations at the “zero” point. Fourier spectrum of this signal is shown at the Fig. 2. Due to the Fourier spectrum and nature of the measured signal a decision to analyze it by rational wavelet transform with the value of 5/3 for dilation factor was made first. Two other values – 10/6 and 15/9 – for the dilation factor were also considered. In order to select the most optimal value entropy-based criterion was used. Results are shown in Table 1. The minimum value of entropy is bolded. Entropy for dyadic wavelet decomposition is also included for comparison. Table 1. Entropy for selected values of dilation factor Dilation factor value Entropy 5/3 0.1071 10/6 0.1066 15/9 0.1071 2 0.3175 165 Fig. 1. Measured signal Fig. 2. Fourier spectrum of the signal Fig. 3 illustrates the advantages of dilation factor 10/6 vs 5/3 in singularities sepa- rating. 166 Fig. 3. Detailed components of third level on Fourier spectrum. Orange vertical lines bound the frequency band of Fourier spectrum that corresponds to the detailed components on third level of wavelet decomposition. Dark red vertical line separates the frequency intervals for the detailed components of decomposition with dilation factor 5/3. Green vertical lines show the spectrum bands for the detailed components of rational wavelet decomposition with dilation factor 10/6. It can be easily seen that in the second case singularities of the signal are better sep- arated from each other. Further fragmentation of frequency band into smaller parts leads to the fact that some singularities will be placed at the boundaries of intervals, and, so, will not be separated. Increasing of wavelet entropy in Table 1 proofs this. 4 Conclusions Authors have proposed to use arbitrary reducible rational fraction as a dilation factor for the rational wavelet transform. It has been shown that perfect reconstruction condi- tion for such values of dilation factor is satisfied. Criterion for selecting the optimal dilation factor from the set of reducible fractions that all are the multipliers of the same irreducible rational number has been introduced. Authors have proposed to use entropy-based criterion. Process of selecting the optimal value for the dilation factor of rational wavelet trans- form is demonstrated on the signal of the spontaneous electromagnetic emission of the Earth. 167 References 1. Hussain, L., Aziz, W.: Time-Frequency Wavelet Based Coherence Analysis of EEG in EC and EO during Resting State. International Journal of Information Engineering and Elec- tronic Business 7(5), 55–61, (2015). 2. Rhif, M., Ben Abbes, A., Farah, I.R., Martinez, B., Sang, Y.: Wavelet Transform Applica- tion for/in Non-Stationary Time-Series Analysis: A Review. Applied Science 9, 1345, (2019). 3. Chertov, O., Malchykov, V.: Rational wavelet transform with reducible dilation factor. In: Selected Papers of the XIX International Scientific and Practical Conference “Information Technologies and Security” (ITS-2019), pp. 146–158. (2020). 4. Baussard, A., Nicolier, F., Truchetet, F.: Rational multiresolution analysis and fast wavelet transform: application to wavelet shrinkage denoising. Signal Processing 84(10), 1735–1747 (2004). 5. Chertov O., Malchykov V.: Perfect Reconstruction Condition for Rational Wavelet Trans- form with Reducible Rational Dilation Factor. In: Shkarlet S., Morozov A., Palagin A. (eds) Mathematical Modeling and Simulation of Systems (MODS'2020). Advances in Intelligent Systems and Computing, vol. 1265, pp. 248-254. (2020). 6. Li, Z.: Orthonormal wavelet bases with rational dilation factor based on MRA. In: 7th Inter- national Congress on Image and Signal Processing, pp. 1146-1150. IEEE, China (2014). 7. Martin, N.F.: Mathematical Theory of Entropy. Addison Wesley (1981). 8. Coifman R. R., Wickerhauser M.V.: Entropy-based algorithms for best basis selection. IEEE Trans. Inform. Theory. 38 (2), 713–719 (1992). 9. Chertov O., Malchykov V.: Determining optimal dilation factor of non-dyadic wavelet transform. In: Proceedings of IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON-2017), pp. 297–300 (2017).