Can't prove the convolution theorem of Fourier theorem for two dimensional matrices.

Question

Palguna Gopireddy 2022-7-27

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1768915-can-t-prove-the-convolution-theorem-of-fourier-theorem-for-two-dimensional-matrices

评论： Palguna Gopireddy 2022-8-1

I multiplied two 2D matrices.A, B

A=[1 2;1 1];
B=[1 2;2 1];
C=A.*B;

I convolved their respective DFTs of 512*512 samples each by using the code given in https://in.mathworks.com/matlabcentral/answers/1665734-how-to-perform-2-dimensional-circular-convolution?s_tid=srchtitle

A_fft2=fft2(A,512,512);
B_fft2=fft2(B,512,512);
C_fft2_cconv2=circular_conv(A_fft2, B_fft2);

I found the IDFT of C_fft2; and applied DFT on C

C_ifft2=ifft2(C_fft2);
C_fft2=fft2(C,512,512);

Acoording to fourier theorem

C_ifft2(1:2,1:2) should be equal to C;

C_fft2 should be equal to C_fft2_cconv2.

But neither are them are same in the results.

Could someone tell how to get it.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Abderrahim. B 2022-7-27

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1768915-can-t-prove-the-convolution-theorem-of-fourier-theorem-for-two-dimensional-matrices#answer_1016160

在 MATLAB Online 中打开

Hi!

Please read about discrete convolution ....

Perhaps this:

Conv, fft and ifft

x = randi(10, 20, 1);
y = randi(20,20,1);
n = length(x)+length(y)-1;
xConvFFt = ifft(fft(x,n).*fft(y,n)) ;
xConv = conv(x,y) ;
% compare
isequal(round(conv(x,y), 4), round(xConv, 4))
ans = logical
   1

Conv2, fft2 and ifft2

x = randi(10, 20, 10);
y = randi(20,20,10);
m = length(x)+length(y)-1;
n = length(x) - 1;
xConvFFt2 = ifft2(fft2(x,m, n).*fft2(y,m, n)) ;
xConv2 = conv2(x,y) ;
% compare
isequal(round(xConvFFt2), round(xConv2))
ans = logical
   1

HTH

5 个评论
显示 3更早的评论隐藏 3更早的评论

Palguna Gopireddy 2022-7-29

编辑：Palguna Gopireddy 2022-7-30

在 MATLAB Online 中打开

@Abderrahim BELISSAOUI.

I understood that you have taken the values of row and column widths as 1 less than sum of the respective matrices length.The value of n you have taken as

n = max(length(x) , length(y)) - 1 %(20-1=19)

Is actually

n= colum width of x+colum width of y-1=10+10-1=19.

In the your example case (20*10,20*10), row length is twice column length.

In other dimension cases

n = max(length(x) , length(y)) - 1 %doesn't work

you proved Lenear convolution equal to circular convolution is proved.

lenear convolution = inverseFT(multiplication between FT(xpad),FT(ypad));

I tried proving the time multiplication property(also called frequency convolution property) of fourier theorem.

I tried proving the convolution property

I am able to prove the circular convolution property

a2=[1 2 1 3];
b2=[2 3 2 1];
c2_cconv=cconv(a2,b2,4);
c2f_ifft=ifft(fft(a2).*fft(b2));
isequal(c2_cconv,c2f_ifft)
ans = logical
   1

I am able to prove the frequency convolution property also

c2=a2.*b2;
c2f_cconv=(1/4)*cconv(fft(a2),fft(b2),4);
c2f_cconv_ifft=ifft(c2f_cconv);
isequal(c2,c2f_cconv_ifft)
ans = logical
   1

But I have been trying to prove the frequency convolution property of DTFT. See the link Convolution property of DTFT

From our discussion in "How to get IDTFT". We verified that

fft(A,512); % gives the DTFT of A for 512 points.

Using this I tried this.

a2=[1 2 1 3];
b2=[2 3 2 1];
c2=a2.*b2;
c2f_cconv_dft=(1/(2*pi))*cconv(fft(a2,512),fft(b2,512),512);
c2f_cconv_idft=ifft(c2f_cconv_dft,512);

but c2f_cconv_idft(1:4) not equal to c2.

Did I do something wrong and what to do?

Paul 2022-7-30

编辑：Paul 2022-7-31

在 MATLAB Online 中打开

When approximating an integral with a sum, the sum needs to be scaled by dtheta.

format short e
a2=[1 2 1 3];
b2=[2 3 2 1];
c2=a2.*b2
c2 = 1×4
     2     6     2     3

For N = 512

N = 512;
dtheta = 2*pi/N;
c2f_cconv_dft=(1/(2*pi))*cconv(fft(a2,N),fft(b2,N),N)*dtheta;

Note that 2*pi cancels, so better to just do

c2f_cconv_dft=cconv(fft(a2,N),fft(b2,N),N)/N;
c2f_cconv_idft=ifft(c2f_cconv_dft,512);

The first four points "match"

c2f_cconv_idft(1:4)
ans = 
   2.0000e+00 - 2.0900e-17i   6.0000e+00 + 1.2001e-16i   2.0000e+00 - 6.4627e-17i   3.0000e+00 - 1.1330e-17i

The rest of the points are "zero"

max(abs(c2f_cconv_idft(5:end)))
ans = 
   3.7831e-16

I think this example is actually demonstrating circular convolution theorem of the DFT or its dual, which should be closely related to the convolution property of the DTFT.

Palguna Gopireddy 2022-8-1

Thank you very much @Paul and @Abderrahim BELISSAOUI.

It works for 2D also.

请先登录，再进行评论。

Can't prove the convolution theorem of Fourier theorem for two dimensional matrices.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

5 个评论
显示 3更早的评论隐藏 3更早的评论

更多回答（0 个）

另请参阅

类别

标签

Community Treasure Hunt

Can't prove the convolution theorem of Fourier theorem for two dimensional matrices.

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

5 个评论 显示 3更早的评论隐藏 3更早的评论

更多回答（0 个）

另请参阅

类别

标签

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

5 个评论
显示 3更早的评论隐藏 3更早的评论