# Why is this matrix invertible in the Kalman gain?

In the wikipedia article about Kalman filters, the well-known expression of the matrix of Kalman gains is given: $$\mathbf {K} _{k}=\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\text{T}}\mathbf {S} _{k}^{-1}$$ with $$\mathbf{S}_k=\mathbf {H} _{k}\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\text{T}}+\mathbf {R} _{k}.$$

I understand that $\mathbf{R}_k$, as a covariance matrix, can be asked to be non-singular: it is reasonable to believe that no variance is zero. But this does not answer my question: why is $\mathbf{S}_k$ invertible?

Note that $\mathbf{P} _{k\mid k-1}$, just like $\mathbf{R}_k$, is also a covariance matrix, and for this reason it is (at least) positve semi-definite, i.e., $\mathbf{y}^T\mathbf{P}_{k\mid k-1}\mathbf{y}\ge 0$ for $\mathbf{y}\neq\mathbf{0}$. Now set $\mathbf{y}=\mathbf{H}_k^T\mathbf{x}$ to see that also $\mathbf {H} _{k}\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\text{T}}$ is at least positive semi-definite (positive definite if $\mathbf{P}_{k\mid k-1}$ is positive definite and $\mathbf{H}_k$ has full rank). Finally, note that the sum of two positive semi-definite matrices is positive semi-definite.

For invertibility, we require that the sum of the two matrices is positive definite. This is the case if at least one of the two matrices is positive definite. In practice we can rather safely assume that both $\mathbf{R_k}$ and $\mathbf{P} _{k\mid k-1}$ are positive definite. However, $\mathbf {H} _{k}\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\text{T}}$ is usually only positive semi-definite due to rank-deficiency of $\mathbf{H}_k$, so for invertibility of the sum of the two matrices we have to rely on the positive definiteness of $\mathbf{R}_k$.

• By the way, $\mathbf{H}_k$ is rarely full rank. In many applications it has rank 1. For example, in target tracking $\mathbf{H}_k = [1, 0, 0]$ is a vector that selects one value of the state $\mathbf{x} = [x, \dot{x}, \ddot{x}]^T$, since the we can only observe the position, $x$. Aug 23 '16 at 21:54
• OK, but in general $\mathbf{H}_k$ is not full rank, surely? If it has full rank, that means that the number of outputs is equal to the number of states... which generally doesn't happen.
– Peter K.
Aug 23 '16 at 21:57
• @ssk08 : SNAP!!!
– Peter K.
Aug 23 '16 at 21:57
• @ssk08 blush :-) Thank-you. :-)
– Peter K.
Aug 23 '16 at 22:05
• @ssk08, Peter K., thanks for your comments; I've improved my answer. Aug 24 '16 at 5:27

Let me take a stab at it.

You agree that $\mathbf{R}_k$ is positive definite. Since it is the variance.

Now, $\mathbf{P}_{k|k-1}$ is also positive definite as it is a covariance matrix, as mentioned by @Matt L.

Let us do an eigen-decomposition of $\mathbf{P}_{k|k-1} = \mathbf{Q}{\bf \Lambda}{\bf Q}^T$. The matrix ${\bf \Lambda} = diag[\lambda_1,\lambda_2, \ldots, \lambda_M]$. Therefore, the term $${\bf H}_k {\bf P}_{k|k-1} {\bf H}_k^T= {\bf H}_k \mathbf{Q}{\bf \Lambda}{\bf Q}^T {\bf H}_k^T = \tilde{\bf H}_k {\bf \Lambda}\tilde{\bf H}_k^T$$ where $\tilde{\bf H}_k = {\bf H}_k \mathbf{Q}$ is the transformed observation matrix.

If you express, the matrix $\tilde{\bf H}_k = [\tilde{\bf h}_1, \tilde{\bf h}_2, \ldots, \tilde{\bf h}_M]$, in terms of is columns, you can express $$\tilde{\bf H}_k {\bf \Lambda}\tilde{\bf H}_k^T = \underbrace{\sum_{i = 1}^M \lambda_i\tilde{\bf h}_i\tilde{\bf h}_i^T}_{Sum\, of \, positive\, semidef. matrices}$$

We can see that the expression above yields a sum of positive definite (rank 1) matrices since all $\lambda_i$ are positive and all $\tilde{\bf h}_i\tilde{\bf h}_i^T$ is positive semidefinite.

Therefore the term $({\bf H}_k {\bf P}_{k|k-1} {\bf H}_k^T + {\bf R}_k)$ is invertible because as ${\bf R}_k$ is invertible, adding a positive semidefinite matrix ${\bf H}_k {\bf P}_{k|k-1} {\bf H}_k^T$ maintains the invertibility.

• "$hh^\top$ is positive definite regardless of its entries" What about $h=[0,1]$, then $hh^\top = [[0,0],[0,1]]$ which is semi-definite positive but not positive and not invertible. Aug 24 '16 at 0:15
• But I think the general idea is correct: if the rows of $H$ are linearly independent, $HPH^\top$ is symmetric pd, so $S$ is symmetric pd hence invertible. Aug 24 '16 at 0:40
• Yup, it's positive semidefinite matrix. Thanks. Aug 24 '16 at 7:15