Prev: MATLAB FFT and IFFT
Next: How to color specific markers with different color?
From: Bruno Luong on 16 Jun 2010 01:19
Gideon <gideon.simpson(a)gmail.com> wrote in message <e71d4ae2-1bc7-4b4a-ae38-2b4e712fe476(a)i31g2000yqm.googlegroups.com>...
> 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)
>

This is 2D convolution between

uv(j1,j2) := u(j1) v(j2)

and w.

So take a look at conv2.

Bruno
From: Bruno Luong on 16 Jun 2010 01:22
Gideon <gideon.simpson(a)gmail.com> wrote in message <e71d4ae2-1bc7-4b4a-ae38-2b4e712fe476(a)i31g2000yqm.googlegroups.com>...
> 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)
>

Also you can compute the above by calling twice one-dimensional CONV

1. between u and w: uw = u*w (* here designs convolution)
2. between v and uw: x = v*uw.

Bruno
From: Matt J on 16 Jun 2010 06:35
Gideon <gideon.simpson(a)gmail.com> wrote in message <e71d4ae2-1bc7-4b4a-ae38-2b4e712fe476(a)i31g2000yqm.googlegroups.com>...
> 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.
=====================

So you basically want to do 2D separable interpolation.

Similar to what Bruno said, you can also use the interpMatrix tool that I mentioned earlier in conjunction with the KronProd class

http://www.mathworks.com/matlabcentral/fileexchange/25969-efficient-object-oriented-kronecker-product-manipulation

in order to do this for regularly spaced j1 and j2. The interpMatrix link contains an example of this for 2D B-spline interpolation, see Example2D.m at

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


From: Gideon on 16 Jun 2010 13:58
On Jun 16, 6:35 am, "Matt J " <mattjacREM...(a)THISieee.spam> wrote:
> Gideon <gideon.simp...(a)gmail.com> wrote in message <e71d4ae2-1bc7-4b4a-ae38-2b4e712fe...(a)i31g2000yqm.googlegroups.com>...
> > 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.
>
> =====================
>
> So you basically want to do 2D separable interpolation.
>
> Similar to what Bruno said, you can also use the interpMatrix tool that I mentioned earlier in conjunction with the KronProd class
>
> http://www.mathworks.com/matlabcentral/fileexchange/25969-efficient-o...
>
> in order to do this for regularly spaced j1 and j2. The interpMatrix link contains an example of this for 2D B-spline interpolation, see Example2D.m at
>
> http://www.mathworks.com/matlabcentral/fileexchange/26292-regular-con...

This will be an O(N^2) computation, won't it?
From: Matt J on 16 Jun 2010 14:27
Gideon <gideon.simpson(a)gmail.com> wrote in message <d247b78c-aaf4-4f30-8b2d-796d1efa5d3a(a)h13g2000yqm.googlegroups.com>...

> This will be an O(N^2) computation, won't it?
======================

You haven't said how big your subsets for j1,j2 are. If they are log(N), then the computation will be O(N*log(N)).

Also, you haven't said how sparse u and v are. If, for example,

nnz(u)=nnz(v)=3

then the operation can be done in <=9 multiplications and additions, using non-Fourier methods, irrespective of N. This may be a lot less than the N*log(N) complexity of FFTs and would avoid complex-valued arithmetic.

I have never seen an interpolation application where one was forced to use interpolation kernels of length O(N). Your situation would be very rare if this were the case.

Failing all this, however, you can still use Fourier methods just as I described for the 1D case, by first setting u(j1) and v(j2) to zero at the appropriate j1 and j2. You can also cut computation a bit by noting that

fft([a,0,0,0,b,0,0,0,c,0,0,0,d...],N)=
repmat( fft([a,b,c,d,...],N/4) , 1, 4)

The computation of fft([a,b,c,d,...],N/4) is obviously smaller than the original N-point FFT.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: MATLAB FFT and IFFT
Next: How to color specific markers with different color?