The Kalman Filter V: It's BLUE!

Read first: Kalman Filter IV: Application to position estimation
Read next: Kalman Filter VI: Further examples

Minimum variance estimators

Firstly, we will show that the conditional expectation is a minimum variance estimator.

Does this theorem look too good to be true? Well... it is. We know that if $(X, Y)$ are jointly normally distributed and we know their mean and variance, we can compute the conditional expectation of $X$ given $Y=y$. However, in practice we often encounter cases where the random variables are not normally distributed. But even when they are approximately jointly normal, we won't know their means and variances.

In the context of the Kalman filter, it makes sense that if the noises ($w$ and $v$) are not normally distributed, the Kalman filter will not be the best estimation methodology. The good news is that the Kalman filter remain the best linear filter in any case!

KF is BLUE

In this section we will drop the normality assumptions. The Kalman filter is a linear (affine) estimator. By combining the measurement and time updates of the Kalman filter, we can see that

$$ \hat{x}_{t+1{}\mid{}t} {}={} \underbrace{A_t \hat{x}_{t{}\mid{}t-1}}_{\text{system dynamics}} {}+{} K_t\underbrace{(y_t - C_t\hat{x}_{t{}\mid{}t-1})}_{\text{prediction error}},$$

where $K_t{}={}A_t\Sigma_{t{}\mid{}t-1}C_t^\intercal (C_t\Sigma_{t{}\mid{}t-1}C_t^\intercal + R_t)^{-1}.$ The Kalman filter is an affine filter. It is in fact the best affine filter (will explain). Recall that, by definition, $\hat{x}_{t+1{}\mid{}t} {}={} {\rm I\!E}[x_{t+1} {}\mid{} y_0,\ldots,y_t]$, therefore, the KF is unbiased, i.e.,

$${\rm I\!E}[\hat{x}_{t+1{}\mid{}t}{}-{}x_{t+1}] {}={} {\rm I\!E}[{\rm I\!E}[x_{t+1} {}\mid{} y_0, \ldots, y_t]-x_{t+1}] {}={} 0.$$

The conditional expectation of a random variable $X$ given $Y=y$ minimises the following function

$$f(z; y) {}={} {\rm I\!E}\left[\|X - z\|^2 {}\mid{} Y=y\right].$$

This means that

$$f\left({{\rm I\!E}[X{}\mid{}Y=y]}; y\right) {}\leq{} f(z; y),$$

for all estimators $z(y)$.

Moreover, define the function $F(z; y) {}={} {\rm I\!E}[(X-z)(X-z)^\intercal {}\mid{}Y=y].$ Then,

$$F\left({{\rm I\!E}[X{}\mid{}Y=y]}; y\right) {}\preccurlyeq{} F(z; y),$$

However, ${\rm I\!E}[X{}\mid{}Y=y]$ can be difficult to determine (without the normality assumption); in general, it is a nonlinear function of $y$.

Question: What is the best linear (affine) estimator we can construct?

Suppose that $X$ and $Y$ are jointly distributed. Then the best (minimum variance) estimator of $X$ given $Y=y$ is ${\rm I\!E}[X{}\mid{}Y=y]$. What is the best affine estimator?

Problem statement: Without assuming that $X$ and $Y$ are (jointly) normally distributed, suppose we are looking for estimators of the form $\widehat{X}(y)=A y+b$, i.e., affine estimators. We seek to determine $A=A^\star$ and $b=b^\star$ so that $\widehat{X}(y)=A^\star y+b^\star$ is the best affine estimator, i.e., the best estimator among all affine ones, i.e.,

$$ {\rm I\!E}\left[\|X - A^\star y + b^\star\|^2\right] {}\leq{} {\rm I\!E}\left[\|X - Ay + b\|^2\right],$$

for any $A$ and $b$, and its conditional counterpart

$${\rm I\!E}\left[\|X - \left(A^\star y + b^\star\right)\|^2 {}\mid{} Y {}={} y\right] {}\leq{} {\rm I\!E}\left[\|X - \left(A y + b\right)\|^2 {}\mid{} Y {}={} y\right],$$

also holds for any $A$ and $b$.

