The Kalman Filter

These notes are based on

Meinhold R.J., Singpurwalla N.D., (1983): Understanding the Kalman Filter. The American Statistician, 37, 123–127.

Model

The Kalman Filter provides an efficient recursive estimator for the unobserved state of a linear discrete time dynamical system in the presence of measurement error. Kalman (1960) first introduced the method in the Engineering literature, but it can be understood in the context of Bayesian inference.

Let $y_t$ denote a vector of observed variables at time $t$ and let $s_t$ denote the unobserved state variables of the system at time $t$. We wish to conduct inference about the state variables given only the observed data $\{y_t\}$ and the structure of a linear model consisting of a measurement equation and a transition equation.

The evolution of the observed variable depends on the state variables through a linear measurement equation $$label\mathrm{measurement}{y}_t=F{s}_t+{\epsilon }_t,{\epsilon }_t\sim N(0,{\Omega }_{\epsilon }).$$ The variable $y_t$ is observed with measurement error which follows the Normal distribution with mean zero and covariance matrix ${\Omega }_{\epsilon }$.

The state vector $s_t$ obeys the transition equation $$label\mathrm{transition}{s}_t=G{s}_{t-1}+{\eta }_t,{\eta }_t\sim N(0,{\Omega }_{\eta })$$ where $G$ and ${\Omega }_{\eta }$ are known matrices and ${\eta }_t$ captures the influence of effects that are outside the model on the state transition process. The noise terms ${\epsilon }_t$ and ${\eta }_t$ are independent. In general $G$ and $F$ can be time-dependent but for the sake of simplicity the time subscripts are omitted here.

The Kalman Filter is similar in nature to the standard linear regression model. The state of the process $s_t$ corresponds to the regression coefficients, however the state is not constant over time, requiring the introduction of the transition equation.

Bayesian Interpretation

Let $Y_t=(y_t,y_{t-1},\dots ,y_1)$ denote the complete history of observed data at time $t$. Our goal is to obtain the posterior distribution of $s_t$ given $Y_t$. We know from Bayes’ Theorem that $$label\mathrm{bayes}\begin{array}{rl}\mathrm{Pr}(s_t|Y_t)& =\frac{\mathrm{Pr}(y_t|s_t,Y_{t-1})\mathrm{Pr}(s_t|Y_{t-1})}{\mathrm{Pr}(y_t|Y_{t-1})}\\ & \propto \mathrm{Pr}(y_t|s_t,Y_{t-1})\mathrm{Pr}(s_t|Y_{t-1}).\end{array}$$ The left-hand side is the posterior distribution of $s_t$. On the second line, the first term is the likelihood of $s_t$ and the second term is the prior distribution of $s_t$. This equation defines a recursive Bayesian updating relationship.

At time $t-1$, our knowledge of the system is summarized by the the posterior distribution $$label\mathrm{PosteriorLastPeriod}{s}_{t-1}|Y_{t-1}\sim N({\hat{s}}_{t-1},{\Sigma }_{t-1})$$ where ${\hat{s}}_{t-1}$ is our previous estimate about the mean of $s_{t-1}$. This process is initialized at time $0$ by specifying ${\hat{s}}_0$ and ${\Sigma }_0$.

Before observing $y_t$, our best prediction of $s_t$ comes from (eq:transition), namely $G{s}_{t-1}+{\eta }_t$. However, combining this with (eq:PosteriorLastPeriod), we have $$label\mathrm{BayesianPrior}{s}_t|Y_{t-1}\sim N(G{\hat{s}}_{t-1},R_t),$$ where $$label\mathrm{BayesR}{R}_t\equiv G{\Sigma }_{t-1}{G}^{\top }+{\Omega }_{\eta }.$$ This follows directly from the properties of the multivariate Normal distribution.

After observing $y_t$, we can update our knowledge about $s_t$ using the likelihood $\mathrm{Pr}(y_t|s_t,Y_{t-1})$. Let $e_t$ denote the error in predicting $y_t$, $$label\mathrm{error}{e}_t\equiv y_t-{\hat{y}}_t=y_t-FG{\hat{s}}_{t-1}.$$ Observing $e_t$ is equivalent to observing $y_t$ since $F$, $G$, and $s_{t-1}$ are all known. Thus, (eq:bayes) becomes $$label\mathrm{bayes}2\mathrm{Pr}(s_t|y_t,Y_{t-1})=\mathrm{Pr}(s_t|e_t,Y_{t-1})\propto \mathrm{Pr}(e_t|s_t,Y_{t-1})\mathrm{Pr}(s_t|Y_{t-1}).$$

