Kalman Filter

Kalman filtering (and filtering in general) considers the following setting: we have a sequence of states  x_t, which evolves under random perturbations over time. Unfortunately we cannot observe x_t, we can only observe some noisy function of  x_t, namely,  y_t. Our task is to find the best estimate of x_t given our observations of y_t.

Consider the equations

where \epsilon_t \sim \mathcal N ( 0, \Sigma^\epsilon_t) ,  \eta_t ) \sim \mathcal N ( 0, \Sigma^\eta_t) and \epsilon_t and \nu_t are independent. (We let \Sigma^{\epsilon} be the sub-matrix of the covariance matrix corresponding to \epsilon and so forth…)

The Kalman filter has two update stages: a prediction update and a measurement update. These are

Screenshot 2019-05-14 at 07.12.37.pngandScreenshot 2019-05-14 at 07.12.41.png

where

The matrix K_t is often referred to as the Kalman Gain. Assuming the initial state x_0 is known and deterministic P_{0|0} =0 in the above.


We will use the following proposition, which is a standard result on normally distributed random vectors, variances and covariances,

Prop 1. Let u be normally distributed vector with mean \bar{u} and covariance \Sigma_{ u}, i.e.

i) For any matrix A and (constant) vector c, we have that

ii) If we take  u = ( v,  w) then w conditional on v gives

iii) Var ( A u ) = A\Sigma_u A^\top, Cov ( Au , Bu) = A \Sigma_u B^\top.


We can justify the Kalman filtering steps by proving that the conditional distribution of x_{t+1} is given by the Prediction and measurement steps. Specifically we have the following.

Theorem 1.

where y_{[0:t]} := (y_0,...,y_{t}) and a_{[0:t]} := (a_0,...,a_{t}).

Proof. We show the result by induction supposing that

Since x_{t+1} is a linear function of x_t, we have that

where, by Prop 1ii), we have that

Given y_{t+1} = C_t x_{t+1} + \eta_t, we have by Prop 1iii) that Var(y_{t+1} | y_{[0,t]}, a_{[0,t]}) = C_t P_{t+1|t} C^\top_t and Cov(x_{t+1}, y_{t+1} | y_{[0,t]}, a_{[0,t]}) = P_{t+1|t} C^\top_t . Thus

Thus applying Prop 1ii), we get that

$ \square$

Literature

The Kalman filter is generally credited to Kalman and Bucy. The method is now standard in many text books on control and machine learning.

Kalman, Rudolph E., and Richard S. Bucy. “New results in linear filtering and prediction theory.” (1961): 95-108.

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s