Estimation of covariance matrices

Given a sample consisting of n independent observations x1,..., xn of a p-dimensional random vector X ∈ Rp×1 (a p×1 column-vector), an unbiased estimator of the (p×p) covariance matrix :\operatorname{\Sigma} = \operatorname{E}\left[\left(X-\operatorname{E}[X]\right ) \left (X-\operatorname{E}[X]\right)^\mathrm{T}\right] is the sample covariance matrix :\mathbf{Q} = {1 \over {n-1}}\sum_{i=1}^n (x_i-\overline{x})(x_i-\overline{x})^\mathrm{T}, where x_i is the i-th observation of the p-dimensional random vector, and the vector :\overline{x}= {1 \over {n}}\sum_{i=1}^n x_i is the sample mean. This is true regardless of the distribution of the random variable X, provided of course that the theoretical means and covariances exist. The reason for the factor n − 1 rather than n is essentially the same as the reason for the same factor appearing in unbiased estimates of sample variances and sample covariances, which relates to the fact that the mean is not known and is replaced by the sample mean (see Bessel's correction). In cases where the distribution of the random variable X is known to be within a certain family of distributions, other estimates may be derived on the basis of that assumption. A well-known instance is when the random variable X is normally distributed: in this case the maximum likelihood estimator of the covariance matrix is slightly different from the unbiased estimate, and is given by :\mathbf{Q_n} = {1 \over n}\sum_{i=1}^n (x_i-\overline{x})(x_i-\overline{x})^\mathrm{T}. A derivation of this result is given below. Clearly, the difference between the unbiased estimator and the maximum likelihood estimator diminishes for large n. In the general case, the unbiased estimate of the covariance matrix provides an acceptable estimate when the data vectors in the observed data set are all complete: that is they contain no missing elements. One approach to estimating the covariance matrix is to treat the estimation of each variance or pairwise covariance separately, and to use all the observations for which both variables have valid values. Assuming the missing data are missing at random this results in an estimate for the covariance matrix which is unbiased. However, for many applications this estimate may not be acceptable because the estimated covariance matrix is not guaranteed to be positive semi-definite. This could lead to estimated correlations having absolute values which are greater than one, and/or a non-invertible covariance matrix. When estimating the cross-covariance of a pair of signals that are wide-sense stationary, missing samples do not need be random (e.g., sub-sampling by an arbitrary factor is valid). ==Maximum-likelihood estimation for the multivariate normal distribution==

A random vector X ∈ Rp (a p×1 "column vector") has a multivariate normal distribution with a nonsingular covariance matrix Σ precisely if Σ ∈ Rp × p is a positive-definite matrix and the probability density function of X is :f(x)=(2\pi)^{-\frac{p}{2}}\, \det(\Sigma)^{-\frac{1}{2}} \exp\left(-{1 \over 2} (x-\mu)^\mathrm{T} \Sigma^{-1} (x-\mu)\right) where μ ∈ Rp×1 is the expected value of X. The covariance matrix Σ is the multidimensional analog of what in one dimension would be the variance, and :(2\pi)^{-\frac{p}{2}}\det(\Sigma)^{-\frac{1}{2}} normalizes the density f(x) so that it integrates to 1. Suppose now that X1, ..., Xn are independent and identically distributed samples from the distribution above. Based on the observed values x1, ..., xn of this sample, we wish to estimate Σ. First steps The likelihood function is: : \mathcal{L}(\mu,\Sigma)=(2\pi)^{-\frac{np}{2}}\, \prod_{i=1}^n \det(\Sigma)^{-\frac{1}{2}} \exp\left(-\frac{1}{2} (x_i-\mu)^\mathrm{T} \Sigma^{-1} (x_i-\mu)\right) It is fairly readily shown that the maximum-likelihood estimate of the mean vector μ is the "sample mean" vector: :\overline{x}=\frac{x_1+\cdots+x_n}{n}. See the section on estimation in the article on the normal distribution for details; the process here is similar. Since the estimate \bar{x} does not depend on Σ, we can just substitute it for μ in the likelihood function, getting : \mathcal{L}(\overline{x},\Sigma) \propto \det(\Sigma)^{-\frac{n}{2}} \exp\left(-{1 \over 2} \sum_{i=1}^n (x_i-\overline{x})^\mathrm{T} \Sigma^{-1} (x_i-\overline{x})\right), and then seek the value of Σ that maximizes the likelihood of the data (in practice it is easier to work with log \mathcal{L}). The trace of a 1 × 1 matrix Now we come to the first surprising step: regard the scalar (x_i-\overline{x})^\mathrm{T} \Sigma^{-1} (x_i-\overline{x}) as the trace of a 1×1 matrix. This makes it possible to use the identity tr(AB) = tr(BA) whenever A and B are matrices so shaped that both products exist. We get :\begin{align} \mathcal{L}(\overline{x},\Sigma) &\propto \det(\Sigma)^{-\frac{n}{2}} \exp\left(-{1 \over 2} \sum_{i=1}^n \left ( \left (x_i-\overline{x} \right )^\mathrm{T} \Sigma^{-1} \left (x_i-\overline{x} \right ) \right ) \right) \\ &=\det(\Sigma)^{-\frac{n}{2}} \exp\left(-{1 \over 2} \sum_{i=1}^n \operatorname{tr} \left ( \left (x_i-\overline{x} \right ) \left (x_i-\overline{x} \right )^\mathrm{T} \Sigma^{-1} \right ) \right) \\ &=\det(\Sigma)^{-\frac{n}{2}} \exp\left(-{1 \over 2} \operatorname{tr} \left( \sum_{i=1}^n \left (x_i-\overline{x} \right ) \left (x_i-\overline{x} \right )^\mathrm{T} \Sigma^{-1} \right) \right)\\ &=\det(\Sigma)^{-\frac{n}{2}} \exp\left(-{1 \over 2} \operatorname{tr} \left( S \Sigma^{-1} \right) \right) \end{align} where :S=\sum_{i=1}^n (x_i-\overline{x}) (x_i-\overline{x})^\mathrm{T} \in \mathbf{R}^{p\times p}. S is sometimes called the scatter matrix, and is positive definite if there exists a subset of the data consisting of p affinely independent observations (which we will assume). Using the spectral theorem It follows from the spectral theorem of linear algebra that a positive-definite symmetric matrix S has a unique positive-definite symmetric square root S1/2. We can again use the "cyclic property" of the trace to write :\det(\Sigma)^{-\frac{n}{2}} \exp\left(-{1 \over 2} \operatorname{tr} \left( S^{\frac{1}{2}} \Sigma^{-1} S^{\frac{1}{2}} \right) \right). Let B = S1/2 Σ −1 S1/2. Then the expression above becomes :\det(S)^{-\frac{n}{2}} \det(B)^{\frac{n}{2}} \exp\left(-{1 \over 2} \operatorname{tr} (B) \right). The positive-definite matrix B can be diagonalized, and then the problem of finding the value of B that maximizes :\det(B)^{\frac{n}{2}} \exp\left(-{1 \over 2} \operatorname{tr} (B) \right) Since the trace of a square matrix equals the sum of eigenvalues ("trace and eigenvalues"), the equation reduces to the problem of finding the eigenvalues λ1, ..., λp that maximize :\prod_{i=1}^n \lambda_i^{\frac{n}{2}} \exp \left (-\frac{\lambda_i}{2} \right ). This is just a calculus problem and we get λi = n for all i. Thus, assume Q is the matrix of eigen vectors, then :B = Q (n I_p) Q^{-1} = n I_p i.e., n times the p×p identity matrix. Concluding steps Finally we get :\Sigma=S^{\frac{1}{2}} B^{-1} S^{\frac{1}{2}}=S^{\frac{1}{2}}\left(\frac 1 n I_p\right)S^{\frac{1}{2}} = \frac S n, i.e., the p×p "sample covariance matrix" :{S \over n} = {1 \over n}\sum_{i=1}^n (X_i-\overline{X})(X_i-\overline{X})^\mathrm{T} is the maximum-likelihood estimator of the "population covariance matrix" Σ. At this point we are using a capital X rather than a lower-case x because we are thinking of it "as an estimator rather than as an estimate", i.e., as something random whose probability distribution we could profit by knowing. The random matrix S can be shown to have a Wishart distribution with n − 1 degrees of freedom. That is: :\sum_{i=1}^n (X_i-\overline{X})(X_i-\overline{X})^\mathrm{T} \sim W_p(\Sigma,n-1). Alternative derivation An alternative derivation of the maximum likelihood estimator can be performed via matrix calculus formulae (see also differential of a determinant and differential of the inverse matrix). It also verifies the aforementioned fact about the maximum likelihood estimate of the mean. Re-write the likelihood in the log form using the trace trick: :\ln \mathcal{L}(\mu,\Sigma) = \operatorname{constant} -{n \over 2} \ln \det(\Sigma) -{1 \over 2} \operatorname{tr} \left[ \Sigma^{-1} \sum_{i=1}^n (x_i-\mu) (x_i-\mu)^\mathrm{T} \right]. The differential of this log-likelihood is :d \ln \mathcal{L}(\mu,\Sigma) = -\frac{n}{2} \operatorname{tr} \left[ \Sigma^{-1} \left\{ d \Sigma \right\} \right] -{1 \over 2} \operatorname{tr} \left[ - \Sigma^{-1} \{ d \Sigma \} \Sigma^{-1} \sum_{i=1}^n (x_i-\mu)(x_i-\mu)^\mathrm{T} - 2 \Sigma^{-1} \sum_{i=1}^n (x_i - \mu) \{ d \mu \}^\mathrm{T} \right]. It naturally breaks down into the part related to the estimation of the mean, and to the part related to the estimation of the variance. The first order condition for maximum, d \ln \mathcal{L}(\mu,\Sigma)=0, is satisfied when the terms multiplying d \mu and d \Sigma are identically zero. Assuming (the maximum likelihood estimate of) \Sigma is non-singular, the first order condition for the estimate of the mean vector is : \sum_{i=1}^n (x_i - \mu) = 0, which leads to the maximum likelihood estimator :\widehat \mu = \bar X = {1 \over n} \sum_{i=1}^n X_i. This lets us simplify :\sum_{i=1}^n (x_i-\mu)(x_i-\mu)^\mathrm{T} = \sum_{i=1}^n (x_i-\bar x)(x_i-\bar x)^\mathrm{T} = S as defined above. Then the terms involving d \Sigma in d \ln L can be combined as : -{1 \over 2} \operatorname{tr} \left( \Sigma^{-1} \left\{ d \Sigma \right\} \left[ nI_p - \Sigma^{-1} S \right] \right). The first order condition d \ln \mathcal{L}(\mu,\Sigma)=0 will hold when the term in the square bracket is (matrix-valued) zero. Pre-multiplying the latter by \Sigma and dividing by n gives :\widehat \Sigma = {1 \over n} S, which of course coincides with the canonical derivation given earlier. Dwyer points out that decomposition into two terms such as appears above is "unnecessary" and derives the estimator in two lines of working. Note that it may be not trivial to show that such derived estimator is the unique global maximizer for likelihood function. ==Intrinsic covariance matrix estimation==

Intrinsic expectation Given a sample of n independent observations x1,..., xn of a p-dimensional zero-mean Gaussian random variable X with covariance R, the maximum likelihood estimator of R is given by :\hat{\mathbf{R}} = {1 \over n}\sum_{i=1}^n x_ix_i^\mathrm{T}. The parameter R belongs to the set of positive-definite matrices, which is a Riemannian manifold, not a vector space, hence the usual vector-space notions of expectation, i.e. "\mathrm{E} [\hat{\mathbf{R}}]", and estimator bias must be generalized to manifolds to make sense of the problem of covariance matrix estimation. This can be done by defining the expectation of a manifold-valued estimator \hat{\mathbf{R}} with respect to the manifold-valued point R as :\mathrm{E}_{\mathbf{R}}[\hat{\mathbf{R}}]\ \stackrel{\mathrm{def}}{=}\ \exp_{\mathbf{R}}\mathrm{E}\left[\exp_{\mathbf{R}}^{-1}\hat{\mathbf{R}}\right] where :\exp_{\mathbf{R}}(\hat{\mathbf{R}}) =\mathbf{R}^{\frac{1}{2}}\exp\left(\mathbf{R}^{-\frac{1}{2}}\hat{\mathbf{R}}\mathbf{R}^{-\frac{1}{2}}\right)\mathbf{R}^{\frac{1}{2}} :\exp_{\mathbf{R}}^{-1}(\hat{\mathbf{R}}) =\mathbf{R}^{\frac{1}{2}}\left(\log\mathbf{R}^{-\frac{1}{2}}\hat{\mathbf{R}}\mathbf{R}^{-\frac{1}{2}}\right)\mathbf{R}^{\frac{1}{2}} are the exponential map and inverse exponential map, respectively, "exp" and "log" denote the ordinary matrix exponential and matrix logarithm, and E[·] is the ordinary expectation operator defined on a vector space, in this case the tangent space of the manifold. Bias of the sample covariance matrix The intrinsic bias vector field of the SCM estimator \hat{\mathbf{R}} is defined to be :\mathbf{B}(\hat{\mathbf{R}}) =\exp_{\mathbf{R}}^{-1}\mathrm{E}_{\mathbf{R}}\left[\hat{\mathbf{R}}\right] =\mathrm{E}\left[\exp_{\mathbf{R}}^{-1}\hat{\mathbf{R}}\right] The intrinsic estimator bias is then given by \exp_{\mathbf{R}}\mathbf{B}(\hat{\mathbf{R}}). For complex Gaussian random variables, this bias vector field can be shown to equal :\mathbf{B}(\hat{\mathbf{R}}) =-\beta(p,n)\mathbf{R} where :\beta(p,n) =\frac{1}{p}\left(p\log n + p -\psi(n-p+1) +(n-p+1)\psi(n-p+2) +\psi(n+1) -(n+1)\psi(n+2)\right) and ψ(·) is the digamma function. The intrinsic bias of the sample covariance matrix equals :\exp_{\mathbf{R}}\mathbf{B}(\hat{\mathbf{R}}) =e^{-\beta(p,n)}\mathbf{R} and the SCM is asymptotically unbiased as n → ∞. Similarly, the intrinsic inefficiency of the sample covariance matrix depends upon the Riemannian curvature of the space of positive-definite matrices. ==Shrinkage estimation==

If the sample size n is small and the number of considered variables p is large, the above empirical estimators of covariance and correlation are very unstable. Specifically, it is possible to furnish estimators that improve considerably upon the maximum likelihood estimate in terms of mean squared error. Moreover, for n A) with some suitable chosen target (B), e.g., the diagonal matrix. Subsequently, the mixing parameter (\delta) is selected to maximize the expected accuracy of the shrunken estimator. This can be done by cross-validation, or by using an analytic estimate of the shrinkage intensity. The resulting regularized estimator (\delta A + (1 - \delta) B) can be shown to outperform the maximum likelihood estimator for small samples. For large samples, the shrinkage intensity will reduce to zero, hence in this case the shrinkage estimator will be identical to the empirical estimator. Apart from increased efficiency the shrinkage estimate has the additional advantage that it is always positive definite and well conditioned. Various shrinkage targets have been proposed: • the identity matrix, scaled by the average sample variance; • the single-index model; • the constant-correlation model, where the sample variances are preserved, but all pairwise correlation coefficients are assumed to be equal to one another; • the two-parameter matrix, where all variances are identical, and all covariances are identical to one another (although not identical to the variances); • the diagonal matrix containing sample variances on the diagonal and zeros everywhere else; • the identity matrix. The Ledoit-Wolf shrinkage has been applied in many fields. It is particularly useful to compute Partial_correlations from high-dimensional data (n < p). Software for computing a covariance shrinkage estimator is available in R (packages corpcor and ShrinkCovMat), in Python (scikit-learn library ), and in MATLAB. ==See also==