# Online Estimation of the Inverse Covariance Matrix

This post is part 5 of a series of five articles:

$$\def\myX{\mathbf{x}} \def\myM{\mathbf{M}} \def\myY{\mathbf{y}} \def\mySigma{\mathbf{\Sigma}} \def\myM{\mathbf{M}} \def\myT{\mathsf{T}}$$

In practice, it is often required to estimate the inverse of the covariance matrix of a Gaussian distribution, for example, when only a Mahalanobis distance between points has to be computed. In an online setting it can be quite expensive to compute the inverse of the covariance matrix again for each new point arriving, since the complexity of the matrix inverse is $\mathcal{O(n^3)}$. As we will see in the following, it is not necessary to estimate the covariance matrix, if only its inverse is needed and furthermore, the inverse can be adapted incrementally in an efficient manner. The results are shown for the general case with a weighted exponentially decaying estimator.

Remember that the weighted exponentially decaying estimator could be incrementally adapt the coviarance matrix using the following relations:

Now, in order to compute the inverse, we simply apply the Sherman-Morrison formula [1] – a special case of the Woodbury matrix identity [2] – to incrementally update $M_n^{-1}$. The formula is given by

\begin{align} (A+uv^\mathsf{T})^{-1}= A^{-1} - \frac{A^{-1}uv^\myT A^{-1}}{1+v^\myT A^{-1}u}. \end{align}

If we look at Eq. \eqref{eq:M}, we can identify:

With Eq. \eqref{eq:Sigma}, we can finally compute the inverse of the covariance matrix with

## Example Code

In the following some R-code is listed, which illustrates the procedure to incrementally estimate the inverse of the covariance matrix for a set of points collected in the matrix $X$.

If we run this script, we could get the following output:

# References

1. J. Sherman and W. J. Morrison, “Adjustment of an inverse matrix corresponding to a change in one element of a given matrix,” The Annals of Mathematical Statistics, vol. 21, no. 1, pp. 124–127, 1950.
2. M. A. Woodbury, “Inverting modified matrices,” Princeton University, Princeton, NJ, Memorandum Report 42, Statistical Research Group, 1950.

### Markus Thill

I studied computer engineering (B.Sc.) and Automation & IT (M.Eng.). Generally, I am interested in machine learning (ML) approaches (in the broadest sense), but particularly in the fields of time series analysis, anomaly detection, Reinforcement Learning (e.g. for board games), Deep Learning (DL) and incremental (on-line) learning procedures.

### Deriving a Closed-Form Solution of the Fibonacci Sequence using the Z-Transform

The Fibonacci sequence might be one of the most famous sequences in the field of mathmatics and computer science. Already high school stu...… Continue reading

#### Derivation of a Weighted Recursive Linear Least Squares Estimator

Published on May 05, 2019

#### Gaussian Distribution With a Diagonal Covariance Matrix

Published on May 04, 2019