# 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]            
k

Y(w) = sum y[n] exp(jwn)
n

= sum sum x[k] h[n-k] exp(jwn)                 
n   k

set p = n-k, find n = p+k and substitute:

Y(w) = sum sum x[k] h[p] exp(jw(k+p))               
p   k

= sum sum x[k] h[p] exp(jwn)exp(jwp)           
p   k

= sum h[p] exp(jwp) sum x[k] exp(jwp)          
p                 k

= X(w)H(w)                                     

Equation  is the key why the DTFT is so useful when
computing convolutions, since the numercal work of
computing  often is far less than computing  directly.

But do take a closer look into how we arrived at , and you
will find one utterly essential step:

Transforming from equation  to equation .

Here, one uses the property of the exponential function that

F(a+b) = F(a)F(b).                  

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  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  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]            
>                         k
>
> Y(w) = sum y[n] exp(jwn)
>         n
>
>      = sum sum x[k] h[n-k] exp(jwn)                 
>         n   k
>
> set p = n-k, find n = p+k and substitute:
>
> Y(w) = sum sum x[k] h[p] exp(jw(k+p))               
>         p   k
>
>      = sum sum x[k] h[p] exp(jwn)exp(jwp)           
>         p   k
>
>      = sum h[p] exp(jwp) sum x[k] exp(jwp)          
>         p                 k
>
>      = X(w)H(w)                                     
>
> Equation  is the key why the DTFT is so useful when
> computing convolutions, since the numercal work of
> computing  often is far less than computing  directly.
>
> But do take a closer look into how we arrived at , and you
> will find one utterly essential step:
>
> Transforming from equation  to equation .
>
> Here, one uses the property of the exponential function that
>
>    F(a+b) = F(a)F(b).                  
>
> 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  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  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]            
> >                         k
>
> > Y(w) = sum y[n] exp(jwn)
> >         n
>
> >      = sum sum x[k] h[n-k] exp(jwn)                 
> >         n   k
>
> > set p = n-k, find n = p+k and substitute:
>
> > Y(w) = sum sum x[k] h[p] exp(jw(k+p))               
> >         p   k
>
> >      = sum sum x[k] h[p] exp(jwn)exp(jwp)           
> >         p   k
>
> >      = sum h[p] exp(jwp) sum x[k] exp(jwp)          
> >         p                 k
>
> >      = X(w)H(w)                                     
>
> > Equation  is the key why the DTFT is so useful when
> > computing convolutions, since the numercal work of
> > computing  often is far less than computing  directly.
>
> > But do take a closer look into how we arrived at , and you
> > will find one utterly essential step:
>
> > Transforming from equation  to equation .
>
> > Here, one uses the property of the exponential function that
>
> >    F(a+b) = F(a)F(b).                  
>
> > 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  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  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