Confusion about convolution theorem in matlab

Convolution theorem in fourier transform states:

Fourier transform of a convolution of two vectors A and B is pointwise product of Fourier transform of each vector. (Ref: https://en.wikipedia.org/wiki/Convolution_theorem)

Now let A=B=[0.7, 0.2, 0.1], pointwise product of A and B can be obtained through the code:

    fft(A).*fft(A)

The result is [1.000000000000000 + 0.000000000000000i, 0.295000000000000 - 0.095262794416288i, 0.295000000000000 + 0.095262794416288i].

Convolution of A and B can be obtained by inverse Fourier transform:

    ifft(fft(A).*fft(A))

The result is C=[0.530000000000000 0.290000000000000 0.180000000000000].

However, convolution of A and B can be calculated in the matlab code:

    conv(A,A)

The result is C'=[0.490000000000000 0.280000000000000 0.180000000000000 0.040000000000000 0.010000000000000].

The result vectors C is not equal to C', contradictory to the convolution theorem. This example shows my confusion on Fourier tranform in matlab code and convolution theorem. Would anyone help me to understand this?

Thanks very much:)

[Arkaprabho Pal]

The convolution theorem says, roughly, that convolving two sequences is the same as multiplying their Fourier transforms. In order to make this precise, it is necessary to pad the two vectors with zeros and ignore roundoff error. Also make sure to use 'full' keyword in conv function.

t = linspace(0,1,200)

x = sin(2*pi*t)

y = exp(-2*t)

X = fft([x zeros(1,length(y)-1)])

Y = fft([y zeros(1,length(x)-1)])

then conv(x,y,'full') = ifft(X.*Y)

Answer 1

[Matt J]

There are differences between the continuous-domain convolution theorem and the discrete one. In particular, the discrete domain theorem says that ifft(fft(A).*fft(B)) gives the circulant convolution of A with B. You can get obtain a linear convolution result from a circulant convolution if you do sufficient zero-padding:

>> ifft(fft(A,5).*fft(A,5),5)

ans =

      0.4900    0.2800    0.1800    0.0400    0.0100

[Felix Wong]

Thanks a lot. I tested for this example, and you suggestion works well for my situation.

I have a further question on the code:

    fft(A,n)

for a general vector A of length L, is there a crietira or reference to set number of n?

[Matt J]

n needs to be large enough to hold the result of the convolution.

[Felix Wong]

I am trying to calculate N times convolution of an input vector A by using FFT method. But since the input vector is a variable, so I would like to know if there is any tricks to control n in 'fft(A,n)'?

Is it possible to set n=2*L or 3*L (L is full length of vector A) as a boundary?

[Image Analyst]

Every time you convolve A with something, it adds a length of A to the something. So A**A is twice as long A**(A**A) is 3 times as long, etc. Don't do the padding yourself or else it will be even longer. Just specify the 'full' option in conv() or conv2() and it will enlarge the array by the correct amount for you.

[Felix Wong]

Thanks @Image Analyst. I have tried that, and using default 'full' option.

I believe it is related to FFT in the synax 'fft(A,n)'. An improperly n will result some misleading result for ifft(fft(A,n).*fft(A,n),n).

Since B=conv(A,A) has a length 2L-1 (given length of A is L), I guess n should be set to no less than 2L-1. I am not sure if it is correct?

Answer 2

[Image Analyst]

Try this:

A = [0.7, 0.2, 0.1]
B = [0.7, 0.2, 0.1]
Cconv = conv(A, B)
% Now if C = A ** B
% Then fftC = fftA * fftB
fftA = fft(A)
fftB = fft(B)
fftC = fftA .* fftB
% If we inverse transform this to get C back:
% ifft(fftC) = C = ifft(fftA .* fftB)
C2 = ifft(fftC)
C3 = ifft(fftA .* fftB)

I think the difference you're seeing in Cconv and C2 or C3 is that CConv is the full convolution - 5 elements - while doing it the fft way, you are clipping to the same size as your input arrays - 3 elements - and so inherently you have a rect function in there multiplying your A and B. And the convolution of a rect is a triangle function, which, because your array is so small, wreaks havoc on your values. With much larger arrays, it won't be as noticeable.

[Felix Wong]

Thank you for the answer.

Actually, I am trying to calculate N times convolution of an input vector A of length L, by using FFT algorithm. The length L is relatively small. I am not sure if your suggestions can work for my situation, since discrete FFT method will truncate vectors.