# Describing a filter in a wavelet basis

Started by 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?

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?
>
>                           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