If you could please offer any advice, this puzzle is driving me mad:
I've come across a problem that is trivial to compute in $\mathcal{O}(m^2)$ operations, but which very closely resembles a convolution that could be performed in $\mathcal{O}(m\log(m))$ (using, for example, FFT). But I just can't seem to get it there.
Consider 3 vectors $N$, $R$, and $D$. The lengths of $N$ and $R$ are both $m$. The length of $D$ is $2m-1$.
Given two vectors $N$ and $D$, the result vector $R$ is defined as: $R_i = \sum_j N_j ~D_{i+j}$. I want to compute the entire vector $R$.
Can you figure out a way to compute the vector $R$ in $m \log(m)$ time?
Notes:
It's apparent that each entry $R_i$ can be computed trivially in $\mathcal{O}(m)$, and thus the entire vector $R$ can be computed in $\mathcal{O}(m^2)$.
I've tried making this into a convolution or DTFT-like formula by applying a shift: $Z\{R\} = \sum_j \sum_i N_j ~D_{i+j} ~z^{-i}$,
where $Z\{R\}$ is the Z-transform of $R$ (i.e. $R_i$ is the coefficient of $z^{-i}$ in $Z\{R\}$).
But I just can't seem to see it... I would be absolutely grateful for any help you can provide.
EDIT: Example
Let $N = [0.05, 0.93, 0.6 , 1. , 0.6 , 0.1]$, and
$D = [ 1. , 0.5 , 0.35, 0.7 , 0.1 , 0.03, 1.2 , 0.6 , 0.3 , 5. , 0.45]$.
I believe the result should be:
$R = [0.4464 , 0.70595, 1.5385 , 0.3472 , 0.60987, 2.8935]$
I computed it using the $m^2$ approach with python:
from numpy import *
def simplePropPosteriors(otherN,D):
L = len(otherN)
result = array([0.0]*L)
for n1 in range(L):
for n2 in range(L):
result[n1] += D[n1+n2]*otherN[n2]
return result
Answer:
Ah, as explained by @littleO:
Let $Q_i = N_{m-i}$; then R is found in the middle elements of the convolution $Q*D$.
Sincerely,
Oliver
Zeropad both $N$ and $D$ out to length $3M-2$. Then
Let $Q_i = N_{m-i}$ (the reverse of $N$).
$R$ is found in the middle of the convolution $Q*D$, which can be found in $m ~log(m)$ via ${DFT}^{-1}(DFT(Q) \cdot DFT(D))$.
Trimming the edges of $Q*D$ gives the correct answer for $R$.