3
$\begingroup$

I recently went through the mathematical derivations of the Kalman filter (KF), the extended Kalman filter (EKF) and the Unscented Kalman filter (UKF). My question is concerned with some detail concerning the derivation of the UKF.

While there is a lot of literature available for the unscented transform (necessary for estimating the mean and the covariance matrix for both the prediction step as well as for the update step), I did not found anything about the derivation of the empirical Kalman gain. This gain is given by $K_t = \Sigma^{x,z}_t \Sigma_t^{-1}$. Here, $x$ represents a state and $z$ represents an observation. The UKF uses a certain set of states called sigma points which are predicted (for the next time step) using a non-linear system model $g(x)$. Observations can be generated from this transformed sigma point set by applying a non-linear observation model $h(x)$. The term $\Sigma^{x,z}_t$ is an empirical cross-correlation matrix of the predicted sigma points and the observations generated from these predicted sigma points. The term $\Sigma_t^{-1}$ is the inverse of an empirical covariance matrix of the observations generated.

I have no idea of how to derive the formula for the empirical Kalman gain $K_t$ described above. Is it possible to show that this Kalman gain is an empirical version of the Kalman gain used for the EKF or the KF? How does this work? Is there a paper or tutorial available providing a derivation of the empirical Kalman gain? Is there may be at least an intuitive explanation why the cross-correlation matrix carries significant information with respect to the Kalman gain?

$\endgroup$
1
  • $\begingroup$ I think you can show that $K_t = \Sigma_t^{x,z} \Sigma_t^{-1}$ is optimal because it minimizes mean squared error. Then using that $z = F x + \epsilon$ for some matrix $F$ and independent noise term $\epsilon$, leads to further simplification you see in the Kalman filter equations. It's just that for for UKF, you cannot do the additional simplification. I'm not completely sure about all this but I will think about it more after work. $\endgroup$
    – Mark
    Jan 8, 2019 at 15:47

3 Answers 3

1
$\begingroup$

Following the symbols on Wikipedia, the Kalman gain is $K_k = P_{k|k-1}H^T_k S_{k-1}^{-1}$

$S_{k-1}^{-1}$ is equivalent to what you have called $\Sigma_t^{-1}$ in your question, so it suffices to show the equivalence of $P_{k|k-1}H_k^T$ and $\Sigma^{x,t}_z$.

Cross covariance between the predicted state $\hat{x}_{k|k-1}$ and the predicted measurement $H_k \hat{x}_{k|k-1} + v_k$ is (which you have called $\Sigma_{z}^{x,t}$) is defined $E[(\hat{x}_{k|k-1} - E[\hat{x}_{k|k-1}])(H_k\hat{x}_{k|k-1} + v_k - E[H_k\hat{x}_{k|k-1}+v_k])^T]$.

$$E[(\hat{x}_{k|k-1} - E[\hat{x}_{k|k-1}])(H_k\hat{x}_{k|k-1} + v_k - E[H_k\hat{x}_{k|k-1}+v_k])^T]$$ Now use linearity of expectation to factor out $H_k$. $$= E[(\hat{x}_{k|k-1} - E[\hat{x}_{k|k-1}])(H_k(\hat{x}_{k|k-1}- E[\hat{x}_{k|k-1}])+v_k - E[v_k])^T]. $$

Define $\Delta \hat{x}_{k|k-1} \equiv \hat{x}_{k|k-1} - E[\hat{x}_{k|k-1}]$ and $\Delta v_k \equiv v_k - E[v_k]$. $$= E[\Delta \hat{x}_{k|k-1}(H_k\Delta \hat{x}_{k|k-1}+\Delta v_k)^T]. $$ Distribute the transpose. $$= E[\Delta \hat{x}_{k|k-1}(\Delta \hat{x}_{k|k-1}^T H_k^T+\Delta v_k^T)]. $$

Distribute. $$= E[\Delta \hat{x}_{k|k-1}\Delta \hat{x}_{k|k-1}^T] H^T + E[\Delta \hat{x}_{k|k-1} \Delta v_k^T]. $$

Now use independence of $v_k$ to distribute the expectation across the product. $$= E[\Delta \hat{x}_{k|k-1}\Delta \hat{x}_{k|k-1}^T] H^T + E[\Delta \hat{x}_{k|k-1}]E[ \Delta v_k^T]. $$ $$= E[\Delta \hat{x}_{k|k-1}\Delta \hat{x}_{k|k-1}^T] H^T + 0 $$ $$= P_{k|k-1} H_k^T $$

So in the end, the equivalence follows from the standard Kalman filter assumptions. The simplification is not possible for the UKF case because we do not have the matrix $H_k$.

You can, however, get a completely mechanical intuition about the information content of the cross covariance. It answers the following question: "If I wiggle state variable $i$ inside $\Delta \hat{x}_{k|k-1}$ upwards, how likely is it that observation variable $j$ of $(H_k \hat{x}_{k|k-1} + v_k)$ will also go up?" This what the entry $(i,j)$ of the crosscovariance means. And it makes sense that this information would be relevant for the operation of the UKF.

$\endgroup$
1
  • 1
    $\begingroup$ Very nice and simple derivation. Thank you. I like it because it takes as input only concepts of the original (linear) Kalman filter. The UKF just takes these formulas and approximates the (cross) covariance matrices by empirical data (sigma points). $\endgroup$
    – Timmer
    Jan 15, 2019 at 12:08
1
$\begingroup$

