4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Doctor Mohawk Nov 26 '15 at 20:45
  • $\begingroup$ 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$? $\endgroup$ – Brian Borchers Nov 26 '15 at 21:00
  • $\begingroup$ 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? $\endgroup$ – Doctor Mohawk Nov 30 '15 at 16:27
  • $\begingroup$ What about P? It should be positive definite as well. $\endgroup$ – Brian Borchers Nov 30 '15 at 17:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Brian Borchers Dec 1 '15 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.