34
$\begingroup$

I have been researching the meaning of positive semi-definite property of correlation or covariance matrices.

I am looking for any information on

  • Definition of positive semi-definiteness;
  • Its important properties, practical implications;
  • The consequence of having negative determinant, impact on multivariate analysis or simulation results etc.
$\endgroup$
  • 5
    $\begingroup$ Do you want to understand what semi-definiteness is, or do you want to know why correlation matrices must be semi-definite, or do you want to know what important results are implied by this property? $\endgroup$ – whuber Sep 3 '13 at 22:34
  • 4
    $\begingroup$ If correlation matrices where not semi-positive definite then you could get variances that were negative. $\endgroup$ – user25658 Sep 3 '13 at 22:51
  • $\begingroup$ I edited your question a bit, please check it. Also, please note that a matrix with an even number of negative eigenvalues will still have positive determinant. $\endgroup$ – ttnphns Sep 4 '13 at 17:03
  • $\begingroup$ A covariance matrix is NOT always equal to the correlation matrix! Covariance considers normalized variables while the correlation matrix does not. $\endgroup$ – Manoj Kumar Sep 6 '15 at 22:15
  • 1
    $\begingroup$ Related questions: Is every covariance matrix positive definite? considers the broader case of covariance matrices, of which correlation matrices are a special case; also Is every correlation matrix positive semi-definite? and Is every correlation matrix positive definite? $\endgroup$ – Silverfish Nov 21 '15 at 22:45
37
$\begingroup$

The variance of a weighted sum $\sum_i a_i X_i$ of random variables must be nonnegative for all choices of real numbers $a_i$. Since the variance can be expressed as $$\operatorname{var}\left(\sum_i a_i X_i\right) = \sum_i \sum_j a_ia_j \operatorname{cov}(X_i,X_j) = \sum_i \sum_j a_ia_j \Sigma_{i,j},$$ we have that the covariance matrix $\Sigma = [\Sigma_{i,j}]$ must be positive semidefinite (which is sometimes called nonnegative definite). Recall that a matrix $C$ is called positive semidefinite if and only if $$\sum_i \sum_j a_ia_j C_{i,j} \geq 0 \;\; \forall a_i, a_j \in \mathbb R.$$

