Tuesday, 20 August 2013

Is there a way to do this with fast convolution?

Is there a way to do this with fast convolution?

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

No comments:

Post a Comment