0
$\begingroup$

I'm reading Knuth/Graham/Patashnik's: Concrete Mathematics.

enter image description here

  • In here, it's not clear to me what is the convolution, is it the act of writing as this?

enter image description here

  • Is this convolution somehow related to this? I tried to read it but I couldn't go far.
$\endgroup$
  • 1
    $\begingroup$ "The sequence $\langle c_n\rangle$ defined by $(5.54)$ is called the convolution..." $\endgroup$ – Pedro Tamaroff Dec 25 '14 at 22:13
  • $\begingroup$ @PedroTamaroff It was confusing because he gave a new name to something I was used to, the product of two series or polynomials. In the same reading, I also discovered this way of writing the product: $$a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+\ldots$$ Which would help me a lot on evaluate the coefficient. I got confused because as that first thing had a name, perhaps he was wanting to call this way to write of convolution. $\endgroup$ – Billy Rubina Dec 25 '14 at 22:33
2
$\begingroup$

There are several related notions of convolution in mathematics. This one is the convolution of two sequences. Suppose that

$$A=\langle a_n:n\in\Bbb N\rangle=\langle a_0,a_1,a_2,\ldots\rangle$$

and

$$B=\langle b_n:n\in\Bbb N\rangle=\langle b_0,b_1,b_2,\ldots\rangle$$

are two sequences of real or complex numbers. The convolution of $A$ and $B$ is a new sequence

$$C=\langle c_n:n\in\Bbb N\rangle=\langle c_0,c_1,c_2,\ldots\rangle$$

defined as follows:

$$c_n=\sum_{k=0}^na_kb_{n-k}\;.$$

Thus,

$$C=\langle a_0b_0,a_0b_1+a_1b_0,a_0b_2+a_1b_1+a_2b_0,\ldots\rangle\;.$$

If we use $*$ to represent the operation of convolution, we have $C=A\mathop{*}B$.

Each of these sequences has an associated power series:

$$\begin{align*} g_A(x)&=\sum_{n\ge 0}a_nx^n\tag{1}\\ g_B(x)&=\sum_{n\ge 0}b_nx^n\tag{2}\\ \end{align*}$$

The point of that passage in Concrete Mathematics is that if you multiply the summations $(1)$ and $(2)$ as if they were ordinary polynomials, you get the power series associated with $A\mathop{*}B$:

$$\begin{align*} \left(\sum_{n\ge 0}a_nx^n\right)\left(\sum_{n\ge 0}b_nx^n\right)&=(a_0+a_1x+a_2x^2+\ldots)(b_0+b_1x+b_2x^2+\ldots)\\\\ &=a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+\ldots\\\\ &=\sum_{n\ge 0}\left(\sum_{k=0}^na_kb_{n-k}\right)x^n\;. \end{align*}$$

The most relevant Wikipedia link is probably this one, for the Cauchy product of series.

$\endgroup$
  • $\begingroup$ It was confusing because he gave a new name to something I was used to, the product of two series or polynomials. In the same reading, I also discovered this way of writing the product: $$a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+\ldots$$ Which would help me a lot on evaluate the coefficients. I got confused because as that first thing had a name, perhaps he was wanting to call this way to write of convolution. $\endgroup$ – Billy Rubina Dec 25 '14 at 22:31
  • 2
    $\begingroup$ @Vÿska: The convolution is related to the product of the series, but it’s not the same thing. Here convolution refers to a binary operation on sequences (and to the sequence that is the result of that operation). One can talk about the convolution of two sequences without making any reference to series or polynomials at all. $\endgroup$ – Brian M. Scott Dec 25 '14 at 22:33
  • $\begingroup$ Sorry for the stupid question, but could you give one example of speaking about convolution without mentioning series of polynomials? $\endgroup$ – Billy Rubina Dec 26 '14 at 19:57
  • 1
    $\begingroup$ @Vÿska: ‘The convolution of the constant sequence $\langle 1,1,1,\ldots\rangle$ with a sequence $\langle a_n:n\in\Bbb N\rangle$ is the sequence $$\left\langle\sum_{k=0}^na_k:n\in\Bbb N\right\rangle\;.’$$ $\endgroup$ – Brian M. Scott Dec 26 '14 at 23:20
1
$\begingroup$

Given two sequences $(a_n)$ and $(b_n)$, we can form their convolution which is a new sequence $(c_n)$ given by $$c_n = \sum_{k=0}^na_kb_{n-k}.$$ This definition is such that the following formal manipulation of power series holds:

$$\left(\sum_{n=0}^{\infty}a_nz^n\right)\left(\sum_{n=0}^{\infty}b_nz^n\right) = \sum_{n=0}^{\infty}c_nz^n.$$

The main concern in the linked article is the convolution of functions. The convolution that you're considering here is often referred to as discrete convolution as the very same article mentions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.