Suppose I want to generate a vector y which when circularly convoluted with a vector h gives me a vector x. I can find such a vector through the division of FFT as below:

y = ifft(fft(x)./fft(h))           // (1)                  

For example:

x = [2,4,8];
h = [1,0.5,0];

then y comes out to be:

y =  [-0.8889, 4.4444, 5.7778]

I can take this y and compute x either through cyclic convolution or FFT method and both methods give me x back:

z = ifft(fft(y).*fft(h))           // (2)


z = cconv(y,h,3)                   // (3)

z comes out to be [2,4,8].

My question is that, similar to how (3) implements (2) as a linear operation (cyclic conv), is there a linear method which can implement (1) without using FFT. I would think such a method would be called cyclic deconvolution, but I can not understand how to do it.

I understand how to implement linear/cyclic convolution and linear deconvolution - but not cyclic convolution.

  • $\begingroup$ Is this question about the software Wolfram Mathematica? $\endgroup$
    – Marius Ladegård Meyer
    Jul 31 '18 at 7:46
  • 2
    $\begingroup$ Here is a method which claims to do circular convolution without using FFT. But why do you not want to use FFT? Here is link to some code which does in using Mathematica Fourier $\endgroup$
    – Nasser
    Jul 31 '18 at 7:55

Since convolution can be written as a matrix-vector product $Ax=b$ of a circulant or Toeplitz matrix $A$ acting on a vector $x$, you can invert or pseudoinvert via SVD $A$ to obtain $x=A^{-1}b$. That said, FFT deconvolution will always be dramatically faster than this approach and should be preferred unless the kernel function ($h$ in your example above) has zeros or near-zeros in its spectrum to avoid dividing by zero. Even then, there may be methods for dealing with this particular case that I am unaware of.


Your Answer

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