Centering of 1D truncated vector convolution?

Question

I am working with a truncated vector convolution and I want to clarify my understanding of the results I am getting. Sorry that the question is kind of long, I hope it's clear what I'm asking.

I am using the operator $\otimes$ to indicate the truncated convolution. I am providing two $N$-length vectors $a$ and $b$, and I am computing the resulting $N$-length truncated convolution vector $c$ in this way:

$$ \begin{aligned} c = a \otimes b \text{ , } c_i = \sum_{j=0}^{N-1} a_{j}b_{i-j} \end{aligned} $$

where negative indices wrap around. For example, if

$$ \begin{aligned} a(x) &= 1x^2+3x+1\\ b(x) &= 2x^2+1x-4 \end{aligned} $$

then

$$ \begin{aligned} a(x) \otimes b(x) &= \begin{bmatrix} a_0 & a_1 & a_2 \end{bmatrix} \begin{bmatrix} b_0 & b_1 & b_2\\ b_2 & b_0 & b_1\\ b_1 & b_2 & b_0 \end{bmatrix} = \begin{bmatrix} 1 & 3 & 1 \end{bmatrix} \begin{bmatrix} -4 & 1 & 2\\ 2 & -4 & 1\\ 1 & 2 & -4 \end{bmatrix}\\ &= \begin{bmatrix} 3 & -9 & 1 \end{bmatrix} \end{aligned} $$

I wanted to verify this algorithm by comparing results to an existing convolution function. I used SciPy's 1D convolution function from scipy.ndimage.convolve, which provides a mode='wrap' parameter to produce the cyclic convolution:

from scipy.ndimage import convolve

a = [1, 3, 1]
b = [-4, 1, 2]

c = convolve(a, b, mode='wrap')

print(f"c = {c}")

which yields the output

$ c = array([-9, 1, 3])

It seems that the elements of the resulting vector are numerically consistent from one function to the other, but they're off-center, i.e. the elements of the vector from SciPy are shifted one position to the left.

What is going on here? What is the reason for the shift? Is my function incorrect? Are these results mathematically equivalent?

Any advice or information is greatly appreciated! Thank you very much.

Answer 1

I believe I have figured out the reason for the discrepancy. It has to do with the "origin" of the convolution. In the case of the SciPy algorithm, the vectors being convolved start oriented one on top of the other, whereas in the case of my own algorithm, the vectors are being treated as starting oriented end-to-end. (see picture below). This causes the resulting vectors to be misaligned.

SciPy's convolution function has an origin parameter which allows me to shift the origin of the convolution to where my own algorithm is starting. Changing this parameter fixed the problem.