Covariance, positive semidefinite matrices, and distance

Introduction

Covariance matrices describe how several variables vary jointly. They occur directly in principal component analysis, where their eigenvectors define the principal directions, and indirectly in methods that compare observations after accounting for their scale and correlation. The relevant matrix class is the class of symmetric positive-semidefinite matrices. This post defines that class, derives why every covariance matrix belongs to it, and then uses the same decomposition to construct whitening transformations and Mahalanobis distance.

Let \(X\) be an \(N\times p\) data matrix. Its rows are \(N\) observations and its columns are \(p\) variables. Assume throughout the first sections that each column has been centred, so that \(\sum_{i=1}^{N}X_{ij}=0\) for every variable \(j\). Centring removes the column means and makes the origin represent the sample mean. The SVD lecture derives principal components and their relation to the singular value decomposition; the purpose here is to state the covariance geometry on which that result rests.

Symmetric positive-semidefinite matrices

A square \(p\times p\) matrix \(A\) is symmetric when

\[ A=A^\top. \]

It is positive semidefinite, abbreviated PSD, when its quadratic form is nonnegative in every direction \(a\in\mathbb{R}^{p}\):

\[ a^\top A a\geq 0. \]

The condition concerns the scalar produced by placing the same vector on both sides of \(A\). It does not say that every entry of \(A\) is nonnegative. For example, a covariance between two variables may be negative even though the covariance matrix is PSD. If \(a^\top A a>0\) for every nonzero \(a\), then \(A\) is positive definite. Positive definiteness is the stronger condition: it rules out a direction with exactly zero variation.

For a real symmetric matrix, the eigenvectors can be chosen as an orthonormal basis. Write its eigendecomposition as

\[ A=V\Lambda V^\top, \]

where \(V\) is \(p\times p\) with \(V^\top V=I_p\), and \(\Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_p)\) contains the eigenvalues. To see what the PSD condition implies, express an arbitrary \(a\) in this eigenvector basis: \(a=Vc\), where \(c=V^\top a\). Substitution gives

\[ \begin{aligned} a^\top A a &= (Vc)^\top V\Lambda V^\top(Vc)\\ &= c^\top\Lambda c\\ &= \sum_{j=1}^{p}\lambda_jc_j^2. \end{aligned} \]

The second line uses \(V^\top V=I_p\). Since \(c_j^2\) is nonnegative, this expression is nonnegative for every \(c\) exactly when every eigenvalue is nonnegative. Thus a symmetric matrix is PSD if and only if all of its eigenvalues are at least zero. It is positive definite if and only if they are all strictly positive.

The covariance matrix

The sample covariance matrix of the centred data matrix \(X\) is

\[ C=\frac{1}{N-1}X^\top X. \]

The dimensions are important. Since \(X^\top\) is \(p\times N\) and \(X\) is \(N\times p\), \(C\) is \(p\times p\): it records a relationship between variables, rather than between observations. Its entry in row \(j\) and column \(\ell\) is

\[ C_{j\ell}=\frac{1}{N-1}\sum_{i=1}^{N}X_{ij}X_{i\ell}. \]

When \(j=\ell\), this is the sample variance of variable \(j\). When \(j\ne\ell\), it is the sample covariance of variables \(j\) and \(\ell\). Interchanging \(j\) and \(\ell\) leaves every product unchanged, so \(C_{j\ell}=C_{\ell j}\) and \(C\) is symmetric.

Covariance matrices are also PSD. Let \(a\) be any \(p\times1\) vector and form the \(N\times1\) vector \(z=Xa\). Its \(i\)-th entry is \(z_i=\sum_{j=1}^{p}X_{ij}a_j\), the value of the linear combination of variables with weights \(a\) for observation \(i\). Because each column of \(X\) is centred, \(z\) is centred as well. Its sample variance is therefore

\[ \operatorname{Var}(z)=\frac{1}{N-1}\sum_{i=1}^{N}z_i^2 =\frac{1}{N-1}(Xa)^\top(Xa) =a^\top\left(\frac{1}{N-1}X^\top X\right)a =a^\top C a\geq0. \]

The last inequality holds because it is a sum of squares divided by \(N-1\). Thus \(a^\top C a\) has a concrete meaning: it is the sample variance in direction \(a\). A zero eigenvalue means that some nonzero linear combination of the variables has no sample variation. This occurs, for example, if one column is an exact linear combination of the others.

Correlation and the geometry of variation

Covariance depends on the units in which variables are measured. If income is recorded in euros rather than thousands of euros, its variance changes by a factor of one million. Correlation removes this unit dependence. Let

\[ D=\operatorname{diag}(C_{11},\ldots,C_{pp}) \]

be the \(p\times p\) diagonal matrix of variances, and suppose each diagonal entry is strictly positive. The correlation matrix is

\[ R=D^{-1/2}CD^{-1/2}. \]