Remarks: The estimator can be written as $\widehat{X}(Y) = m_x + A^\star(Y-m_y)$. The Kalman filter is the best affine filter in the sense that it minimises the mean square error, ${\rm I\!E}[\|X-\widehat{X}\|^2].$ Theorem 2 does not require that $X$ or $Y$ be Gaussian. We can prove a similar result for the covariance matrix ${\rm I\!E}[(X-\widehat{X})(X-\widehat{X})^\intercal]$ (guess what...). Later we will show that KF is the best affine filter.

Before the Proof. We will use the following observations: for an $n$-dimensional random variable $Z$:

$${\rm I\!E}[\|Z\|^2] {}={} {\rm I\!E}[Z^\intercal Z] {}={} {\rm I\!E}[{\rm trace}(ZZ^\intercal)] {}={} {\rm trace} {\rm I\!E}[ZZ^\intercal].$$

Secondly, \({\rm Var}[Z] = {\rm I\!E}[ZZ^\top] - {\rm I\!E}[Z]{\rm I\!E}[Z]^\intercal\), so ${\rm I\!E}[ZZ^\top] = {\rm Var}[Z] + {\rm I\!E}[Z]{\rm I\!E}[Z]^\intercal,$ therefore,

$${\rm I\!E}[\|Z\|^2] {}={} {\rm trace} {\rm I\!E}[ZZ^\top] {}={} {\rm trace} {\rm Var}[Z] + {\rm trace} \left({\rm I\!E}[Z]{\rm I\!E}[Z]^\intercal\right).$$

Note also that ${\rm I\!E}[X-AY-b] = m_x - Am_y - b.$

Proof. It is

$$\begin{aligned} {\rm I\!E}[\|X-AY-b\|^2] & \quad {}={} {\rm trace} {\rm Var} [X-AY-b] + {\rm trace}({\rm I\!E}[X-AY-b]({}\cdot{})^\intercal) \\ & \quad {}={} {\rm trace} {\rm Var} [X-AY-b] + \|m_x - Am_y - b\|^2, \end{aligned}$$

where

$$\begin{aligned} {\rm Var}(X-AY-b) {}={} & {\rm I\!E}[(X-m_x-A(Y-m_y))({}\cdot{})^\intercal] \\ {}={} & {\rm I\!E}[(X-m_x)(X-m_x)^\intercal] {}+{} {\rm I\!E}[A(Y-m_y)(Y-m_y)^\intercal{}A^\intercal] \\ & \qquad {}-{} A(Y-m_y){\rm I\!E}[X-m_x]^\intercal {}-{} {\rm I\!E}[X-m_x](Y-m_y)^\intercal A^\intercal \\ {}={} & \Sigma_{xx} + A\Sigma_{yy}A^\intercal - A\Sigma_{yx} - \Sigma_{xy}A^\intercal, \end{aligned}$$

therefore,

$${\rm I\!E}[\|X-AY-b\|^2] {}={} {\rm trace} \left[ \Sigma_{xx} {}+{} A\Sigma_{yy}A^\intercal - A\Sigma_{yx} - \Sigma_{xy}A^\intercal \right] {}+{} \|m_x-Am_y-b\|^2.$$

Now observe that

$$(A-\Sigma_{xy}\Sigma_{yy}^{-1}) \Sigma_{yy} (A-\Sigma_{xy}\Sigma_{yy}^{-1})^\intercal {}={} { A\Sigma_{yy}A^\intercal -\Sigma_{xy}A^\intercal -A\Sigma_{yx} } {}+{} \Sigma_{xy}\Sigma_{yy}^{-1}\Sigma_{yx}.$$

The mean square error can be written as

$$\begin{aligned} {\rm I\!E}[\|X-AY-b\|^2] {}={}& \underbrace{ {\rm trace}[\Sigma_{xx} - \Sigma_{xy}\Sigma_{yy}^{-1}\Sigma_{yx}] }_{\text{independent of } A \text{ and } b} \\ &\quad{}+{} {\rm trace}[(A-\Sigma_{xy}\Sigma_{yy}^{-1}) \Sigma_{yy} (A-\Sigma_{xy}\Sigma_{yy}^{-1})^\intercal] \\ &\qquad{}+{} \|m_x - Am_y - b\|^2.\end{aligned}$$

