Kalman Filter: Why do we decrease the state uncertainty regardless of the current measurement?

Question

I'm struggling with fully understanding the concept behind a Kalman filter. For the sake of simplicity, let's ingore the input variable $u$ and assume constant process $Q$ and measurement noise $R$. We can now predict the new state by using the state transition matrix $F$ and the old state estimation $$x^-_k = Fx_{k-1}$$. Same does apply for the estimate uncertainty matrix : $P^-_k = FP_{k-1}F +Q$. Now we observe some data and depending on the ratio between the estimate uncertainty and the measurement uncertainty, we update our belief of the state estimation by calculating the innovation $$x_k = x^-_k + K(z_k - Hx^-_k)$$ where $z_k$ is the current measurement, $H$ is the observation matrix and $K$ is the kalman gain $P^-_kH^T(HP^-_kH^T+R)^{-1}$. To incorporate the new measurement the state uncertainty is updated with $P_k = (1-KH)P^-_k$.

1. Do I see it correctly that $P_k$ decreases with each iteration because $ (1−KH)≤1$? Assuming that this is true, doesn't this mean that the uncertainty in the state estimation becomes very small with enough time steps and eventually tends towards $Q$ since the values within KH become smaller with each step?

2. If we are at a point where the values in $P$ are very small, which yes means that the uncertainty in our estimated state and the estimated measurement is very small, then the influence of the measurements is probably very small as the Kalman gain becomes small - I.e. even if the innovation $z_k-Hx^-_k$ is very large, we trust the prediction of the model, although perhaps the true observation would have been correct?

3. Suppose the values in $P_k$ are very small and we get measurements that are very different from the previous ones, but (for whatever reason) are true. The predictions of the kalman filter will deviate strongly from this and still have a small variance, simply because according to the previous data the prediction of the KL is more probable than the measurement? I.e. At a certain point we have only predictions with a small variance, no matter whether they correspond to the truth and I see now way how the values in $P_k$ could grow again. But I think they should grow because if the innovation is big for some iterations, then there must be something wrong with the predictions

Thankful for any tip or reference

Answer 1

The Kalman filter is one of those interesting algorithms which are completely impenetrable if you don't have the underlying math background (multivariate statisics, in this case), but become utterly obvious in in hindsight when you do.

Every "why" question about the plain old Kalman filter can be answered by looking at its problem statement, which is to design a filter that:

• Assumes zero-mean Gaussian noise driving the processes and measurement error.
• Assumes the states of a linear system is being estimated.
• Assumes that -- aside from noise -- the system parameters and inputs are perfectly known.
• Defines "optimal" as being that solution which, at each step, gives the state estimate whose expected value is the smallest Euclidean distance from the system's actual states (i.e., sum-of-squares).

Most of the time, when the operation of the Kalman filter isn't intuitive, it's because your intuition comes from real world systems, and real world systems aren't linear, real-world noise isn't Gaussian, and real world system models aren't 100% accurate.

Do I see it correctly that Pk decreases with each iteration because (1−KH)≤1? Assuming that this is true, doesn't this mean that the uncertainty in the state estimation becomes very small with enough time steps and eventually tends towards Q since the values within KH become smaller with each step?

For constant $Q$ and $R$ it does decrease asymptotically, but it doesn't tend toward $Q$ because of the update step $P_k = (1-KH)P^-_k$ -- and $K$ depends on $R$. Basically, high $R$ (high measurement noise) increases the uncertainty in the state estimation. Do a web search on "Steady State Kalman" for much more information than will fit into a StackExchange post.

If we are at a point where the values in P are very small, which yes means that the uncertainty in our estimated state and the estimated measurement is very small, then the influence of the measurements is probably very small as the Kalman gain becomes small - I.e. even if the innovation zk−Hx−k is very large, we trust the prediction of the model, although perhaps the true observation would have been correct?

