# Convolution for non-signal-processing background

I am a civil engineer and am analyzing traffic data recorded by capturing vehicle movements over a highway for a specified time period. The database I am dealing with contains observations at every 0.1 seconds (total about 4 million rows) and has some 'noise' in position (lateral and longitudinal) columns. A research paper suggests to 'smooth' the velocity and acceleration data (derived from position) by using following formula: Someone told me it is a 'convolution'. Since I have no background in electronics/ DSP, I had no idea what convolution is. After studying some online resources I can understand a little about the concept but I need a thorough understanding of this topic from a resource which is targeted towards people who have no background in DSP. Could anyone please guide me to the required resources? I am using R for analysis.

## 2 Answers

I disagree with the assertion in the answer by user7090 that the calculation in question is not a convolution; it is indeed a convolution. Let us consider the case $D=2$. Ignoring $Z$ for now, the five terms in that sum $\displaystyle \sum_{k = i-2}^{i+2} x(t_k)e^{-|i-k|/\Delta}$ on the left in the OP's question are \begin{align} x(t_{i-2})e^{-|i - (i-2))|/\Delta} &= x(t_{i-2})e^{-2/\Delta}\\ x(t_{i-1})e^{-|i - (i-1))|/\Delta} &= x(t_{i-1})e^{-1/\Delta}\\ x(t_{i-0})e^{-|i - (i-0))|/\Delta} &= x(t_i)e^{-0/\Delta} = x(t_i)\\ x(t_{i+1})e^{-|i - (i+1))|/\Delta} &= x(t_{i+1})e^{-1/\Delta}\\ x(t_{i+2})e^{-|i - (i-2))|/\Delta} &= x(t_{i+2})e^{-2/\Delta} \end{align} and so the sum is very much a convolution of the sequence $x$ whose $i$-th term is $x(t_i)$ with a length-$5$ sequence $h$ whose $n$-th term is $e^{-|n|/\Delta}$ for $|n| \leq 2$ in this case (and a length-$(2D+1)$ sequence with $|n| \leq D$ more generally).

What you, the OP, need to understand is the following (and don't get bogged down in words like convolution). You are doing a smoothing of the data that you have collected. Each $x(t_i)$ of the original data is being replaced by a $\tilde{x}(t_i)$ which is formed as a weighted sum of $x(t_i)$ and its immediate neighbors. The weights assigned to $x(t_i)$ is the largest, the weight assigned to its nearest neighbors $x(t_{i+1})$ and $x(t_{i-1})$ are smaller (but equal), the weights assigned to slightly more distant neighbors $x(t_{i+2})$ and $x(t_{i-2})$ is yet smaller, and so on, till the we get to $x(t_{i+D})$ and $x(t_{i-D})$ which get the smallest weights of all. Anything more than $D$ away gets a weight of $0$. The weights in question are normalized in the sense that the total weight is $1$, but let us look at the raw weights which are alleged to be those $e^{-|i-k|/\Delta}$. What you really have (before normalization of the weights) is that sum (let us use $D = 3$ for simplicity) which is

$x(t_i) + \left.\left.e^{-1/\Delta}\right[x(t_{i+1}) + x(t_{i-1)}\right] + \left.\left.e^{-2/\Delta}\right[x(t_{i+2}) + x(t_{i-2})\right] + \left.\left.e^{-3/\Delta}\right[x(t_{i+3}) + x(t_{i-3})\right]$

$= e^{-3/\Delta}x(t_{i-3}) + e^{-2/\Delta}x(t_{i-2}) + e^{-1/\Delta}x(t_{i-1}) + x(t_i) + e^{-1/\Delta}x(t_{i+1}) + e^{-2/\Delta}x(t_{i+2}) + e^{-3/\Delta}x(t_{i+3})\quad (1)$ where on the right side we have the elements occurring in the natural order, flanking the central element $x(t_i)$ on both sides. Now, the sum of the raw weights exhibited in $(1)$ is $$e^{-3/\Delta} + e^{-2/\Delta} + e^{-1/\Delta} + 1 + e^{-1/\Delta} + e^{-2/\Delta} + e^{-3/\Delta} \tag{2}$$ which is just the element $Z$ in the question, and so the normalized weights are just the ones exhibited in $(2)$ divided by $Z$. A better way of writing $Z$ might be $$Z = \sum_{k=-D}^D e^{-|k|/\Delta} = 1 + 2\sum_{k=1}^De^{-k/\Delta} \tag{3}$$ and perhaps a better way of expressing the first sum might be $$\tilde{x}(t_i) = \frac{1}{Z}\sum_{k=-D}^D x(t_{i-k})e^{-|k|/\Delta}$$ which expresses more clearly that we are forming a weighted sum of $x(t_i)$ and its nearest neighbors and that the weights assigned to neighbors at distance $k$ decrease exponentially as a function of $k$ (here $k \geq 0$ of course since we are not distinguishing between the directions of separation).

• Beautiful explanation! Thank you very much. I understand the concept pretty well now. However, I believe that for the implementation of this formula within a program I have to understand the basic parameters of convolution so that I can use the function 'convolve' in R language. Thanks again! – umair Nov 27 '13 at 2:50
• Nice explanation, Dilip! +1 – Peter K. Nov 27 '13 at 15:07

That's not convolution, but its close. Its technically non-causal, so it is actually a complicated beast from an analysis standpoint. Basically what its doing is taking the a single point and creating a weighted average from D points ahead and D points behind a single measurement. The weights are the terms in the second sum. Z is simply the normalization factor. In a normal average you'd divide by the number of elements, in a weighted average you divide by the sum of the weights.

I'm not sure I'd recommend doing that if you've got position data to work with directly already. If I was you, without a background in DSP, I'd look at doing an alpha-beta-gamma filter to start with, and if you want something better, your problem works well with a Kalman filter. These use the basic position/velocity/acceleration equations in their estimation, but rely on data that comes before your current measurement. If you want to use the data that comes afterwards, Rauch-Taung-Striebel smoothing is an extension of Kalman filtering that takes all of your data as well as physical models to estimate position, velocity and acceleration over time from a set of position measurements. I do recommend starting with Alpha-Beta-Gamma filtering though, its easy to understand, quick to program and is oftentimes good enough.