# Kalman filter swapping algorithmic steps

In the textbooks and in code examples, the Kalman filter equations usually have the prediction step first followed by the measurement updates. Specifically, inside the loop that iterates over the measurements, prediction is first and then the measurement update step. My question is the following: Is it correct to swap these two and put the measurement update first and then the prediction so at each time step I have a prediction for the next time step? What I want to achieve is that at time k I make a prediction about k+1, and then at k+1 I refine the estimates. Does that make sense? Thanks.

• Sorry, I do not understand the down vote. Why is that? – notArefill Apr 9 '17 at 12:48
• There's someone (just one person by the look) downvoting all over and never leaving a comment; I can only conclude that they don't have a good reason for it. I see no problem with your question, it's clear enough and as far as I can see, quite answerable. I think it's worth an upvote – Glen_b Apr 11 '17 at 0:17

If $x$ is the state vector and $S$ is its variance-covariance matrix, and subscript $i|j$ indicates the estimate at time $i$ given information to time $j$, the steps go:

$(x_{0|0},S_{0|0})\stackrel{\rightarrow}{_{_{(P)}}} (x_{1|0},S_{1|0})\stackrel{\rightarrow}{_{_{(U)}}} (x_{1|1},S_{1|1})\rightarrow (x_{2|1},S_{2|1})\rightarrow (x_{2|2},S_{2|2})\rightarrow (x_{3|2},S_{3|2})\rightarrow ...$

The calculation steps (arrows) which are followed by the two halves of the subscript matching are the update steps.

You still have to do the steps in the same order, but note that the arrival of an observation can happen as late as in between the two steps in the usual loop you have - you can't avoid this progression within the KF algorithm, though you can modify what it consists of in various ways, and as long as you progress in that order, you can organize your loop however you like. (The matrix operations you do in each step don't care where you put your loop breaks.)

So, as you say, most times when people write the algorithm they'll progress as follows (in a sort of pseudocode):

Initialize x and S (to 0|0)
For i = 1 to n
predict x and S         (ie. go from i-1|i-1 to i|i-1)
(must observe data point by here because it's needed in the next step)
update x and S          (ie. go from i|i-1 to i|i)


i.e. progressing as
$(x_{0|0},S_{0|0})\, [\rightarrow (x_{1|0},S_{1|0})\rightarrow (x_{1|1},S_{1|1})]\, [\rightarrow (x_{2|1},S_{2|1})\rightarrow (x_{2|2},S_{2|2})]\, [\rightarrow ...$

(with the square brackest $[...]$ denoting what's done within a single loop).

There's nothing stopping you shifting everything along by half a loop:

Initialize x and S (to 0|0)
predict x and S  (ie. go from 0|0 to 1|0)
For i = 1 to n-1
(must observe data point by here because it's needed in the next step)
update x and S   (ie. go from i|i-1 to i|i)
predict x and S  (ie. go from i|i to i+1|i)


i.e. progressing as
$(x_{0|0},S_{0|0})\rightarrow (x_{1|0},S_{1|0})\,[\rightarrow (x_{1|1},S_{1|1})\rightarrow (x_{2|1},S_{2|1})]\,[\rightarrow (x_{2|2},S_{2|2})\rightarrow (x_{3|2},S_{3|2})]\,[\rightarrow$

(if the algorithm will end at any point then you may also do a final update step after the loop).

I think this is just what you were asking if you can do.

This works because that does the same steps in the same order -- it's still the Kalman Filter. The two steps before the loop might be able to be combined into a single step (i.e. in many cases you may be able to just start with the 1|0 values immediately).

• Yes, this is exactly what I was asking. The way I view it is that in the first case, there is an estimate for the "current" state (k) which is then refined at time k , while in the second case (my case), there is an estimate for the next state (k+1), which is refined at k+1. – notArefill Apr 11 '17 at 10:11

Is it correct to swap these two and put the measurement update first and then the prediction so at each time step have a prediction for the next time step?

Depends what you mean by "swap." Let $X_t$ be the state at time $t$. Let $Y_t$ be the observation at time $t$. The Kalman filter assumes you know the observation distribution (call it $g(y_t|x_t)$) and the state transition distribution (call it $f(x_t|x_{t-1})$). The Kalman filter is a recursive formula for the filtering distribution $p(x_t|y_{1:t})$. And it is just Bayes' rule. This is why it works. The predict step gives you $$p(x_t|y_{1:t-1}) = \int f(x_t|x_{t-1})p(x_{t-1}|y_{1:t-1})dx_{t-1} \tag{1}$$ and the update step gives you $$p(x_t|y_{1:t}) \propto g(y_t|x_t) p(x_t|y_{1:t-1}) \tag{2}.$$

So no, you can change the math that it's based on. But, algorithmically, you can "predict" time $t$ before the time $t$ data $y_t$ arrives. This might save you a little time if speed is critical for you. For more information, see @Gleb_b's answer. Basically, the order does not change, but if you separate $(1)$ and $(2)$ into two different functions, you can call $(1)$ as soon as you finished calling step $(2)$ on the last time point. You don't have to wait for your data to arrive to call $(1)$ and $(2)$ in the same function call which might waste time. If you did it this way, your prediction (for either the state or the heretofore unseen data point), would be sitting in memory, available for some action/use before the actual data arrives.

What I want to achieve is that at time k I make a prediction about k+1, and then at k+1 I refine the estimates

Tthis sounds exactly like what the Kalman filter does, whether you're trying to predict the state or the next observation.

• Maybe you meant "So no, you can't" ? Just asking. – notArefill Apr 11 '17 at 10:12
• @notArefill yeah, haha, with the way I think you mean swap you can't. But with what I think you're trying to do I think you will be able to accomplish what you want. – Taylor Apr 11 '17 at 12:10