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$
The Convolution Process: Fading and Summing¶
Conceptually, convolution can be understood as a "blending" or "smearing" operation.
The calculation of the output at any point $n$ involves three main steps:
- Flip: One of the input functions (conventionally $g$) is conceptually reversed or "flipped."
- Shift: The flipped function $g$ is shifted to the position $n$.
- Multiply and Sum: At that position, the overlapping elements of $f$ and the shifted $g$ are multiplied point-by-point, and the products are summed to get the value of the output $(f * g)[n]$.
As the flipped function $g$ slides across $f$, the output sequence $(f * g)$ is generated.
Convolution as Blurring or Averaging¶
In practice, the physical meaning of convolution is often one of:
- Blurring: If $f$ is a sharp signal (like an image) 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$.
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-1}$) and adding the probability distribution of the motion displacement ($g$). The resulting probability distribution ($f_t$) is the convolution of the two, representing the total combined uncertainty.