If that is the case, then $Q$ or $R$ or both are wrong. $Q$ and $R$ aren't chosen arbitrarily -- they must match the problem. If (and only if) they do, then the Kalman is optimal in the least-squares sense.

Suppose the values in Pk are very small and we get measurements that are very different from the previous ones, but (for whatever reason) are true. The predictions of the kalman filter will deviate strongly from this and still have a small variance, simply because according to the previous data the prediction of the KL is more probable than the measurement? I.e. At a certain point we have only predictions with a small variance, no matter whether they correspond to the truth and I see now way how the values in Pk could grow again. But I think they should grow because if the innovation is big for some iterations, then there must be something wrong with the predictions

Then $Q$ or $R$ or both are wrong, or the probability distributions aren't Gaussian and the assumptions of a plain old Kalman filter don't hold.

The Kalman filter assumes that the system whose states are being estimated is linear, that $Q$ and $R$ are known, and that the processes they describe are Gaussian. If they aren't known (or are not matched to the problem at hand) then the Kalman won't give optimal results. If the processes are not Gaussian then the Kalman filter will be the best linear filter in the mean-squared sense, but it won't be the best filter overall, and there may be some other sense (i.e., min-max) where it isn't optimal.

You seem to either be confused about the necessary condition (sometimes impossible to meet) that $Q$ and $R$ are known, or that the plain old Kalman assumes Gaussian processes.

