Why is this matrix invertible in the Kalman gain?

Question

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?

Answer 1

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$.

Answer 2

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.