All terms are nonnegative. The term $\Sigma_{xx} - \Sigma_{xy}\Sigma_{yy}^{-1}\Sigma_{yx}$ is the Schur complement of $\Sigma$, so it is positive semidefinite. The first term is independent of $A$ and $b$. The second term can be made $0$ by taking $A = \Sigma_{xy}\Sigma_{yy}^{-1}$ and the third term vanishes if we take $b = m_x - Am_y$. $\Box$

Exercises

Exercise V.1. Suppose that $(X, Y)$ are jointly distributed with means ${\rm I\!E}[X]=m_x$, ${\rm I\!E}[Y]=m_y$ and covariance matrix

$${\rm Var}\begin{bmatrix}X\\Y\end{bmatrix} {}={} \begin{bmatrix} \Sigma_{xx} & \Sigma_{xy} \\ \Sigma_{yx} & \Sigma_{yy} \end{bmatrix},$$

with $\Sigma_{yy} {}\succ{} 0$. Show that the best affine estimator of $X$ given $Y$ is $\widehat{X}(Y) = A^\star Y + b^\star$ with

$${A^\star {}={} \Sigma_{xy}\Sigma_{yy}^{-1}}, \text{ and } {b^\star = m_x - A^\star m_y},$$

in the sense that

$${\rm I\!E}\left[(X-\widehat{X}(y))(X-\widehat{X}(y))^\intercal\right] {}\preccurlyeq{} {\rm I\!E}\left[(X-Ay-b)(X-Ay-b)^\intercal\right],$$

for any parameters $A$ and $b$.

Hint: follow the steps of the proof of the theorem we just stated, omitting the trace.

Exercise V.2 (Estimator bias and variance). Show that the best linear estimator, $\widehat{X}(Y)= A^\star{}Y + b^\star$, with

$$\begin{aligned} A^\star {}={} & \Sigma_{xy}\Sigma_{yy}^{-1}, \\ b^\star {}={} & m_x - A^\star m_y. \end{aligned}$$

is unbiased, i.e., ${\rm I\!E}[X-\widehat{X}(Y)]=0$ and its variance (the variance of the estimator error, $X-\widehat{X}(Y)$) is

$${\rm Var}[X-\widehat{X}(Y)] {}={} \Sigma_{xx} - \Sigma_{xy}\Sigma_{yy}^{-1}\Sigma_{yx}.$$

Recovering the Kalman Filter

Assumptions: $x_0$, $(w_t)_t$ and $(v_t)_t$ are mutually independent random variables (not necessarily Gaussian) with ${\rm I\!E}[w_t]=0$, ${\rm I\!E}[v_t]=0$, ${\rm I\!E}[x_0] = \tilde{x}_0$, and ${\rm Var}[w_t] = Q_t$, ${\rm Var}[v_t] = R_t$, ${\rm Var}[x_0] = P_0$. Then \((x_0, y_0)\) is jointly distributed with mean

$${\rm I\!E} \begin{bmatrix} x_0 \\ y_0 \end{bmatrix} {}={} \begin{bmatrix} {\tilde{x}_0} \\ {C_0\tilde{x}_0} \end{bmatrix},$$

and variance-covariance matrix

$${\rm Var} \begin{bmatrix} x_0 \\ y_0 \end{bmatrix} {}={} \begin{bmatrix} {P_0} & {P_0C_0^\intercal} \\ {C_0P_0} & {C_0P_0C_0^\intercal + R_0} \end{bmatrix}.$$

By Theorems V.1 and V.2, the best affine estimator of $x_0$ given $y_0$ is

$$\hat{x}_{0}(y_0) {}={} {\tilde{x}_0} {}+{} {P_0C_0^\intercal} ({C_0P_0C_0^\intercal + R_0})^{-1} (y_0 - {C_0\tilde{x}_0}).$$

and the error covariance is

$${\rm Var}[x_0 - \hat{x}_{0}(y_0)] {}={} P_0 {}-{} {P_0C_0^\intercal} ({C_0P_0C_0^\intercal + R_0})^{-1} {C_0P_0}.$$

These are the same formulas as in the Kalman filter!

We can easily show recursively that the Kalman filter is the Best (minimum variance, minimal covariance matrix) Linear (actually affine) Unbiased Estimator (BLUE). "Best linear" means that it is the best among all linear estimators - however, there may be some nonlinear estimator that leads to a lower variance. Without the normality assumption, the Kalman filter is not a minimum variance estimator.

Read next: Kalman Filter VI: Further examples