There are $K$ vectors and all possible $K-1$-fold convolutions are needed to be determined. How many minimum number of convolutions are necessary?
Here is an example:
Lets assume we have $K=4$. Then we have four vectors $v_1$, $v_2$, $v_3$, $v_4$ and the followings are to be computed:
$1.$ $v_1\star v_2\star v_3$ here we need $2$ convolutions
$2.$ $v_1\star v_2\star v_4$ here we need $1$ convolution because we already have $v_1\star v_2$ from the previous step
$3.$ $v_3\star v_4\star v_1$ here we need $2$ convolutions
$4.$ $v_3\star v_4\star v_2$ here we need $1$ convolution because we already have $v_3\star v_4$ from the previous step.
Altogether one needs $6$ convolutions which is normally $8$, if we do not use the convolutions already done in the previous steps.
If we use the same idea for $K=5$
$1.$ $v_1\star v_2\star v_3\star v_4$ here we need $3$ convolutions
$2.$ $v_1\star v_2\star v_3\star v_5$ here we need $1$ convolution
$3.$ $v_1\star v_2\star v_4\star v_5$ here we need $2$ convolutions
$4.$ $v_5\star v_4\star v_3\star v_1$ here we need $3$ convolutions
$5.$ $v_5\star v_4\star v_3\star v_2$ here we need $1$ convolutions
Altogether one needs $10$ convolutions which is normally $15$, if we do not use the convolutions already done in the previous steps.
For $K=6$ one can reduce $24$ convolutions to $14$ and for $K=7$ instead of $35$ convolutions one only needs to calcule $19$ (added: it is actually $18$ according to my new calculation) convolutions if I am not mistaken.
Here are the questions:
Question $1$: I am wondering for a possible generalization to this. For example if we have $K=1000$ or $K=1000000$? How many minimum number of convolutions are necessary?
I can also find all $K-1$ convolutions by first convolving all $K$ vectors with each other resulting in say vector $v$. Then I go ahead with deconvolving $v$ with $v_1$, then deconvolving $v$ with $v_2$, etc.
In this way, I need to make only $999$ convolutions and $1000$ deconvolutions. However the size of devonvolutions is much bigger than the size of convolutions. For example if the length of $v_1$ is $10$, then all convolutions are between vectors of size $1\times 10$. However, if we use the deconvolution idea, the deconvoltion will be beween a vector of size $10$ and size $9001$ for $K=1000$. Moreover, deconvolution is not always reliable.
Question $2$: which idea is the best to obtain $K-1$-fold convoltions with less number of computations for example if one wants to implement using a computer program?
Here is the figure that I got from my examples above. The y axis is the ratio of the minimum that I found by my hands to the clairvoyent so $K(K-2)$. It is almost linear but it wont be like that forever..
So accroding to my examples, the answer should be $4K-10$, which is surprisingly linear. If true, it is also very interesting because for large $K$, one needs to have a very good strategy to achieve the minimum number of convolutions.. what should be the strategy? how can one prove it, if correct?