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$.
$$\mathcal{O}(nN\log nN)$$
$$\mathcal{O}(n^2N\log nN).$$
So, even in big-$\mathcal{O}$ sense, the second case requires many more operations than the first one.