$\endgroup$
  • $\begingroup$ Thanks, I removed my downvote but I did not upvote because it does not answer about practical implications. Say I have a matrix that is not positive definite (due for exemple to modifification by 'expert'). What would happen if I use it to calibrate and/or simulate data ? Specifically, is this a real problem when trying to study a big sum and there is only a few negative eigen values ? What would be an efficient algorithm to transform a non positive semi-definite correlation matrix to a positive semi-definite one ? What would be the impact of this algorithm ? $\endgroup$ – lcrmorin Nov 26 '15 at 11:10
  • $\begingroup$ @Were_cat Thanks for the reversal of the downvote. $\endgroup$ – Dilip Sarwate Nov 26 '15 at 16:28
  • $\begingroup$ Could you please explain the first equality in the first equation? $\endgroup$ – Vivek Subramanian Mar 22 '18 at 15:32
  • 1
    $\begingroup$ @VivekSubramanian Variance is a special case of the covariance function: $\operatorname{var}(X)=\operatorname{cov}(X,X)$ and the covariance function is bilinear (meaning it is a linear function with respect to each argument: \begin{align}\operatorname{cov}\left(\sum_i a_iX_i,Y\right)&=\sum_i a_i\operatorname{cov}(X_i,Y)\\ \operatorname{cov}\left(X, \sum_i b_jY_j,\right) &=\sum_j b_j \operatorname{cov}(X,Y_j)\end{align} $\endgroup$ – Dilip Sarwate Mar 22 '18 at 15:45
18
$\begingroup$

The answer is quite simple.

The correlation matrix is defined thus:

Let $X = [x_1, x_2, ..., x_n]$ be the $m\times n$ data matrix: $m$ observations, $n$ variables.

Define $X_b= [\frac{(x_1-\mu_1 e)}{s_1}, \frac{(x_2-\mu_2 e)}{s_2}, \frac{(x_3-\mu_3 e)}{s_3}, ...]$ as the matrix of normalized data, with $\mu_1$ being mean for the variable 1, $\mu_2$ the mean for variable 2, etc., and $s_1$ the standard deviation of variable 1, etc., and $e$ is a vector of all 1s.

The correlation matrix is then

$$C=X_b' X_b$$

A matrix $A$ is positive semi-definite if there is no vector $z$ such that $z' A z <0$.

Suppose $C$ is not positive definite. Then there exists a vector w such that $w' C w<0$.

However $(w' C w)=(w' X_b' X_b w)=(X_b w)'(X_b w) = {z_1^2+z_2^2...}$, where $z=X_b w$, and thus $w' C w$ is a sum of squares and therefore cannot be less than zero.

So not only the correlation matrix but any matrix $U$ which can be written in the form $V' V$ is positive semi-definite.

$\endgroup$
  • 2
    $\begingroup$ This is by far the clearest most concise and useful answer. Thanks ! $\endgroup$ – Yohan Obadia Oct 14 '16 at 8:46
12
$\begingroup$

(Possible looseness in reasoning would be mine. I'm not a mathematician: this is a depiction, not proof, and is from my numeric experimenting, not from books.)

  1. A positive semidefinite (psd) matrix, also called Gramian matrix, is a matrix with no negative eigenvalues. Matrix with negative eigenvalues is not positive semidefinite, or non-Gramian. Both of these can be definite (no zero eigenvalues) or singular (with at least one zero eigenvalue). [Word "Gramian" is used in several different meanings in math, so perhaps should be avoided.]
  2. In statistics, we usually apply these terms to a SSCP-type matrix, also called scalar product matrix. Correlation or covariance matrices are particular cases of such matrix.
  3. Any scalar product matrix is a summary characteristic of some multivariate data (a cloud). For example, given $n$ cases X $p$ variables data, we could compute $p$X$p$ covariance matrix between the variables or $n$X$n$ covariance matrix between the cases. When you compute it from real data, the matrix will always be Gramian. You may get non-Gramian (non-psd) matrix if (1) it is similarity matrix measured directly (i.e. not computed from the data) or the similarity measure isn't SSCP-type; (2) the matrix values was incorrectly entered; (3) the matrix is in fact Gramian but is (or so close to be) singular that sometimes the spectral method of computing eigenvalues produces tiny negative ones in place of true zero or tiny positive ones.
  4. An alternative and equivalent summary for the cloud is the matrix of euclidean distances. A scalar product (such as covariance) between a pair of items and the corresponding squared euclidean distance between them are tied by the law of cosines (cosine theorem, look at the picture there): $d_{12}^2 = h_1^2+h_2^2-2s_{12}$, where the $s$ is the scalar product and the $h$'s are the distances of the two items from the origin. In case of covariance matrix between variables $X$ and $Y$ this formula looks as $d_{xy}^2 = \sigma_x^2+\sigma_y^2-2cov_{xy}$.
  5. As interim conclusion: a covariance (or correlation or other scalar product) matrix between some $m$ items is a configuration of points embedded in Euclidean space, so euclidean distances are defined between all these $m$ points.
  6. Now, if [point 5] holds exactly, then the configuration of points is truly euclidean configuration which entails that the scalar product matrix at hand (e.g. the covariance one) is Gramian. Otherwise it is non-Gramian. Thus, to say "$m$X$m$ covariance matrix is positively semi-definite" is to say "the $m$ points plus the origin fit in Euclidean space perfectly".
  7. What are possible causes or versions of non-Gramian (non-Euclidean) configuration? The answers follow upon contemplating [point 4].
    • Cause 1. Evil is among the points themselves: $m$X$m$ distance matrix isn't fully euclidean. Some of the pairwise distances $d$ are such that they cannot agree with the rest of the points in Euclidean space. See Fig1.
    • Cause 2. There is general (matrix-level) mismatch between $h$'s and $d$'s. For example, with fixed $d$'s and some $h$'s given, the other $h$'s must only vary within some bounds in order to stay in consent with Euclidean space. See Fig2.
    • Cause 3. There is localized (pair-level) mismatch between a $d$ and the pair of corresponding $h$'s connected to those two points. Namely, the rule of triangular inequality is violated; that rule demands $h_1+h_2 \ge d_{12} \ge |h_1-h_2|$. See Fig3.
  8. To diagnose the cause, convert the non-Gramian covariance matrix into distance matrix using the above law of cosines. Do double-centering on it. If the resultant matrix has negative eigenvalues, cause 1 is present. Else if any $|cov_{ij}| \gt \sigma_i \sigma_j$, cause 3 is present. Else cause 2 is present. Sometimes more than one cause get along in one matrix.

Fig1.

Fig1

Fig2.

Fig2

Fig3.

Fig3

$\endgroup$
  • 2
    $\begingroup$ Point 6 needs demonstration: you have shown that a matrix of squared Euclidean distances is p-d, but you assert without proof that to each p-d matrix corresponds a Euclidean configuration of points. Also you haven't connected your definition of p-d ("no negative eigenvalues") to any of your subsequent characterizations. The key idea comes at the end (point 8): a p-d matrix can be used to define a distance. Logically, this is where you should begin the analysis. $\endgroup$ – whuber Sep 4 '13 at 20:02
  • $\begingroup$ @whuber: Thank you for the critical appraisal. I'm afraid, when it comes to mathematically proving something, I sink. I've reported part of my practical experience (I said that); the answer wasn't really an analytical sequence. Wouldn't you like then to add your own answer that can correct/improve mine? It might turn out a valuable aid. Or, you are free to work on my text to improve it if you find it not downright futile. $\endgroup$ – ttnphns Sep 4 '13 at 20:57
  • $\begingroup$ P.S. My point 8 implies that since double centering anchors a configuration of points to its centroid, this operation itself does not introduce non-euclidity (it itroduces only singularity because the new point, centre, belongs to the same space). Thence we can check if the initial configuration was euclidean. Is that not correct? $\endgroup$ – ttnphns Sep 4 '13 at 21:09

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.