Haar Wavelet Transform

[ColdFury]

I've been playing around with the Haar Wavelet Transform.

In case anybody doesn't know, the Haar transform can be performed in O(N) time rather than the O(N*LogN) time of the FFT.

I was wondering if there was a way to design a convulution that could multiply large numbers like the way it's used in FFT.

Unfortunately I lack the math skill to even begin thinking about such a thing. (I understand how the FFT works, but not why).

Anyone with any experience has any ideas?

(I think there's probably no scheme, since this idea seems so obvious I'd be shocked it hasn't been investigated already.)

[xilman]

Originally Posted by ColdFury

I've been playing around with the Haar Wavelet Transform.

In case anybody doesn't know, the Haar transform can be performed in O(N) time rather than the O(N*LogN) time of the FFT.

I was wondering if there was a way to design a convulution that could multiply large numbers like the way it's used in FFT.

Unfortunately I lack the math skill to even begin thinking about such a thing. (I understand how the FFT works, but not why).

Anyone with any experience has any ideas?

(I think there's probably no scheme, since this idea seems so obvious I'd be shocked it hasn't been investigated already.)

Coincidence! I played around with the Haar transform back in the summer. Quite fun, but I was unable to find any properties useful to me. That's not to say the Haar transform isn't useful, far from it! It's uses are to be found in other fields.

Paul

[dave_dm]

Originally Posted by ColdFury

In case anybody doesn't know, the Haar transform can be performed in O(N) time rather than the O(N*LogN) time of the FFT.

I was wondering if there was a way to design a convulution that could multiply large numbers like the way it's used in FFT.

Unfortunately I lack the math skill to even begin thinking about such a thing. (I understand how the FFT works, but not why).

Approaching the problem from the other end, my attitude is "Intuitively, we can't multiply as fast as O(N), so the Haar transform won't be able to".

So either I have good intuition or I'm a defeatist

Dave

[xilman]

Originally Posted by dave_dm

Approaching the problem from the other end, my attitude is "Intuitively, we can't multiply as fast as O(N), so the Haar transform won't be able to".

So either I have good intuition or I'm a defeatist

Dave

Or both.

It may be that the Haar transform could be used to shave off a little from the operation count used by, for example, FFT's without thereby producing a O(N) algorithm. This is pure conjecture and I've no justification for the claim whatsoever.

I'm not sure what has been proved about the minimum possible number of operations needed to multiply N-bit numbers on conventional machines. It has been shown that a systolic array with O(N) very simple processors can multiply N-bit numbers in O(N) clock cycles. I can't see that this helps enormously...

Paul

[ET_]

I'm interested in the wavelet subject.

I searched for some texts about it, both introductory and formally correct from a mathematical point of view, but I only found this one:

Fractal Functions, Fractal Surfaces, Wavelets
P.R.Massopust - AP Professional

Is it good/complete ? Form the title I deduce it is not...

Could you point me to better links?

Thanks in advance.

Luigi