# discrete Haar wavelet transform, fast and efficient method?

I'm working on my own implementation of the discrete Haar wavelet transform, I understand the wavelet theory and how to construct the Haar matrix of size N to perform the transform, but obviously there is a problem using the Haar matrix in application - it's simply too big.

I am working on an application that applies the Haar transform to an audio signal. If I sample the signal at 44.1 kHz, even a one second recording would require a 2^16 by 2^16 Haar matrix to do the transform in one step, which is obviously impractical and a hardware constrained machine such as a phone wouldn't have the capability to hold such a matrix in memory.

The other method I've seen used is that a 2X2 Haar matrix is applied to the entire signal iteratively, and the results are stored in two arrays - one array holding the "average" Haar coefficients (first element of the output vector) and the other holding the "difference" coefficients (second element of the output vector). The process is then repeated over the "average" coefficients - as these coefficients are essentially the result of a lowpass filter. Each time the process is repeated the number of elements needed to process in the following step is halved, until only one lowpass coefficient is left. This seems fine, and definitely works but when I started to think about it, it just seems that it would be really slow.

My main question is, what's a good way to implement a fast and efficient haar transform? Or a practical way to apply one of these two methods?

PSS: I've never done any kind of audio processing before, so if you know about some other filters that I should apply to the raw signal before doing a wavelet transform let me know!

PSSS: I know that the Haar wavelet may not be the best for this type of signal processing, but when I tried to learn about using other DWTs such as the Daubechies wavelets, the literature seemed very confusing, or at least was directed at more advanced readers. If anyone could point me in the direction of how to implement other DWTs, that would be great.

The Haar wavelet is actually a part of the Daubechies wavelet, for the case D=2. There's some example code on wikipedia that shows the Daubachies transform.

The Haar transform is just a low pass filter combined with a high pass filter, with the coefficients being placed in the first and second halves of the signal. Then, this iteratively (or recursively) keep going.

The low pass filter is just the sum of two components while the high pass filter is their difference.

For the Haar wavelet case, you can check out my vectorized code on Github. Here, idwt2 stands for "Inverse Discrete Wavelet Transform 2D."

• Hey Scott, thanks for the reply. I'm guessing that some of the functions you were using, like "cblas_scopy" are part of one of the packages you included in the declarations, correct? Nov 20, 2013 at 2:18
• Correct. They're part of BLAS, which (in my case) is part of Apple's Accelerate framework. If you want without those functions, look at the code's history (around Sept 2013). Nov 20, 2013 at 18:54
• Ok, thanks. I'll just need to do some research about what all that stuff is actually doing. Nov 21, 2013 at 5:35
• It just adds the first two components (a low pass filter) and then subtracts the same components (a high pass filter). There's more info here: cs.ucf.edu/~mali/haar and on the wiki page: en.wikipedia.org/wiki/Haar_wavelet Nov 21, 2013 at 18:33
• Haha, well yes, that's what the haar lowpass and high pass filters do, I guess I was just saying I want to see how exactly how those methods work. Nov 23, 2013 at 4:36