Computational complexity of $n$-fold convolution of a vector versus a function

computational complexityconvolutionfourier analysisfourier transform

Suppose that we have $n$ different real valued vectors $v_1,v_2,…,v_n$, each having $N$ elements, namely $v_k\in\mathbb{R}^N$ for all $k$, and we would like to calculate the convolution of these vectors with each other as follows:

$$v^{*n}=v_1*v_2*\cdots *v_n$$

There are two possible cases:

$1.$ $v=v_k$ for all $k$

$2.$ $v_k$ are random vectors and and each vector is different

I am wondering about the computational complexity required for these cases.

I know that both can be done with $N\log N$ complexity employing fast Fourier trasnform (FFT). But is there a faster algorithm which can solve $1.$, faster than the best solver for $2.$?

It is all about the continuous analogy of the same problem. For $1.$ one can just take the Fourier transform and do $(\cdot)^n$ and take the inverse Fourier transform. It seems to me that $2.$ will require much efforts to solve than $1.$ for the continous case.

Intuitively, one can expect a similar story for the discrete case. Is it so? If yes how?

Best Answer

The output of the $n$-fold convolution has $nN-n+1$ samples, so you meed to dp Fourier transforms of this size. These Fourier transforms have complexity $nN\log nN$.

  • In the first case, you take the FFT of $v$, raise each sample to the $n$-th power, and take the IFFT. As raising $nN-n+1$ samples to the $n$-th power has $\mathcal{O}(nN)$ complexity, the total complexity is

$$\mathcal{O}(nN\log nN)$$

  • In the second case, you need to take the FFT of all $n$ vectors ($\mathcal{O}(n^2N\log nN)$), multiply them together ($\mathcal{O}\left(n^2N\right)$), and take one IFFT ($\mathcal{O}(nN\log nN)$). This gives

$$\mathcal{O}(n^2N\log nN).$$

So, even in big-$\mathcal{O}$ sense, the second case requires many more operations than the first one.

Related Question