Haar Wavelet Transform Calculation Primer

The DWT calculation is carried out in detail for a signal vector containing 8 data elements. The first step is to compute the averages and differences (divided by two) for each of the signal components. This is shown in Figures 1-4.

Figure 1
Figure 2
Figure 3
Figure 4

The next step involves computing the averages and differences of those averages and differences just computed. This is shown in Figures 5 and 6.

Figure 5
Figure 6

Finally, the last step involved is to compute the average and difference of the previous step. This is shown in Figure 7.

Figure 7

The discrete wavelet transform vector for the signal supplied is given by the bottom row, shown in Figure A-8. The color-coding is included to indicate where each of the computed differences (and the final average) is placed in the vector.

Figure 8

As the number of signal data points increases, so does the number of computations of averages and differences. This process lends itself quite readily to automation.

Haar Wavelet Transform Calculations Using MS Excel

Background on Calculations with the DWT

The discrete wavelet transform provides a system for constructing or approximating a signal or function. Unlike Fourier series, which reflects only the frequency or spectral components of a signal, wavelets provide time and frequency localization of signal specifics, which is necessary to reconstruct time-varying, non-stationary processes [1, 2]. The discrete wavelet transform calculation is conducted with respect to a Haar basis function, in which individual averages and differences (or details, as they are sometimes referred to in the art) are computed with respect to the raw signal data. Let’s begin by considering a small sample signal of raw data collected from a patient, defined by Eq. 1:

Equation 1

The process of computing wavelet coefficients from this vector is straightforward and is as illustrated in Figure 1.

Figure 1

The signal is decomposed into a series of averages and differences, where the average is calculated according to normal convention, and the difference is actually half the difference between any two raw signal values. Thus, from Equations 2 and 3:

Equation 2
Equation 3

The computations illustrated in Figure 1 proceed as follows: the average of each raw sample is computed with respect to its immediate neighbor, together with the difference (divided by 2). Once these are computed, the average and difference of these results are then computed. This process is continued until the complete ensemble (that is, the single value and difference) corresponding to the entire signal is determined. The first wavelet coefficient is given by the ensemble average corresponding to the longest scale value over the entire interval. The next wavelet coefficient corresponds to the size of the difference of the averages at the next scale up. The remaining coefficients follow the pattern of the differences between the averages at finer and finer scale (in general). Thus, the vector of wavelet coefficients given the data sample above appears as follows, represented as Equation 4:

Equation 4

We can represent this relationship between the wavelet coefficients and the raw signal as Equation 5:

Equation 5

Where H4 represents a 4 x 4 Haar matrix having the form:

Equation 6

Alternatively, given the raw signal, the wavelet coefficients may be found directly from Equation 7:

Equation 7

The Haar matrix may be inverted using standard methods. The creation of the Haar matrix follows a predictable pattern as the number of rows and columns increases. However, by applying the Haar transform, the size of the matrix increases according to 2n scale, where n is a positive integer. Thus, in the Haar basis, the quantity of data must conform to this scale as well. We can expand this Haar basis to an H8 basis, illustrated here in Equation 8:

Equation 8

The number of rows and columns contained within a Haar Hn basis follows in accord with 2n. We can consider an example problem now to illustrate the method. Let’s first expand the original signal from four to eight elements. This larger data quantity will help to illustrate some other features of the discrete wavelet transform and why it is being considered for the specific application. The vector for this data set is given by Equation 9:

Equation 9

The vector of wavelet coefficients associated with this signal, found using the H8, is as follows:

Equation 10

Now, one of the benefits of wavelet coefficients is that they establish the relative scale of the differences with respect to the overall signal average. This is important because, in terms of reproducing the signal, the values of these wavelet coefficients establish their relative impact on the overall signal. Thus, compression of the original signal can be achieved (at a loss) by discarding certain of these coefficients based on establishing a sensitivity threshold.

Defining the statistical significance level of this threshold can be done in accord with well-documented practices, especially relative to setting confidence intervals with respect to a known distribution [3, 4, 5]. However, the discarding of coefficients is not the objective of the wavelet transform in medical applications: indeed, removing potentially important information from the raw signal can be detrimental and will provide the clinician with incomplete data on the patient. Instead, wavelet transforms provide the capability to record all of the data and to automatically filter it so that (1) communication of all data elements between the clinical environment and the health enterprise will not be overwhelmed; and, (2) the ability to retrieve any amount of the data, from an ensemble to detailed temporal changes, can be mined at will by clinicians and researchers without requiring that all data be retrieved from the data repository in any one request.