If, for example, your measurement usually has a Gaussian error, but occasionally has a really bad measurement (i.e., it's got some almost-Gaussian long-tailed distribution), then you may be able to get close to an optimal filter with a filter that's a plain old Kalman at its core, but which monitors the error between $\hat z$ and the measured $z$, and if that error is much larger than predicted by $H\ P\ H^T$ you substitute in a much larger $R$ than "normal".

OTOH, if your system usually runs along smoothly, but every once in a while it acts like it got hit with a rock, you could again detect that $\hat z$ is not matching measurement, and substitute in a large $Q$ and recompute $P$ (especially if the "got hit by a rock" mechanism is known, and has a known effect on $P$).

Neither of these is indicative of problems with the plain old Kalman filter per se -- just that it is only optimal in one sense, and only for a certain model, and only when reality actually matches the model that you use to generate the filter. Stray outside of the bounds where it is the right answer and -- you'll get the wrong answer.

Answer 2

• I am currently building a 1D Kalman filter for tracking stock trends as a daytrader, and find the YouTube KF lectures by Michel van Biezen (which is also the name of his YouTube channel) to be very helpful for understanding the process in 1D. He takes it out of the matrix format and reduces it to a recurring set of 3 equations, whose variables are for measurement (M), measurement error (m), estimate (E), estimate error (e), and Kalman Gain (K), essentially as follows:

• (1) Kalman Gain: K = e/(e+m), whose complement [1-K] = m/(e+m) can also be useful. K is a number between 0 and 1 that evaluates how much of the total error of both the previous Estimate and the current Measurement can be attibuted to the previous Estimate. A K-value close to 1 means that the current Measurement is more accurate, and a value close to 0 means that the previous Estimate is more accurate. As to how the KF knows that, we'll get into that soon.

• (2) The Estimation update: E(t) = E(t-1) + K[M - E(t-1)]. I prefer to rewrite this equation as: E(t) = KM + [1-K]E(t-1), to show more plainly how the range from which the next (i.e., current) Estimate E(t) will come from, will extend from the value of the previous Estimate E(t-1) to that of the current Measurement M, and how K, the Kalman Gain will determine what value that will be. Again, a K-value close to 1 will favor the current Measurement more, while a K-value close to 0 will favor the previous estimate more.

• (3) The Estimation Error update: e(t) = [1-K]e(t-1). Here we can see how the current error in the Estimate, e(t), will almost surely be smaller than the previous error in the Estimate, e(t-1), since the value of the Kalman Gain K will almost surely be greater than 0. We'll shortly see more about how this works, but for now we'll just observe how with a K-value close to 1, the drop in Estimation error will be relatively large, and that this will occur more when the current Measurements are considered to be more accurate than the current Estimates.

• At this point, we now have the "classic" look at the Kalman filter, but what I find helpful (and potentially more efficient) is to substitute equation (1) and its complement into equations (2) and (3) as follows:

• First, equation (1) and its complement are: (1) K = e/(e+m), and [1 - K] = m/(e+m).

• Substituting these into equation (2) gives us: (2) E(t) = KM + [1-K]E(t-1) = Me/(e+m) + Em/(e+m) = (Me + Em)/(e+m). In other words, E(t) = (Me + Em)/(e+m)

• Similarly, substituting into equation (3), we get: (3) e(t) = [1 - K]e(t-1) = me/(e+m). So now, e(t) = me/(e+m).

• And as an aside, when we invert our new equation (3), we get an analogy to adding parallel resistors, where: 1/e(t) = 1/e + 1/m.

• We see how equations (2) and (3) also share the common denominator (e+m), which we can gain more insight by dividing E(t) by e(t) to get:

• E(t)/e(t) = [(Me + Em)/(e+m)]/[me/(e+m)] = (Me + Em)/(em) = (Me/em) + (Em/em) = M/m + E/e. Thus: E(t)/e(t) = M(t)/m(t) + E(t-1)/e(t-1)

• Just to briefly recap, for equation (2) we now have: E(t)/e(t) = M(t)/m(t) + E(t-1)/e(t-1) , and for equation (3), we now have 1/e(t) = 1/m(t) + 1/e(t-1).

• These equations can now provide both greater insight and potential usefulness.

• First, we can extend the analogy of the addition of parallel resistors in equation (3) further:

• Since 1/e(t) = 1/e(t-1) + 1/m(t), then 1/e(t-1) = 1/e(t-2) + 1/m(t-1), and 1/e(t-2) = 1/e(t-3) + 1/m(t-2), and so on back up to the first instance of the process.

• This means that: 1/e(t) = 1/m(t) + 1/m(t-1) + 1/m(t-2) + 1/m(t-3)... and so on back up to the very first measurement.

• Similarly, with equation (2) we can go from: E(t)/e(t) = M(t)/m(t) + E(t-1)/e(t-1), to E(t)/e(t) = M(t)/m(t) + M(t-1)/m(t-1) + M(t-2)/m(t-2) + M(t-3)/m(t-3), and so on back up to the first instance.

• So now we take our current Estimate error to simply be the cumulative sum of all previous Measurement errors, up to and including the current one - when added reciprocally like parallel resistors.

• Similarly, we can also see how the current Estimate Signal-to-Noise Ratio (SNR) is also the cumulative sum of all previous Measurement SNRs, again up to and including the current one.

• So to obtain just the Estimate value, we can simply divide the Estimate SNR by the reciprocal of the Estimate Error at each Measurement point, i.e.: E(t) = [E(t)/e(t)]/[1/e(t)]

• And at this point I'll be wanting to implement this into a stock chart to see how it looks.

• I'm concerned about the smoothness of the plot it will produce, and would like to see how a second KF pass will look if it is run immediately after the first pass, only using the newly produced Estimates in the same way the first KF pass used the new Measurements. In other words, a second pass using the same process on the now much-less-noisy KF output from the first pass might smooth things significantly. At first, I was concerned that this might provide very little additional advantage but since each and every estimate point is actually a cumulative sum, this "secondary" pseudo-measurement input might preent itself just like a fresh random data set, only much less noisy. We shall see! In the meantime, all the best in your own projects!

PS: My quick answer to your question is that the "state uncertainty", which I refer to as "Estimate error" decreases because in the KF process, those uncertainties are added the same way you add resistors in a parallel circuit, where adding them in parallel actually decreases the total resistance. In a similar fashion, when the uncertainties are again added reciprocally, the total uncertainty at any point will be less than any of the uncertainties that were added reciprocally get to that point. Thanks for reading this!