Kalman filtering: 1D case - MathOverflow

Kalman filtering: 1D case

2010-09-21T09:57:10Z

How will the kalman filtering model look like in the case when I just receive some data and want to filter them from noise? The data is actually an acceleration of some object. So the system must be like this:

$$x_t = A_tx_{t-1} + B_tu_t + \epsilon_t$$ $$z_t = C_tx_t + \delta_t$$ Where the $\epsilon_t$ and $\delta_t$ are the white noise. $x_t$ is a state variable. The problem is that I can't figure out what will the system look like in my case, when I receive acceleration measurements (observations - $z_t$) at each time period $\Delta t$. I think I don't need the control vector $u_t$ in my case, so the system will be: $$x_t = A_tx_{t-1} + \epsilon_t$$ $$z_t = C_tx_t + \delta_t$$ I suppose, but not sure about this kind of filter system: $$x_t = x_{t-1} + \epsilon_t$$ $$z_t = x_t + \delta_t$$ But it seems too simple. How to make the first iteration in the Kalman filtering procedure?

EDIT 1: here is the kalman filtering algorithm, taken from the book: probabilistic robotics.

Kalman_filter($\mu_{t-1}$, $\Sigma_{t-1}$, $u_t$, $z_t$) $$\bar{\mu}_t = A_t\mu_{t-1} + B_tu_t$$ $$\bar{\Sigma}_t = A_t\Sigma_{t-1}A_t^T + R_t$$ $$K_t = \bar{\Sigma}_tC_t^T\left(C_t\bar{\Sigma}_tC_t^T + Q_t\right)^{-1}$$ $$\mu_t = \bar{\mu_t} + K_t\left(z_t - C_t\bar{\mu}_t\right)$$ $$\Sigma_t = \left(I - K_tC_t\right)\bar{\Sigma}_t$$ return $\mu_t$, $\Sigma_t$

The thing that I do not understand here is: Here the data that is unknown is - $\Sigma_0$, $\mu_0$ I supppose that I can choose some data by myself for that values. But one more data that is unknown for me is: $R_t$ It comes from: The state transition probability is given by $p(x_t|u_t,x_{t-1})$. And we got: $$x_t = A_t\mu_{t-1} + B_tu_t+\epsilon_t$$ as one of the equations of the Kalman filter.

We also know the normal distribution: $$p(x) = det\left(2\pi\Sigma\right)^{-1/2}exp\left(-1/2(x-\mu)^T\Sigma^{-1}(x-\mu)\right)$$ (I've already asked a question from which you can see where it comes from: question)

So we have:

$\mu_t = A_tx_{t-1} + B_tu_t$(discussed in the question, the link is above) And also $R_t$ is a covariance of the posterior state. Here we got the whole formula.

$$p(x_t|u_t, x_{t-1}) = det\left(2\pi R_t\right)^{-1/2}exp\left(-1/2(x_t-A_tx_{t-1}-B_tu_t)^TR_t^{-1}(x_t-A_tx_{t-1}-B_tu_t)\right)$$

So, how should be the $R_t$ value estimated? It depends on $t$. If I set some value by myself to $\Sigma_0$ and $\mu_0$ then what should be done with $R_t$ which appears in the Kalman filter algorithm listed above in this step: $$\bar{\Sigma}_t = A_t\Sigma_{t-1}A_t^T + R_t$$ ?

Correct me please if I am wrong: $$R_t = cov\left(x_t|x_{t-1}, u_t\right) = E\left[x_t^2|x_{t-1}, u_t \right] - \left(E\left[x_t|x_{t-1},u_t\right]\right)^2$$ $$R_t = E\left[x_t^2|x_{t-1}, u_t \right] - \left(A_tx_{t-1}+B_tu_t\right)^2$$ So how to calculate the $R_t$? Should it be also set by user? Actually $R_t$ is a covariance of the noise $\epsilon_t$ in equation: $$x_t = A_tx_{t-1} + B_tu_t + \epsilon_t$$. And it depends on $t$. The same thing about the noise covariance of $\delta_t$ in case of this equation of the Kalman filter: $$z_t = C_tx_t + \delta_t$$

EDIT 2: So as I understood four parameters should be selected by the user (tuned), they are:

$Q_t$, $R_t$, $\mu_0$ and $\Sigma_0$

Am I right?

Answer by Will Jagy for Kalman filtering: 1D case

2010-09-21T19:58:27Z

The original uses of the filter were in navigation, although Kalman was arguing from an electrical engineering perspective. The first huge success was on the Apollo missions. So there are texts at a variety of levels. I photocopied two of them, lots of effort but these engineering-related books are amazingly expensive, even by mathematics standards. They are:

Global Positioning Systems, Inertial Navigation, and Integration (Second Edition, 2007, Wiley) Mohinder S. Grewal, Lawrence R. Weill, Angus P. Andrews

Kalman Filtering: Theory and Practice using MATLAB (second edition, 2001, Wiley) Mohinder S. Grewal, Angus P. Andrews

A year or two ago I was tutoring a CS major and the filter was included. The presentation (no course textbook, the lecturers wrote it as they went along) was hopeless. I encourage you to branch out to extra books. Given the nature of your questions, borrowing these books and others in some interlibrary loan would help you a good deal. It is nice that arsmath is available to answer some questions, but MO is hardly going to serve as an effective tutor for a subject that is so very intricate in practice.

Answer by Gilead for Kalman filtering: 1D case

2010-09-22T01:05:48Z

A few remarks on your problem:

You have to assume something for your initial variance (not covariance in this case, since it's univariate). The same applies in the multivariate case -- you have to know something about $P_{0|0}$. You do not calculate the initial variance.
If you really have no idea what to choose for your initial variance, choose a large number. This is equivalent to saying "I don't know what's going on in the system, so I'm going to be conservative and assume the worst." As the Kalman filter iterates, it will generally converge and the variance will tend to decrease.
Given a measurement $z_{0}$, you can do the rest (Kalman gain, prediction etc.). In fact in the linear case, it is proven that the Kalman gain can be calculated off-line (see "Separation Principle" http://en.wikipedia.org/wiki/Separation_principle).
If your filter is having trouble converging (very unlikely in this simple case), you can use something called a Re-iterative Kalman Filter (http://tinyurl.com/2fokknm). This Kalman filters iterates $n$ steps and uses the information collected to correct $x_{0}$. At $n+1$, it uses to the corrected $x_{0}$ and recursively calculates $x_{n+1}$; thereafter the Kalman filter will usually converge rapidly.

Peter D. Joseph (a pioneer in the use of Kalman Filters in the 1960s) wrote a simple tutorial on the subject in which he gives the reader an intuitive understanding of what these filters do -- in it he motivates the subject through the derivation of a 1-D example. Unfortunately the webpage no longer exists; however I managed to find the original document in text format: http://www.humintel.com/hajek/kalman.txt

If you're willing to reformat it into $\LaTeX$, I think you'll find the document helpful.