# Deconvolution Using Complex Division in The Frequency Domain

Consider these two signals:

a = [1 1 0 0 0 0 0 0]
b = [1 0 1 0 0 0 0 0]


their convolution is

c = a * b = [1 1 1 1 0 0 0 0]


I am trying to obtain b by using complex division to divide the discrete Fourier transform of c by the discrete Fourier transform of a. I am aware that in general, there may not be a solution when attempting deconvolution in this way, due to division by zero issues etc. -- however, I want to understand why this doesn't work in this specific case.

The discrete Fourier transforms of all three signals are:

F(a) = [
2                 (0)
1.707 - 0.707 i
1 - i
0.293 - 0.707 i
0                 (N/2)
0.293 + 0.707 i
1 + i
1.707 + 0.707 i
]

F(b) = [
2                 (0)
1 - i
0
1 + i
2                 (N/2)
1 - i
0
1 + i
]

F(c) = [
4                 (0)
1 - 2.414 i
0
1 - 0.414 i
0                 (N/2)
1 + 0.414 i
0
1 + 2.414 i
]


The zero-th entry (marked (0)) is the sum of the number of 1 values in the signal, equal to $\Sigma_{i = 0}^7k_i$ for each kernel $k \, \epsilon \{a, b, c\}$; the value of the $N/2$-th entry (marked (N/2)) is equal to $\Sigma_{i = 0}^7k_i(-1)^i$.

The problem arises when F(c) is divided by F(a) at the $N/2$-th entry: this is 0/0, which is undefined, or is sometimes defined as evaluating to 1. However, the correct result for the complete division $F^{-1}(F(c) / F(b)) = F(a)$ can only be obtained if this instance of 0/0 in the $N/2$-th position evaluates to the value 2, not 1, since the $N/2$-th entry of F(b) is 2. Other than this value at the $N/2$-th position, all entries of F(b) can be recovered correctly by simply dividing entries in F(c) by the corresponding entry in F(a), using complex division.

Why is the N/2-th entry of the Fourier transform problematic in this way? Is there a robust way to derive what the correct result should be for the division of Fourier transforms at the N/2-th position? Or is this simply due to the fact that the value 2 is lost due to multiplication by 0 in the pointwise multiplication $F(a) . F(b)$?

Does this problem affect other components of the Fourier transform? Or is it only possible for this to happen at the N/2th position, which will be real-valued and may be zero?

Are there other gotchas to dividing signals in the Fourier domain in this way, or does this only happen in cases where there are zeroes in the Fourier domain of one of the factors?

– Royi
Apr 30 at 20:07
• @Royi I'm torn on this... I couldn't quite understand what you were explaining. Matt L's comment on his answer makes it all make sense to me: "if there are no zeros in the frequency domain, no information is lost. If certain frequencies are eliminated by the filtering process (which is what convolution is) then without additional information there is no way to reconstruct them without error." I'm tempted to mark mark Matt L.'s answer as accepted. But I'll give you a chance to edit your answer, since it's the highest upvoted anyway, to explain the "nothing left" comment a bit more. May 1 at 23:54
• I thank you for the feedback. I updated my answer. Let me know what you think now.
– Royi
May 2 at 4:06

Think of your coefficients as filters and what would happen to a Sine Signal with frequency of $$\frac{N}{2} {F}_{s}$$ that would be filtered (Convolved) with your samples of signal $$a$$.

You will sum samples with the same absolute value yet one is negative and the other is positive, namely their sum is zero which means nothing will be left from this signal.

In practice we never use complex division for Deconvolution.
The minimum you can do is use some kind of regularization.

## Zeros in Frequency Domain

In the noiseless case, having zero magnitude at some indices means those indices were zero either in the input signal or the filter.
The problem is we can never know hence when we want to recover any of them the data is lost. This is due to convolution being multiplication in frequency domain so at some index $${C}_{k} = {A}_{k} {B}_{k}$$ and if either $${A}_{k}$$ or $${B}_{k}$$ is zero then $${C}_{k}$$ is zero without being able to recover $${A}_{k}$$ or $${B}_{k}$$.

It means, that, potentially if there are no zeros for the data or the filter (At least in their overlapping domain) data can be restored.
In practice, this is very hard problem given noise.

There is nothing special about the DFT value at the index $N/2$, other than that it's real-valued for real-valued sequences (just like the value at index $0$). Any DFT value could be zero, and that would prevent you from performing deconvolution by complex division. In your example, imagine you wanted to compute $a$ from the DFTs of $b$ and $c$. The DFT of $b$ has zeros at indices $2$ and $6$, so you wouldn't be able to recover the corresponding DFT values of $a$. That's all there is to it; if the DFT of a known sequence zeroes out the values you're looking for there is no way to recover them.

• Thanks for this explanation. I have heard the claim that in the general case, convolution results in information loss. Is it correct to assume then that all cases of information loss due to convolution occur as a result of the zeroing out of values in the Fourier elementwise product, due to there being a zero in the Fourier transform of one of the two convolution terms? Jul 5 '18 at 23:15
• @LukeHutchison: Yes, if there are no zeros in the frequency domain, no information is lost. If certain frequencies are eliminated by the filtering process (which is what convolution is) then without additional information there is no way to reconstruct them without error. Jul 6 '18 at 9:32

You are not able to get it because the combination of ifft and fft gives circular convolution,not just convolution. You need to pad both c,a with atleast 2*n-1 zeros. Try this, I am getting it this way.

ifft(fft(c,15)./fft(a,15))

• Not true -- the example I gave already assumes circular convolution. The signals are already padded. If it works in your case, you just happened to get lucky in avoiding the division by zero issue. As another answer indicates, the division by zero issue will not go away in general. It seems to be an information loss issue incurred by convolution. Jul 5 '18 at 23:11
• You can avoid it by padding to odd length. You have padded to even length 8. So make it 5 or 7..., normally 2*n-1 is enough, which in your case is 5. Jul 8 '18 at 5:09
• Fourierist: This is pretty interesting. How or why does this work? Does it always work in the general case, or is it a trial and error thing? In another answer, it was noted that there's nothing special about N/2, so I suspect that means that padding to an odd length is also luck of the draw. Jul 9 '18 at 9:26
• It is not general. It totally depends on the a vector. For this case it is even. For a=[1 -1 0], you get 0 for any length. We can just think of it as that frequency is not present Jul 11 '18 at 3:53