Introduction to Discrete Convolutions¶

Discrete convolution is a fundamental mathematical operation used across many fields, including signal processing, image analysis, and, crucially, probabilistic state estimation like the Bayes Filter. It provides a formal, structured way to combine two sequences of numbers (or functions) to produce a third sequence that represents how the shape of one sequence is modified by the other.

Definition of Discrete Convolution¶

Given two discrete functions (or sequences) $f$ and $g$, their discrete convolution, denoted by $(f * g)$, is defined as:

$$(f * g)[n] = \sum_{k} f[k] \cdot g[n - k]$$

Where:

• $f[k]$ is the value of the first function at index $k$.
• $g[n - k]$ is the value of the second function, which is flipped and shifted by $n$ (the current index of the resulting sequence).
• The sum iterates over all possible indices $k$ where the functions overlap.

Note: The convolution is commutative, i.e. $f * g = g * f$

Connection to Probability¶

In the context of your localization problem, discrete convolution has a specific probabilistic meaning:

• Blending Distributions: Convolution is the mathematical operation that describes the distribution of the sum of two independent random variables.
• Prior + Motion: When predicting a state, you are effectively taking the probability distribution of the previous position ($f_{t}$) and adding the probability distribution of the motion displacement ($g$). The resulting probability distribution ($f_{t+1}$) is the convolution of the two, representing the total combined uncertainty.

Example¶

• $f_{t}$ is the robot location at time $t$
• $g$ is the motion displacement
• $f_{t+1} = f_{t} * g$ is the robot location at time $t+1$

Visualizing the Convolution Process: Flip, Shift, Multiply & Sum¶

This example uses a discrete signal $f$ and a motion kernel $g$.

• Signal $f_{t}$: [0, 0, 0, 1.0, 0, 0] (A single point/robot at index 3)
• Kernel $g$: [0.0, 0.2, 0.8]: stand still probability is 0.2 and moving right with probability 0.8.

Flip

The kernel $g$ is reversed around its center point:

• Original $g$: [0.0, 0.2, 0.8]
• Flipped $g_{rev}$ : [0.8, 0.2, 0.0]

Shift, Multiply and Sum We slide the flipped kernel $g_{rev}$ across signal $f$. The output at index $n$ is the sum of products where they overlap.

At position $n = 2$:

Index:          0    1    2    3    4    5
f_t[k]:           0    0    0   1.0   0    0

                               |
g_rev[2-k]:      [0.8,  0.2,  0.0]
                               |
Calculation:            1.0 * 0.0 = 0.0
Output f_tp1[3]:    0.0

At position $n = 3$:

Index:          0    1    2    3    4    5
f[k]:           0    0    0   1.0   0    0

                               |
g_rev[3-k]:            [0.8,  0.2,  0.0]
                               |
Calculation:            1.0 * 0.2 = 0.2
Output f_tp1[3]:    0.2

At position $n = 4$

Index:          0    1    2    3    4    5
f[k]:           0    0    0   1.0   0    0

                               |
g_rev[4-k]:                  [0.8,  0.2,  0.0]
                               |
Calculation:            1.0 * 0.8 = 0.8
Output f_tp1[4]:    0.8

Example¶

$f$ is a distribution:

Convolution as Blurring or Averaging¶

In practice, the physical meaning of convolution is often one of:

• Blurring: If $f$ is a sharp signal and $g$ is a smoothing kernel, the convolution $(f * g)$ results in a blurred version of $f$.
• Weighted Averaging: Convolution calculates a new output value as a weighted average of the input function $f$, where the weights are provided by the second function $g$.

Applications of Convolution in CNNs¶

• Convolutional Neural Networks (CNNs) used for feature extraction in computer vision: Learned kernels over (camera) images e.g. to automatically detect edges, shapes, and complex objects like pedestrians or traffic signs.