Prev: Wolfram Alpha - Integrate - bug and glitch - 1996 - 2010 (!)
Next: Unable to interpret TeX string
From: Antony on 22 Jul 2010 09:24
Dear all,

What's the relationship between correlation and convolution? For example, if \otimes denoting convolution operator and * denoting correlation operator, "A * B" can be written into what form of correlation? "B^T \otimes A" is incorrect, I think. But how to convert? Furthermore, how to convert a convolution operation into a correlation operation? What is the transfer rule? Thanks a lot.

In addition, I often see some articles saying convolution can be accelerated by FFT, but I have no idea of such a transformation. Would you mind give me some advice or links on how such a transformation takes?
From: Wayne King on 22 Jul 2010 10:29
"Antony " <mutang.bing(a)gmail.com> wrote in message <i29gpk$1ve$1(a)fred.mathworks.com>...
> Dear all,
>
> What's the relationship between correlation and convolution? For example, if \otimes denoting convolution operator and * denoting correlation operator, "A * B" can be written into what form of correlation? "B^T \otimes A" is incorrect, I think. But how to convert? Furthermore, how to convert a convolution operation into a correlation operation? What is the transfer rule? Thanks a lot.
>
> In addition, I often see some articles saying convolution can be accelerated by FFT, but I have no idea of such a transformation. Would you mind give me some advice or links on how such a transformation takes?

Hi Anthony, Look at the "Definition" of convolution at

http://en.wikipedia.org/wiki/Convolution

Now imagine that you have g(t-\tau)=h*(\tau-t) where the asterisk denotes complex conjugation.

Substituting h*(\tau-t) gives the cross correlation of f with h.
So convolving f with g is the same as cross correlating f with a function that is the time-reverse and complex conjugate of g.

As far as computing convolution through the FFT algorithm, you should read about circular convolution and under what conditions the circular convolution of two sequences is equal to the linear convolution.

For example:

A = 1:5;
B = 2:7;
A1 =[A zeros(1,5)];
B1 = [B zeros(1,4)];
% compare
ifft(fft(A1).*fft(B1))
% with
conv(A,B)

Hope that helps,
Wayne
From: TideMan on 22 Jul 2010 16:19
On Jul 23, 1:24 am, "Antony " <mutang.b...(a)gmail.com> wrote:
> Dear all,
>
>    What's the relationship between correlation and convolution? For example, if \otimes denoting convolution operator and * denoting correlation operator, "A * B" can be written into what form of correlation? "B^T \otimes A" is incorrect, I think. But how to convert? Furthermore, how to convert a convolution operation into a correlation operation? What is the transfer rule? Thanks a lot.
>
>    In addition, I often see some articles saying convolution can be accelerated by FFT, but I have no idea of such a transformation. Would you mind give me some advice or links on how such a transformation takes?  

This is explained very well in an old textbook of mine:
Brigham, E. O. 1974: The Fast Fourier transform. Prentice-Hall.
Most libraries will have it.
From: Antony on 22 Jul 2010 22:30
"Antony " <mutang.bing(a)gmail.com> wrote in message <i29gpk$1ve$1(a)fred.mathworks.com>...
> Dear all,
>
> What's the relationship between correlation and convolution? For example, if \otimes denoting convolution operator and * denoting correlation operator, "A * B" can be written into what form of correlation? "B^T \otimes A" is incorrect, I think. But how to convert? Furthermore, how to convert a convolution operation into a correlation operation? What is the transfer rule? Thanks a lot.
>
> In addition, I often see some articles saying convolution can be accelerated by FFT, but I have no idea of such a transformation. Would you mind give me some advice or links on how such a transformation takes?

Thank you very much, Wayne and TideMan. I understand the relationship between covolution and correlation a little now, *-*. I will follow the links and other advice you provide for more details, and wish that I can completely know the principle finally. Thanks again!

Antony
 | 
Pages: 1
Prev: Wolfram Alpha - Integrate - bug and glitch - 1996 - 2010 (!)
Next: Unable to interpret TeX string