Forums

Describing a filter in a wavelet basis

Started by Palle Uldenborg May 23, 2007
Suppose that I have used the same orthogonal (Dauberchies) wavelet
basis to describe a filter I(t) and a set of signales x1(t), x2(t),
x3(t). Now I want to calculate the convolutions (I*x1)(t), (I*x2)(t),
(I*x3)(t).. and express them in the same wavelet basis as the signals
and the filter.

Is there a smart way to do this within the wavelet formalism?
Is it better to do inverse wavelet transform, FFT, and then wavelet
transform the result?
Where should I look to find algorithms?

                  Thanks in advance
                          Palle

On 23 May, 09:23, Palle Uldenborg <palle.uldenb...@gmail.com> wrote:
> Suppose that I have used the same orthogonal (Dauberchies) wavelet > basis to describe a filter I(t) and a set of signales x1(t), x2(t), > x3(t). Now I want to calculate the convolutions (I*x1)(t), (I*x2)(t), > (I*x3)(t).. and express them in the same wavelet basis as the signals > and the filter. > > Is there a smart way to do this within the wavelet formalism?
Before discussing wavelets, let's see how time-domain convolution and the DTFT are related (view with fixed-width font): [All sums from -infinite to infinite. sum means "sum over k"] k y[n] = x[n] (x) h[n] = sum x[k] h[n - k] [1] k Y(w) = sum y[n] exp(jwn) n = sum sum x[k] h[n-k] exp(jwn) [2] n k set p = n-k, find n = p+k and substitute: Y(w) = sum sum x[k] h[p] exp(jw(k+p)) [3] p k = sum sum x[k] h[p] exp(jwn)exp(jwp) [4] p k = sum h[p] exp(jwp) sum x[k] exp(jwp) [5] p k = X(w)H(w) [6] Equation [6] is the key why the DTFT is so useful when computing convolutions, since the numercal work of computing [6] often is far less than computing [1] directly. But do take a closer look into how we arrived at [6], and you will find one utterly essential step: Transforming from equation [3] to equation [4]. Here, one uses the property of the exponential function that F(a+b) = F(a)F(b). [7] I don't know of any other function than the exponential function that has this property. Not that this is the reason why one can set up equation [5] without any (p,k) cross terms, which in turn is essential for the whole result.
> Is it better to do inverse wavelet transform, FFT, and then wavelet > transform the result?
If the reason is to save FLOPs, then yes. Unless your wavelet function satisfies [7] above. Rune
On May 23, 2:13 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 23 May, 09:23, Palle Uldenborg <palle.uldenb...@gmail.com> wrote: > > > Suppose that I have used the same orthogonal (Dauberchies) wavelet > > basis to describe a filter I(t) and a set of signales x1(t), x2(t), > > x3(t). Now I want to calculate the convolutions (I*x1)(t), (I*x2)(t), > > (I*x3)(t).. and express them in the same wavelet basis as the signals > > and the filter. > > > Is there a smart way to do this within the wavelet formalism? > > Before discussing wavelets, let's see how time-domain > convolution and the DTFT are related (view with fixed-width > font): > > [All sums from -infinite to infinite. sum means "sum over k"] > k > > y[n] = x[n] (x) h[n] = sum x[k] h[n - k] [1] > k > > Y(w) = sum y[n] exp(jwn) > n > > = sum sum x[k] h[n-k] exp(jwn) [2] > n k > > set p = n-k, find n = p+k and substitute: > > Y(w) = sum sum x[k] h[p] exp(jw(k+p)) [3] > p k > > = sum sum x[k] h[p] exp(jwn)exp(jwp) [4] > p k > > = sum h[p] exp(jwp) sum x[k] exp(jwp) [5] > p k > > = X(w)H(w) [6] > > Equation [6] is the key why the DTFT is so useful when > computing convolutions, since the numercal work of > computing [6] often is far less than computing [1] directly. > > But do take a closer look into how we arrived at [6], and you > will find one utterly essential step: > > Transforming from equation [3] to equation [4]. > > Here, one uses the property of the exponential function that > > F(a+b) = F(a)F(b). [7] > > I don't know of any other function than the exponential > function that has this property. Not that this is the > reason why one can set up equation [5] without any (p,k) > cross terms, which in turn is essential for the whole result. > > > Is it better to do inverse wavelet transform, FFT, and then wavelet > > transform the result? > > If the reason is to save FLOPs, then yes. Unless your > wavelet function satisfies [7] above. > > Rune
Rune, This is a property of any constant or variable raised to a power. x^(a +b) = x^a * x^b. Is this what you are calling the exponetial function, or are you strictly refering to the constant epsilon? Maurice Givens
On May 23, 2:23 am, Palle Uldenborg <palle.uldenb...@gmail.com> wrote:
> Suppose that I have used the same orthogonal (Dauberchies) wavelet > basis to describe a filter I(t) and a set of signales x1(t), x2(t), > x3(t). Now I want to calculate the convolutions (I*x1)(t), (I*x2)(t), > (I*x3)(t).. and express them in the same wavelet basis as the signals > and the filter. > > Is there a smart way to do this within the wavelet formalism? > Is it better to do inverse wavelet transform, FFT, and then wavelet > transform the result? > Where should I look to find algorithms? > > Thanks in advance > Palle
Why are you taking the convolution of the wavelet basis and the signal? Are you trying to establish a relationship between the convolution of signals and their wavelet transformation? Maurice Givens
On 24 May, 22:01, maury <maury...@core.com> wrote:
> On May 23, 2:13 pm, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > > > > On 23 May, 09:23, Palle Uldenborg <palle.uldenb...@gmail.com> wrote: > > > > Suppose that I have used the same orthogonal (Dauberchies) wavelet > > > basis to describe a filter I(t) and a set of signales x1(t), x2(t), > > > x3(t). Now I want to calculate the convolutions (I*x1)(t), (I*x2)(t), > > > (I*x3)(t).. and express them in the same wavelet basis as the signals > > > and the filter. > > > > Is there a smart way to do this within the wavelet formalism? > > > Before discussing wavelets, let's see how time-domain > > convolution and the DTFT are related (view with fixed-width > > font): > > > [All sums from -infinite to infinite. sum means "sum over k"] > > k > > > y[n] = x[n] (x) h[n] = sum x[k] h[n - k] [1] > > k > > > Y(w) = sum y[n] exp(jwn) > > n > > > = sum sum x[k] h[n-k] exp(jwn) [2] > > n k > > > set p = n-k, find n = p+k and substitute: > > > Y(w) = sum sum x[k] h[p] exp(jw(k+p)) [3] > > p k > > > = sum sum x[k] h[p] exp(jwn)exp(jwp) [4] > > p k > > > = sum h[p] exp(jwp) sum x[k] exp(jwp) [5] > > p k > > > = X(w)H(w) [6] > > > Equation [6] is the key why the DTFT is so useful when > > computing convolutions, since the numercal work of > > computing [6] often is far less than computing [1] directly. > > > But do take a closer look into how we arrived at [6], and you > > will find one utterly essential step: > > > Transforming from equation [3] to equation [4]. > > > Here, one uses the property of the exponential function that > > > F(a+b) = F(a)F(b). [7] > > > I don't know of any other function than the exponential > > function that has this property. Not that this is the > > reason why one can set up equation [5] without any (p,k) > > cross terms, which in turn is essential for the whole result. > > > > Is it better to do inverse wavelet transform, FFT, and then wavelet > > > transform the result? > > > If the reason is to save FLOPs, then yes. Unless your > > wavelet function satisfies [7] above. > > > Rune > > Rune, > This is a property of any constant or variable raised to a power. x^(a > +b) = x^a * x^b. Is this what you are calling the exponetial > function, or are you strictly refering to the constant epsilon?
Good point. It's been a couple of days since I wrote that post, so I don't remember the exact details, but I am almost sure I thought about a and b as arguments/variables in the function, not constants. With that in mind, I should have said f(x+y)=f(x)f(y) which permits the generalization of f to the form f(x)=a^x. Rune
On May 24, 10:05 pm, maury <maury...@core.com> wrote:
> Why are you taking the convolution of the wavelet basis and the > signal? Are you trying to establish a relationship between the > convolution of signals and their wavelet transformation?
Thank you both for the replies Actually my final goal is to toy with using 2 or 3 dimensional wavelets to describe multivariate probability theory distributions for some physics problem, but right now I am just trying to find out what is up and down wavelet analysis. I looked at some books and I was confused that they didn't include a convolution algorithm. I seem to remember someone using a 3-dimensional array a[l,m,n] so that y[l] = \sum_{m,n} a[l,m,n] * x[m] * h[n] Here y[l], x[m], and h[n] denote coefficients of the wavelet transformed versions of the signals, whereas \sum_{m,n} means that I sum over indexes m and n. I guess that the array a[l,m,n] can be calculated by brute force. I was hoping that a[l,m,n] would have some properties that could lead to a faster method, but I understand from your replies that this is not the case. If someone has a reference to a book or article that goes through the math, then I would still like to read it for personal enlightenment. Palle