I am trying to understand the equivalence of convolution through polynomial (coefficient) multiplication, Fast Fourier Transforms, and matrix multiplication. I am using octave with the octave-signal package, and part of this question may possibly related to their implementation (which I believe would be the same for MATLAB).
So I create my original signal with length $N$, and my boxcar window length is $n$.
N = 48;
n = 6;
I use $\sin$ as the input function for this example.
dt = 2*pi/N;
t = [-N/2:N/2-1]'*dt;
f = sin(t);
Convolution by polynomial multiplication ($g = h \star f$):
h = ones(n,1);
g_conv = conv(h,f);
g_conv_same = conv(f,h,'same');
Convolution by FFT and FFT with zero-padding of the input (also $g = h \star f$):
g_ft = real(ifft(fft(h,N).*fft(f)));
f_padded = [f; zeros(n-1,1)]; % append zeros
g_ft_padded = real(ifft(fft(h,N+n-1).*fft(f_padded)));
Convolution by matrix multiplication ($\mathbf{g} = \mathbf{A} \mathbf{f}$):
A = convmtx(h,N);
g_mtx = A*f;
$\mathbf{A}$ looks like this:
Find indices to trim arrays:
idx_A = find(sum(A,2) == n);
idx_t = 1:length(idx_A);
Plot results (the signals convolved by different methods):
plot(t(idx_t),g_mtx(idx_A),'k','linewidth',3);
line(t-5*dt,g_ft,'color','g','linewidth',2); %-> offset by 5*dt
line(t-7*dt,g_ft_padded(1:length(t)),'color','r','linestyle','--'); %-> offset by 7*dt
line(t(idx_t),g_conv(idx_A),'color','b','marker','o');
line(t-2*dt,g_conv_same,'color','b','marker','+'); %-> offset by 2*dt
legend({'matrix','FFT','FFT (padded)','conv','conv (same shape)'},...
'location','southeast')
xlabel('x value')
ylabel('y value')
which looks like this:
I have several questions at this point:
- Why are the results for the FFT methods offset by several units of
dt
? - If I pad the FFT results such that the input vector is no longer periodic (red dotted line), why do I miss part of the convolved function (on the right side) in the result?
- How do I treat the ends for the FFT convolution so that the results are aligned with the polynomial and matrix multiplication results?
Thanks in advance. P.S. if there is a good textbook reference for these details I would appreciate your guidance.
(I have edited for clarification.)