1
$\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$
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$
  • $\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$ – Luke Hutchison Jul 5 '18 at 23:15
  • $\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 '18 at 9:32
1
$\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.

$\endgroup$
0
$\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$
  • $\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$ – Luke Hutchison Jul 5 '18 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 '18 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$ – Luke Hutchison Jul 9 '18 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 '18 at 3:53
  • $\begingroup$ @LukeHutchison If this answers your question,please accept it $\endgroup$ – Fourierist Aug 9 '18 at 5:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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