5

I've got an extended Kalman filter with innovation covariance defined as $\mathbf{W}=\mathbf{H}\mathbf{P}\mathbf{H}^\textrm{T} + \mathbf{R}$. I want to know the squared Mahalanobis distance $\|z\|^2$ between a (vector) measurement residual $\mathbf{y}$ and the matrix $\mathbf{W}$, e.g., $\|z\|^2 = \mathbf{y}^\textrm{T} \mathbf{W}^{-1} \mathbf{y}$.

At first I was using the Cholesky decomposition and then forward substitution to solve for $\mathbf{L}\mathbf{z}=\mathbf{y}$. Then, $\|z\|^2 = \mathbf{z}^\textrm{T}\mathbf{z}$.

However, sometimes $\mathbf{W}$ does not appear to be positive definite, though it is symmetric. This seems to happen when — based on the residuals — the Mahalanobis distance should be quite large. I can't do a Cholesky decomposition in these cases, so instead I do an LDL' decomposition, and say that $\|z\|^2 = \mathbf{z}^\textrm{T} \mathbf{D}^{-1} \mathbf{z} = \sum_i^{n-1} \frac{z_i^2}{d_i}$.

That gives me a reasonable value in some cases, but sometimes diagonal elements are negative. That gives me a very large negative squared Mahalanobis distance, which doesn't make a lot of sense to me.

I figure I'm making some math error, but I'm also unsure that it should ever be necessary to do an LDL' decomposition. Might something be wrong with my computation of $\mathbf{W}$?

What does it mean when my sample covariance is not positive definite? How should I decompose this in order to compute the squared Mahalanobis distance?

Translunar
  • 151
  • 5

1 Answers1

2

When $W$ is positive semidefinite but singular there will be entries in $D$ that are effectively 0 but due to round-off error might have very small negative values. A common approach would be to set a tolerance and consider all negative values of $D$ and small positive entries in $D$ less than the tolerance to be effectively 0.

Brian Borchers
  • 5,015
  • 1
  • 18
  • 27
  • Can you give me a little bit more justification? I'm actually seeing some really large negative values in D (for example, for one measurement 3-vector, I get -1.8111752954e+206, 4.8592888658e+190, -7.4324207769e+191). I already have near-zero tolerance checks on all divisions. – Translunar Nov 26 '15 at 20:45
  • There is obviously something else wrong then- if your matrix is positive semidefinite then all of the entries in $D$ should be greater than or equal to 0- that's a fact of linear algebra. Can you check the eigenvalues of your $W$ matrix to see that they are alll greater than or equal to 0? What about $P$ and $R$? – Brian Borchers Nov 26 '15 at 21:00
  • Okay, it looks like it's a snowball effect. $\mathbf{W}$ has a slightly negative diagonal, which causes later $\mathbf{W}$'s to have extremely negative diagonals. But $\mathbf{R}$, the "measurement noise covariance," is just a diagonal, basically $\varepsilon \mathbf{I}$, so does this imply that my scalar multiplier $\varepsilon$ is not large enough? – Translunar Nov 30 '15 at 16:27
  • What about P? It should be positive definite as well. – Brian Borchers Nov 30 '15 at 17:30
  • Yes, and if W stops being positive definite, P usually stops being positive definite. But why positive definite and not positive semi-definite, out of curiosity? – Translunar Dec 01 '15 at 18:32
  • 2
    From the numerical computing point of view it's effectively impossible to decide whether a matrix is actually positive semidefinite or whether it's indefinite, because you can't compute eigenvalues exactly. From a modeling perspective you generally want to avoid the degenerate distributions associated with positive semidefinite but singular covariance matrices. – Brian Borchers Dec 01 '15 at 20:47
  • In other words, cases where the Cholesky decomposition don't work are probably not going to provide much helpful information to the filter? – Translunar Dec 02 '15 at 16:20