The Extended Kalman Filter: An Interactive Tutorial for Non-Experts

Part 16: Dealing with Nonlinearity

Although nonlinearity introduces a whole new world of possible variations into any system, hope is not lost. As you may have noticed in the previous demo, the first three nonlinear examples have a useful property in common: they are all smoothly curved, as opposed to the final example, which has sharp turnaround. Mathematicians refer to such smoothly curving functions as differentiable. As anyone who has studied calculus can attest, differentiable functions (smooth curves) can be modeled to an arbitrary degree of precision by a sequence of successively smaller line segments. Even without calculus, you can see this in the demo below, which allows you to approximate the function $f(x) = x^2$ by adjusting the size of the line segment $\Delta x$:

$\Delta x$ = 0

So how does this line-segment trick help handle nonlinear relationships in our Kalman Filter? Consider a very simple filter with the following linear equation for its sensor: \[ z_k = 3 x_k +2 \] This equations says that the sensor reading is always three times the corresponding state value, plus two: no matter what the state value, the sensor reading is always three times that value plus two. Now consider a nonlinear sensor equation: \[ z_k = log_2(x_k)\] This equation says that the sensor reading is the logarithm (to the base 2) of the state value: a typical relationship, for example, in our sensation of pitch as a function of frequency. Even if you've never heard of a logarithm before, a quick look a the following table of approximate values shows that the relationship between the state $x_k$ and the sensor reading $z_k$ is not as straightforward as the previous one:

$x_k$ 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10 11 12 13 14 15 16 17 18 19 20
$z_k$ 0.0 1.0 1.6 2.0 2.3 2.6 2.8 3.0 3.2 3.3 3.5 3.6 3.7 3.8 3.9 4.0 4.1 4.2 4.2 4.3

Here, you can see that there are no constants $a$ and such that $z_k = a x_k + b$. We can, however, use our line-segment insight from above to derive a different set of values $a_k$ and $b_k$, one for each timestep, that approximates such a relationship. If you studied calculus, you may remember that we can compute the first derivative of many nonlinear functions ($log$, $sin$, $cos$, etc.) directly. If you didn't study calculus, don't feel bad: the first derivative of a function is really just the best linear (line-segment) approximation to that function at each given point. A little Googling reveals that the first derivative of $log_2(x)$ is approximately $1 / 0.693x$, which makes sense: as $x$ increases, the value of $log_2(x)$ goes up more and more gradually.

Previous:       Next: