convolution with restriction [Matlab]

Prev: MATLAB FFT and IFFT
Next: How to color specific markers with different color?

From: Gideon on 15 Jun 2010 17:10

I was wondering if there was a *fast* (N log N) way to perform
convolution, with restriction. By this I mean, suppose I want to
compute

\sum_j u(j) v(k - j +1)

restricted to a subset of the j's.

From: ImageAnalyst on 15 Jun 2010 17:20

Never heard of it but from your formula it looks like you can just use
the regular convolution and then just shift over the result by one
element - in essence the k of the convolution output is just your (k
+1) which means the convolution output would be shifted from where you
want it.

From: Matt J on 15 Jun 2010 17:37

From: Matt J on 15 Jun 2010 17:59

Gideon <gideon.simpson(a)gmail.com> wrote in message <37d82d30-20e4-42a4-b528-b51c0c804ca4(a)u7g2000yqm.googlegroups.com>...
> I was wondering if there was a *fast* (N log N) way to perform
> convolution, with restriction. By this I mean, suppose I want to
> compute
>
> \sum_j u(j) v(k - j +1)
>
> restricted to a subset of the j's.
====================

You might also want to take a look at this:

http://www.mathworks.com/matlabcentral/fileexchange/26292-regular-control-point-interpolation-matrix-with-boundary-conditions

It can quickly construct a sparseToeplitz matrix with some of the columns removed. Multiplying with such a matrix is equivalent to a convolution sum with the j corresponding to the missing columns deleted.

Here's an example for which every other j index is removed:

>> u=(1:5)';v=[1 2 3 4 5].';
>> V=interpMatrix(v,3,length(u),2); full(V)

ans =

3 1 0 0 0
4 2 0 0 0
5 3 1 0 0
0 4 2 0 0
0 5 3 1 0
0 0 4 2 0
0 0 5 3 1
0 0 0 4 2
0 0 0 5 3

>> convResult=V*u(:)

convResult =

5
8
14
14
23
20
32
26
35

From: Gideon on 16 Jun 2010 01:05

I was shortsighted in the formula I gave. The computation I really
want to make is:

\sum_{j1,j2} u(j1) v(j2) w(k - j1 - j2)

where now I want to restrict over a certain subset of the j1's and
j2's.

On Jun 15, 5:37 pm, "Matt J " <mattjacREM...(a)THISieee.spam> wrote:
> Gideon <gideon.simp...(a)gmail.com> wrote in message <37d82d30-20e4-42a4-b528-b51c0c804...(a)u7g2000yqm.googlegroups.com>...
> > I was wondering if there was a *fast* (N log N) way to perform
> > convolution, with restriction. By this I mean, suppose I want to
> > compute
>
> > \sum_j u(j) v(k - j +1)
>
> > restricted to a subset of the j's.
>
> ===================
>
> Are you sure you don't mean a subset of the k's?
>
> If you don't want certain j's to contribute to the convolution sum, just set
> u(j)=0 for those j and implement the convolution with the modified signal using FFTs for the usual N log N speed.

| Next | Last
Pages: 1 2 3
Prev: MATLAB FFT and IFFT
Next: How to color specific markers with different color?