kalman filtering and smoothing

When the dynamics model and the observation model of a state space model are both Gaussian, that is we have a linear gaussian ssm, we can perform inference efficiently using Kalman filtering methods.

We perform filtering to predict one step and obtain $p({\mathbf{z}}_t|{\mathbf{y}}_{1:t})$. Ignoring the optional exogenous inputs, ${\mathbf{u}}_t$, the algorithm consists of two steps:

• Time update step

$$\begin{array}{rl}p({\mathbf{z}}_t|{\mathbf{y}}_{1:t-1})& =\mathcal{N}({\mathbf{z}}_{t-1}|{\mu }_{t|t-1},{\mathbf{\Sigma }}_{t|t-1})\\ {\mu }_{t|t-1}& ={\mathbf{F}}_t{\mu }_{t-1|t-1}\\ {\mathbf{\Sigma }}_{t|t-1}& ={\mathbf{F}}_t{\mathbf{\Sigma }}_{t-1|t-1}{\mathbf{F}}_t^T+{\mathbf{Q}}_t\end{array}$$

• Measurement step, getting the expected observation $\hat{\mathbf{y}}$

$$\begin{array}{rl}p({\mathbf{z}}_t|{\mathbf{y}}_{1:t})& =\mathcal{N}({\mathbf{z}}_t|{\mu }_{t|t},{\mathbf{\Sigma }}_{t|t})\\ \hat{\mathbf{y}}& ={\mathbf{H}}_t{\mu }_{t|t-1}\\ {\mathbf{S}}_t& ={\mathbf{H}}_t{\mathbf{\Sigma }}_{t|t-1}{\mathbf{H}}_t^T+{\mathbf{R}}_t\\ {\mathbf{K}}_t& ={\mathbf{\Sigma }}_{t|t-1}{\mathbf{H}}_t^T{\mathbf{S}}_t^{-1}\\ {\mu }_{t|t}& ={\mu }_{t|t-1}+{\mathbf{K}}_t(\mathbf{y}-\hat{\mathbf{y}})\\ {\mathbf{\Sigma }}_{t|t}& ={\mathbf{\Sigma }}_{t|t-1}-{\mathbf{K}}_t{\mathbf{H}}_t{\mathbf{\Sigma }}_{t|t-1}\\ & ={\mathbf{\Sigma }}_{t|t-1}-{\mathbf{K}}_t{\mathbf{S}}_t{\mathbf{K}}_t^T\end{array}$$

The algorithm scales as $O(N)$. The full derivation relies on the conjugate properties of Gaussians and is in both the Kevin Murphy and Durbin and Koopman books.

When all the data have arrived, we can perform offline smoothing and obtain $p({\mathbf{z}}_t|{\mathbf{y}}_{1:T})$. The algorithm requires two passes through the data, a forward-filter and backward-smoother, and so scales $O(N^2)$.

$$\begin{array}{rl}p({\mathbf{z}}_t|{\mathbf{y}}_{1:T})& =\mathcal{N}({\mathbf{z}}_t|{\mu }_{t|T},{\mathbf{\Sigma }}_{t|T})\\ {\mu }_{t|t+1}& ={\mathbf{F}}_t{\mu }_{t|t}\\ {\mathbf{\Sigma }}_{t|t+1}& ={\mathbf{F}}_t{\mathbf{\Sigma }}_{t|t}{\mathbf{F}}_t^T+{\mathbf{Q}}_{t+1}\\ {\mathbf{G}}_t& ={\mathbf{\Sigma }}_{t|t}{\mathbf{F}}_t^T{\mathbf{\Sigma }}_{t|t+1}^{-1}\\ {\mu }_{t|T}& ={\mu }_{t|t}+{\mathbf{G}}_t({\mu }_{t+1|T}-{\mu }_{t+1|t})\\ {\mathbf{\Sigma }}_{t|T}& ={\mathbf{\Sigma }}_{t|t}+{\mathbf{G}}_t({\mathbf{\Sigma }}_{t+1|T}-{\mathbf{\Sigma }}_{t+1|t}){\mathbf{G}}_t^T\end{array}$$