Valid Shape FFT Deconvolution
20 views (last 30 days)
Show older comments
Benjamin Hezrony
on 6 Oct 2023
Commented: Benjamin Hezrony
on 18 Oct 2023
Hi MathWorks community,
I am trying to wrap my head around FFT convolution and deconvolution, and the effect of different "shape" (full, valid, and same). I have sample code displaying my problem. I'd like to reconstruct the input, x, in both deconvolutions. I got it for full conv/deconv, but not for valid conv/deconv. I didn't even try it for same conv/deconv yet since I don't even know if it is possible for valid conv/deconv. I hope it is possible. I may be missing some theory!
Thank you for any help,
~BH
0 Comments
Accepted Answer
Paul
on 7 Oct 2023
Hi Benjamin,
Here's an approach for the 'valid' convolution.
Problem parameters:
x = 1:7; nx = numel(x);
h = 1:3; nh = numel(h);
nyf = nx + nh - 1;
nyv = nx - nh + 1;
Define the window function such that conv(x,h,'valid) = w*conv(x,h,'full') with appropriate zero padding as will be shown
d = nh - 1;
w = [zeros(1,d) ones(1,nyv) zeros(1,nyf - nyv - d)];
nw = numel(w);
Verify
yf = conv(x,h)
w.*yf
conv(x,h,'valid')
Now, just like we could compute yf as
yf = ifft(fft(x,nw).*fft(h,nw)) % same results as above
We can compute yv (the zero-padded form of the valid convolution) as
yv = ifft(cconv(fft(w),fft(x,nyf).*fft(h,nyf),nw)/nw) % same as above (*)
Verify the imaginary part is rounding error and get rid of it
max(abs(imag(yv)))
yv = real(yv)
From which conv(x,h,'valid') can be extracted with appropriate indexing.
If we want to recover x starting from fft(yv), it may be possible to invert (*) to get to x. But I couldn't see a way to do that. It seems clear that
fft(yv) = fft(w.*conv(x,h)) = fft(w.*ifft(fft(x,nw).*fft(h,nw)))
but I don't see a way to isolate an expression for fft(x), which could then be ifft'd.
Will be interested to see if anyone comes up with a solution.
0 Comments
More Answers (1)
Bruno Luong
on 7 Oct 2023
Edited: Bruno Luong
on 7 Oct 2023
You just do something that is obviously impossible. By FFT with truncation
X = fft(x,L)
You don't use the n-1 last elements so The (n-1) last elements of X is not used to get y.
There is then no way to get back X from Y and h2/H2
%% Valid conv and deconv:
x = 1:7;
h = 1:3;
m = length(x);
n = length(h);
L = m-n+1
X = fft(x,L);
H = fft(h,L);
Y = X.*H;
y = ifft(Y,L)
% This x3/h will give the same vector in Fourier domain as x/h
x3 = x; x3([6 7]) = 0;
X3 = fft(x3,L);
Y3 = X3.*H;
y3 = ifft(Y3,L)
AFAIK the discrete FFT theorem applies for circular convolution. Only FULL convolution is can be convert to FT by Padding 0s and make pb circular without interfering the head and the tail of the original data.
One cannot do that with 'SAME' and 'VALID' convolution. This is impossible, period.
Another way to conceive that only FULL convolution is invertible (interm of x as unknown) is to write down the convolution matrix (in term of flip(h) as band diagonal). You'll see that the simple analysis is matrix size that only FULL convolution makes sense of possibme inversion.
But SAME and VALID convolution are simply truncations of the FULL convolution (that is how @Paul did in his reply).
See Also
Categories
Find more on Spectral Measurements in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!