18
$\begingroup$

I have a covariance matrix:

$\operatorname{cov}(\mathbf{X}, \mathbf{X}) = \operatorname{E}[(\mathbf{X} - \operatorname{E}[\mathbf{X}])(\mathbf{X} - \operatorname{E}[\mathbf{X}])^T]$

According to Wikipedia, it should be a positive semi-definite matrix.

Under what circumstances will it be positive semi-definite rather than positive definite?

The reason I am asking is because I see that a common thing to do when implementing an Unscented Kalman Filter is to implement the square-root of the covariance matrix using the matlab command:

sqrt_P = gamma * chol(P_a, 'lower')

where gamma is a scaling factor and P_a is the state covariance matrix.

I understand that for chol() to work, it needs to be positive definite:

>> help chol
 CHOL   Cholesky factorization.
    CHOL(A) uses only the diagonal and upper triangle of A.
    The lower triangle is assumed to be the (complex conjugate)
    transpose of the upper triangle.  If A is positive definite, then
    R = CHOL(A) produces an upper triangular R so that R'*R = A.
    If A is not positive definite, an error message is printed.

So, what are the dangers in assuming that it isn't positive semi-definite? Will it only be semi-definite when (for example) it is the zero matrix, or when there are fully correlated states?


ADDENDUM:

In the original post, there was a reference to "if the states are fully correlated". This was rather fast and loose with the notation. There is a discussion and an answer on it here.

$\endgroup$
  • 1
    $\begingroup$ The covariance matrix will be positive semi-definite if (and only if? I haven't checked this) a linear combination of the variables is a.s. constant. $\endgroup$ – Qiaochu Yuan Aug 1 '11 at 13:10
  • 3
    $\begingroup$ @Qiaochu: $\newcommand{\X}{\mathbf{X}}$ Wlog, assume $\mathbb{E} \X = 0$. Let $A = \mathrm{cov}(\X,\X)$. If there exists $v$ such that $v^T A v = 0$, then by linearity, $\mathbf{E} (v^T \X)^2 = 0$, hence $v^T \X = 0$ a.s. The other direction is even easier. $\endgroup$ – cardinal Aug 1 '11 at 15:17
  • 3
    $\begingroup$ One can use an eigendecomposition in the case of a psd matrix to find a "square root" instead of the Cholesky decomposition. Namely, there exists orthogonal $U$ and nonnegative diagonal $D$ such that $\mathrm{cov}(\mathbf{X},\mathbf{X}) = U D U^T$. So, taking $Q = U D^{1/2}$ works, in general, as a square-root of the covariance matrix. $\endgroup$ – cardinal Aug 1 '11 at 16:15
  • 1
    $\begingroup$ The Cholesky decomposition might fail in floating point when given a symmetric positive semidefinite matrix. However, one can modify Cholesky to do symmetric pivoting so that the matrix is factored for "as long as the matrix seems positive definite". You'll have to modify your Kalman formula if you adopt this, though. $\endgroup$ – J. M. is a poor mathematician Aug 3 '11 at 5:53
  • 2
    $\begingroup$ For that matter, in that document on the UD-factored version of the UKF, it mentions explicitly "In real applications, the original UKF may fail due to loss of positive-definiteness property of the state covariance matrix."... I guess I have my answer! $\endgroup$ – Damien Aug 3 '11 at 12:52
7
$\begingroup$

Well, in the $1 \times 1$ case, a matrix is positive semi-definite precisely when its single entry is a non-negative number, and a random variable $X$ has zero variance if and only if it is a.s. constant. (If you don't know what ‘a.s.’ means, you may ignore it throughout this discussion.) Indeed, assuming $\mathbb{E}[X] = 0$ (which is no loss of generality), we have $$\operatorname{Var} X = \int_{\Omega} X^2 \mathrm{d} \mathbb{P}$$ and since the integrand is non-negative, this is zero if and only if the integrand is a.s. zero, i.e. if and only if $X = 0$ a.s. In the case where $\mathbb{E}[X] \ne 0$, we have (by linearity) $\operatorname{Var} X = 0$ if and only if $X = \mathbb{E}[X]$ a.s.

In general, if you have a $n \times n$ symmetric matrix $V$, there is an orthogonal matrix $Q$ such that $Q V Q^{\sf T}$ is a diagonal matrix $D$, and $V$ is positive semi-definite if and only if the diagonal entries of $D$ are all non-negative. But if $V$ is the covariance matrix of $\mathbf{X}$, then $D$ is the covariance matrix of $Q \mathbf{X}$, and so $V$ is positive semi-definite but not positive definite if and only if some component of $Q \mathbf{X}$ is a.s. constant. This happens if and only if some linear combination of $\mathbf{X}$ is ‘fully correlated’, to use your phrasing.

$\endgroup$
  • 5
    $\begingroup$ For those wondering, a.s. refers to almost surely. $\endgroup$ – Damien Aug 3 '11 at 12:35

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.