Now, using the measurement equation (eq:measurement), we can write $e_t=F(s_t-G{\hat{s}}_{t-1})+{\epsilon }_t$, and therefore $$label\mathrm{BayesianLikelihood}{e}_t|s_t,Y_{t-1}\sim N(F(s_t-G{\hat{s}}_{t-1}),{\Omega }_{\epsilon }).$$ Now, from Bayes’ Theorem the posterior distribution of $s_t$ satisfies $$label\mathrm{BayesianPosterior}\mathrm{Pr}(s_t|y_t,Y_{t-1})=\frac{\mathrm{Pr}(e_t|s_t,Y_{t-1})\mathrm{Pr}(s_t|Y_{t-1})}{\int \mathrm{Pr}(e_t,s_t|Y_{t-1}){\mathrm{ds}}_t}.$$ Once this probability is computed, we can perform another iteration of the recursion by going back to (eq:bayes).

Calculating the Posterior Distribution

We can calculate the posterior distribution (eq:BayesianPosterior) directly by appealing to the properties of the Normal Distribution. Note that $$label\mathrm{CalculatingDistribution}\left(\begin{array}{c}{s}_t\\ e_t\end{array}\right)|Y_{t-1}\sim N[\left(\begin{array}{c}G{s}_{t-1}\\ 0\end{array}\right),\left(\begin{array}{cc}R& R_t{F}^{\top }\\ F{R}_t& {\Omega }_{\epsilon }+F{R}_t{F}^{\top }\end{array}\right)].$$ where $R_t$ is given by (eq:BayesR). Conditional on $e_t$, the distribution of $s_t$ is $$label\mathrm{CalculatingPosterior}{s}_t|e_t,Y_{t-1}\sim N[G{\hat{s}}_{t-1}{R}_t{F}^{\top }({\Omega }_{\epsilon }+F{R}_t{F}^{\top }{)}^{-1}{e}_t,R_t-R_t{F}^{\top }({\Omega }_{\epsilon }+F{R}_t{F}^{\top }{)}^{-1}F{R}_t].$$

To summarize, the posterior distribution of $s_t$ was be calculated recursively by first choosing initial values for $s_0$ and ${\Sigma }_0$. Then at each period $t$, given the posterior distribution of $s_{t-1}$, with mean ${\hat{s}}_{t-1}$ and covariance matrix ${\Sigma }_{t-1}$ as in (eq:PosteriorLastPeriod), we form a prior for $s_t$ with mean $G{\hat{s}}_{t-1}$ and variance $R_t=G{\Sigma }_{t-1}{G}^{\top }+{\Omega }_{\eta }$ as in (eq:BayesianPrior), evaluate the likelihood in (eq:BayesianLikelihood) given $e_t=y_t-FG{\hat{s}}_{t-1}$, and then arrive at the posterior in time $t$ given by (eq:CalculatingPosterior).

Algorithm

Using the theoretical derivation as a guide, we can implement the Kalman Filter as a recursive algorithm. Given initialization values $s_0$ and ${\Sigma }_0$, at time $t$,

1. The posterior distribution at time $t-1$ is Normal with mean ${\hat{s}}_{t-1}$ and covariance matrix ${\Sigma }_{t-1}$.

2. Form the covariance matrix of the prior distribution, $$R_t=G{\Sigma }_{t-1}{G}^{\top }+{\Omega }_{\eta };$$

3. Calculate the mean of the posterior, $${\hat{s}}_t=G{\hat{s}}_{t-1}+R_t{F}^{\top }({\Omega }_{\epsilon }+F{R}_t{F}^{\top }{)}^{-1}{e}_t;$$

4. Calculate the variance of the posterior: $${\Sigma }_t=R_t-R_t{F}^{\top }({\Omega }_{\epsilon }+F{R}_t{F}^{\top }{)}^{-1}F{R}_t.$$