For completeness, I want to add some details making it easier for others to understand the proof from above. The textbooks on the vanilla (linear) Kalman filter often give the following formula for the Kalman gain: $K_k = P_{k|k-1}H_k^T(H_kP_{k|k-1}H_k^T + Q_k)^{-1}$. Here, it is assumed that the observation model is given by $z_k = H_kx_{k|k-1} + \epsilon_k$ such that $x_{k | k-1}$ is the predicted state and $\epsilon_k$ is zero-mean gaussian noise with covariance matrix $Q_k$. Since the covariance matrix of the predicted state is given by $P_{k| k-1}$, the distribution of the generated observation is the result of a linear transformation ($H_kx_k$) and an additive gaussian distribution (observation noise $\epsilon_t$) independent of all other distributions. The resulting covariance matrix of the observation which you called $S_{k-1}$ can then be computed from standard results for covariance matrices. It follows easily that $S_{k-1} = H_kP_{k|k-1}H_k^T + Q_k$.

Two little, insignificant mistakes in your derivation:

  1. When factoring out $H_k$, the signs of $v_k$ and $E[v_k]$ are consfused. It must be $v_k - E[v_k]$ instead of $E[v_k] - v_k$. This also changes the definition of $\Delta v_k$. However, this is not a problem for the proof.

  2. During the last part of the proof it is $-\Delta \hat{x}_{k | k-1}\Delta v_k^T$ instead of $+\Delta \hat{x}_{k | k-1}\Delta v_k^T$. This also does not make any difference.

Thanks again for the helpful answer, I will add it to my personal notes on the Kalman Filter.

$\endgroup$
1
  • $\begingroup$ Thanks for your corrections I have updated my answer - hopefully the signs are correct now $\endgroup$
    – Mark
    Jan 27, 2019 at 16:07
1
$\begingroup$

Let us consider the state space model of any discrete-time nonlinear system as follows, \begin{align} &x_k = \phi(x_{k-1}) + \eta_{k-1}, \\& y_k = \gamma(x_k) + \nu_k, \end{align} where $x_k \in \mathbb{R}^{n_x}$ is the state of system, $y_k \in \mathbb{R}^{n_y}$ is sensor output (measurement). $\phi(\cdot) : \mathbb{R}^{n_x} \rightarrow \mathbb{R}^{n_x}$ and $\gamma(\cdot) : \mathbb{R}^{n_x} \rightarrow \mathbb{R}^{n_y}$ are known nonlinear functions of state. The process noise, $\eta_{k-1}$ and measurement noise, $\nu_k$ are white Gaussian with mean zero and covariance $Q_{k-1}$ and $R_k$, respectively. Further, we assume that the initial state $x_0$, $\eta_{k-1}$ and $\nu_k$ are independent to each other.

There is an ample amount of literature on the derivation of the nonlinear filtering algorithm. Now, I am directly coming to your question, how to derive 'Kalman gain' for unscented Kalman filter (UKF). The given 'Kalman gain' holds for all nonlinear filters. So here we are going to derive the Kalman gain for any nonlinear filter.

The posterior state estimate can be calculated as \begin{equation}\label{xpost} \hat{x}_{k|k} = \hat{x}_{k|k-1} + K_k (y_k - \hat{y}_{k|k-1}). \end{equation} To find the posterior estimation error $(\tilde{x}_{k|k})$, we substitute $\hat{x}_{k|k}$ into $x_k$ \begin{equation} \begin{split} \tilde{x}_{k|k}& = x_k - \hat{x}_{k|k-1} - K_k (y_k - \hat{y}_{k|k-1}) \\& = \tilde{x}_{k|k-1} - K_k \tilde{y}_{k|k-1}. \end{split} \end{equation} The posterior error covariance is given by \begin{equation*} \begin{split} P_{k|k} &= E[\tilde{x}_{k|k}\tilde{x}_{k|k}^T] \\& =E[\tilde{x}_{k|k-1}\tilde{x}_{k|k-1}^T] - E[\tilde{x}_{k|k-1}\tilde{y}_{k|k-1}^T]K_k^T - K_k E[\tilde{y}_{k|k-1}\tilde{x}_{k|k-1}^T] + E[\tilde{y}_{k|k-1}\tilde{y}_{k|k-1}^T]K^T \\& = P_{k|k-1} - P^{xy}_{k|k-1} K_k^T - K_k (P^{xy}_{k|k-1})^T + K_k P^{yy}_{k|k-1} K_k^T . \end{split} \end{equation*}

The Kalman family filter is 'minimum mean square estimator' (MMSE). So, here we try to minimize the magnitude of the posterior error covariance matrix. It is equivalent to minimizing the trace of $P_{k|k}$. Taking trace on both side, the above equation looks like \begin{equation*} \begin{split} tr(P_{k|k}) & = tr(P_{k|k-1}) -tr(P^{xy}_{k|k-1} K_k^T) - tr(K_k (P^{xy}_{k|k-1})^T) +tr(K_k P^{yy}_{k|k-1} K_k^T ) \\& = tr(P_{k|k-1}) -2 tr(K (P^{xy}_{k|k-1})^T) + tr(K_k P^{yy}_{k|k-1} K_k^T ). \end{split} \end{equation*}

The trace of $P_{k|k}$ will be minimized, when its derivative with respect to $K_k$ is zero. Taking differentiation on both side with respect to $K_k$ \begin{equation*} \begin{split} &0 = 0 - 2 P^{xy}_{k|k-1} + 2 K_k P^{yy}_{k|k-1} \\& K_k = P^{xy}_{k|k-1} (P^{yy}_{k|k-1})^{-1}. \end{split} \end{equation*}

Few references are important to read.

https://www.kalmanfilter.net/kalmanGain.html

https://en.wikipedia.org/wiki/Kalman_filter#Kalman_gain_derivation

https://ieeexplore.ieee.org/document/4982682

https://www.seas.harvard.edu/courses/cs281/papers/unscented.pdf

https://ieeexplore.ieee.org/document/855552

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .