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

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.

Answer 1

[Abderrahim. B]

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

[Palguna Gopireddy]

@Abderrahim BELISSAOUI, I am unable to understand how you have taken the output sizes m,n values.

I read about discrete convolution. The sizes of the matrices are either (size(x)+size(y)-1), or max(size(x), size(y)) in different sites.

In Gonzalex book 4th chapter it is told that lenear convolution = circular convolution with zero-padding with 1 less than twice the size of the original matrices.

Can you please tell me how you have got m,n values

you proved

(convolution between x,y) = IDFT(DFT(x),DFT(y)) by taking m,n values

Actually I am trying to acheive

x.*y=IDFT(convolution between DFT(x),DFT(y))

I am unable to acheive it.

[Abderrahim. B]

Hi!

sizes of the matrices are either (size(x)+size(y)-1), or max(size(x), size(y)) in different sites.

> Length is the largest dimension of an array. If the size of a given matrix is (20,10) then the length is 20.

The convolution based DFT is called circular convolution, however conv and conv2 calculate respectively the linear 1D and 2D convolutions. To get the equivalence between them, you need to zero pad your vectors or matrices. Please refer to this link to learn more.

x = randi(10, 20, 10);
xSize = size(x)

xSize = 1×2

20 10

y = randi(20,10,10); 
ySize = size(y)

ySize = 1×2

10 10

m = length(x)+length(y)-1

m = 29

n = max(length(x) , length(y)) - 1

n = 19

% Circular Convolution
circulaConv2 = ifft2(fft2(x,m, n).*fft2(y,m, n)) ;
size(circulaConv2)

ans = 1×2

29 19

%  Compute the full linear convolution of x and y. 
linearConv2 = conv2(x,y) ;
size(linearConv2)

ans = 1×2

29 19

% Compare
isequal(round(circulaConv2), round(linearConv2))

ans = logical
   1

Hope you find this reply helpful.

[Palguna Gopireddy]

@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]

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]

Thank you very much @Paul and @Abderrahim BELISSAOUI.

It works for 2D also.