Deconvolution Using Complex Division in The Frequency Domain

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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))