One way to illustrate these concepts is by applying an exclusion threshold on the smallest values of coefficients: the magnitude of the wavelet coefficients provides insight into the level of contribution they make to the character of the overall raw signal. Hence, by omitting certain coefficients it becomes possible to exclude noise, artifact, or other components that are judged to be of minor influence to the overall raw data sample.

Table 1

For instance, consider the table of wavelet coefficients (Table 1). The column on the left is the independent variable (time). Each subsequent set of columns defines the set of Haar-basis wavelet coefficients, and the resulting signal value, beginning with no applied threshold up to a value of 30% threshold. The threshold value is computed by multiplying the threshold percentage by the largest wavelet coefficient. For instance:  a 10% threshold multiplied by -4 yields a threshold (absolute) value of 0.4. In this case, one wavelet coefficient is discarded, given that the requirement for the 10% threshold case is that the absolute value of all coefficients is greater than 0.4.

Figure 2

At the 20% level, the threshold value is 0.8, but no other coefficients exceed this threshold, so still only one coefficient is discarded (i.e., set to zero so that its contribution will be ignored for signal reconstruction). In comparing the reconstructed signals with thresholds of 10% and 20% to the original (no threshold applied signal) one can see that there are differences in the reconstructed signal. These differences have a maximum deviation of 0.25 between the reconstructed and the original signal.

In viewing the 30% threshold columns, three coefficients are discarded. Here, the deviation between the original and reconstructed signals is no larger than 1.25. So, the general impact of discarding wavelet coefficients from the basis results in an approximation to the original signal. Thus, by discarding wavelet coefficients from the basis, the reconstructed signal approximates the original signal. As the discard threshold approaches zero, the difference between the reconstructed and original signals approaches zero. Figure 2 provides a comparative view of these data by displaying all of these signals on one overlay. To the casual observer, there does not appear to be much difference between the lossy and the lossless cases: the signal data points all appear to be close to one another.

Depending on the behavior of the original signal (that is, its shape, repetitiveness, noise content), the degree of loss vis-à-vis discarding of wavelet coefficients may or may not be acceptable to the end-user. However, in the case of a predictable or repetitive signal, the discarding of wavelet coefficients can have a trivial effect on the reconstruction of the original signal. This latter case can be illustrated effectively with the aid of a revised form of the signal data. The data are contained in Table 2, plotted in Figure 3

Table 2

In this revised case, the raw signal data follow a series of three step functions: values of 8 for three time units, 3 for three time units and –4 for three time units. The wavelet coefficients show that three values are zero. Hence, thresholds of 30% on any of these coefficients will not exceed the threshold. In this instance we are seeing another benefit of the discrete wavelet transform: the ability to “automatically” filter out repeated data. Therefore, all of the reconstructed data shown in Figure 3 overlay the raw signal data. The number of coefficients required to reconstruct this signal are three fewer than the total number of data points contained within the raw signal. Hence, the discrete wavelet transform provides a means for representing the original signal with fewer overall data points. This concept plays a role in the application of the discrete wavelet transform technique to patient vitals data.

Figure 3

[1]     C. Sidney Burrus, Ramesh A. Gopinath, Haitao Guo, Introduction to Wavelets and Wavelet Transforms—A Primer; Prentice-Hall, 1998; page 3.

[2]     Tommi Vuorenmaa, “The Discrete Wavelet Transform with Financial Time Series Applications”; Seminar on Learning Systems at the Rolf Nevanlinna Institute; University of Helsinki, April 9th 2003.

[3]     James F. Zolman, Biostatistics: Experimental Design and Statistical Inference; Oxford University Press, 1993; pp 77-99.

[4]     Christopher Torrence, Gilbert P. Compo, “A Practical Guide to Wavelet Analysis,” Bulletin of the American Meteorological Society; Vol. 79, No. 1: 69-71, January 1998.

[5]     Sheldon Ross, A First Course in Probability, 3d Ed.; Macmillan Publishing Company, 1988; pp 336-357.