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?

PS: I've been learning about this completely on my own, so if I made some mistakes in my explanation or way of thinking about this stuff let me know.

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."