4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Could you please mark my answer? $\endgroup$
    – Royi
    Apr 30, 2021 at 20:07
  • $\begingroup$ @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. $\endgroup$ May 1, 2021 at 23:54
  • $\begingroup$ I thank you for the feedback. I updated my answer. Let me know what you think now. $\endgroup$
    – Royi
    May 2, 2021 at 4:06

3 Answers 3

2
$\begingroup$

It's not about the index, it is about the Filter :-).

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Jul 5, 2018 at 23:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – Matt L.
    Jul 6, 2018 at 9:32
1
$\begingroup$

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))
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ Jul 5, 2018 at 23:11
  • $\begingroup$ 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. $\endgroup$
    – Fourierist
    Jul 8, 2018 at 5:09
  • $\begingroup$ 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. $\endgroup$ Jul 9, 2018 at 9:26
  • $\begingroup$ 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 $\endgroup$
    – Fourierist
    Jul 11, 2018 at 3:53
  • $\begingroup$ @LukeHutchison If this answers your question,please accept it $\endgroup$
    – Fourierist
    Aug 9, 2018 at 5:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.