Its \((j,\ell)\) entry is \(C_{j\ell}/\sqrt{C_{jj}C_{\ell\ell}}\), the usual correlation coefficient. The diagonal entries of \(R\) equal one because \(C_{jj}/\sqrt{C_{jj}C_{jj}}=1\). Equivalently, if \(X_s=XD^{-1/2}\) divides every column by its sample standard deviation, then

\[ \frac{1}{N-1}X_s^\top X_s =D^{-1/2}CD^{-1/2}=R. \]

Thus, analysing the correlation matrix is the same as applying covariance analysis after standardising all variables to unit sample variance.

The eigendecomposition \(C=V\Lambda V^\top\) describes the geometry of the data cloud. Along unit eigenvector \(v_j\), the variance is

\[ v_j^\top C v_j=\lambda_j. \]

Consequently, the eigenvectors give perpendicular directions of variation and the eigenvalues state the variance along them. Principal component analysis orders these directions from largest to smallest eigenvalue. If \(X=U\Sigma V^\top\) is the SVD of the centred data matrix, then

\[ C=\frac{1}{N-1}V\Sigma^2V^\top. \]

The right singular vectors are therefore the covariance eigenvectors, and the eigenvalues are \(\sigma_j^2/(N-1)\). This is the connection to PCA; the calculation and low-rank approximation result are developed in the SVD lecture.

Whitening

Whitening transforms variables so that their covariance matrix is the identity. It is useful when a method should treat variation in each retained direction on the same scale. Suppose first that \(C\) is positive definite, so every eigenvalue in \(\Lambda\) is positive. Define the \(p\times p\) whitening matrix

\[ W=V\Lambda^{-1/2}V^\top, \]

where \(\Lambda^{-1/2}=\operatorname{diag}(\lambda_1^{-1/2},\ldots,\lambda_p^{-1/2})\). The whitened data matrix is \(X_w=XW\). Its covariance matrix is

\[ \begin{aligned} \frac{1}{N-1}X_w^\top X_w &=W^\top\left(\frac{1}{N-1}X^\top X\right)W\\ &=W^\top C W\\ &=V\Lambda^{-1/2}V^\top V\Lambda V^\top V\Lambda^{-1/2}V^\top\\ &=VIV^\top=I_p. \end{aligned} \]

Here \(W^\top=W\) because \(V\Lambda^{-1/2}V^\top\) is symmetric, and the two appearances of \(V^\top V\) become \(I_p\). The transformation first rotates the variables into the principal-direction basis, divides coordinate \(j\) by its standard deviation \(\sqrt{\lambda_j}\), and rotates back. A direction with large original variance is contracted more than a direction with small variance.

If \(C\) is only PSD, a zero eigenvalue cannot be inverted. Let \(V_r\) collect the \(r\) eigenvectors with positive eigenvalues and let \(\Lambda_r\) be the corresponding \(r\times r\) diagonal matrix. The reduced whitened coordinates

\[ Z=X V_r\Lambda_r^{-1/2} \]

are \(N\times r\) and satisfy \((N-1)^{-1}Z^\top Z=I_r\). Dropping the zero-variance directions loses no variation, because every observation has the same coordinate in those directions.

Mahalanobis distance

Euclidean distance treats a one-unit difference alike in every coordinate and ignores correlation. For two \(p\times1\) observations \(x\) and \(y\), and a positive-definite covariance matrix \(C\), the Mahalanobis distance is

\[ d_C(x,y)=\sqrt{(x-y)^\top C^{-1}(x-y)}. \]

This is ordinary Euclidean distance after whitening. Since \(C^{-1}=V\Lambda^{-1}V^\top=W^\top W\), substituting \(h=x-y\) gives

\[ d_C(x,y)^2=h^\top W^\top Wh=(Wh)^\top(Wh)=\lVert Wh\rVert_2^2. \]

The equality explains the weighting. Differences in a high-variance direction are divided by a larger standard deviation and therefore count less. Differences in a low-variance direction count more. Correlation matters because the principal directions generally do not coincide with the original variables: Mahalanobis distance measures separation relative to the tilted covariance geometry, rather than relative to the coordinate axes.

When \(C\) is singular, the inverse is unavailable. One can either work only in the \(r\) positive-variance principal coordinates, or replace the inverse by its Moore–Penrose pseudoinverse. In both cases the resulting measure ignores directions in which the sample contains no variation. This restriction is necessary rather than cosmetic: the data provide no scale with which to judge a difference along such a direction.

Conclusion

Covariance matrices are symmetric positive semidefinite because every quadratic form \(a^\top C a\) is the sample variance of a linear combination of variables. Their eigenvectors give perpendicular directions of variation and their eigenvalues give the variance in those directions, which is the covariance geometry used by principal component analysis. Whitening rescales the positive-variance directions to unit variance, while Mahalanobis distance measures separation in those rescaled coordinates. A zero eigenvalue is a genuine absence of sample variation, so it must be omitted or handled with a pseudoinverse rather than inverted.