# Kalman filtering: 1D case

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?

-
I'm not sure what you're asking. Everything works fine in that case. That's actually a good case to use to try to understand the general case. –  arsmath Sep 21 '10 at 15:12
Actually to begin this filtering process I need to know the initial $\mu_t$ and $\sigma_t$ where $t=0$. But I have no idea how to calculate it.. In the general case at the prediction step we got: $$\bar{\mu}_t = A_t\mu_t + B_tu_t + \epsilon_t$$ So we need to know the initial $\mu_0$ The same thing and even more complicated about the initial covariance $\Sigma_0$. I do not remember the formula right now for calculating the $\bar{\Sigma}_t$. I can assume that the $\mu_0$ of the $x_0$ is $0$. ($\mu_0 = 0$) But what it is just How I think it should be and I can't put anything for $\Sigma_0$ –  maximus Sep 21 '10 at 18:39
There is a mistake, it should be: $$\bar{\mu}_t = A_t\mu{t-1}+B_tu_t+\epsilon_t$$ I have no idea how to calculate the initial covariance for $x_0$ to be able then to start the process. –  maximus Sep 21 '10 at 18:42
Read the link I wrote earlier: citeseerx.ist.psu.edu/viewdoc/… (Part 3 A Kalman Filter in Action: Estimating a Random Constant) They've worked out your problem right there. –  Gilead Sep 22 '10 at 3:45
Very useful! Thank you! –  maximus Sep 22 '10 at 5:58

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.

-
@Gilead Thank you for your answer, it is very useful, I've updated the question. And I will try to read that book but text format is a little bit not convenient to read. May be I will make a PDF using LATEX, when I am free. Thanks –  maximus Sep 22 '10 at 2:50
Here's another good reference: citeseerx.ist.psu.edu/viewdoc/… (see section on Filter Parameters and Tuning - it speaks to your problem). Yes, $R_{t}$ (normally assumed constant, so $R$) has to be measured, or otherwise assumed. –  Gilead Sep 22 '10 at 3:11
If you have historical data from your process, you can use it to identify the noise/disturbance structure using System Identification techniques -- that's the way to get accurate starting covariance matrices. If you have no data, then you must assume something. –  Gilead Sep 22 '10 at 3:17
Thank you very much! Very useful information! –  maximus Sep 22 '10 at 3:19

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.

-
Thank you very much! Useful information about the books! I am currently reading the probabilistic robotics, it is very good in my opinion, however some question arise while reading it.. –  maximus Sep 22 '10 at 2:52