Must a matrix of sample pairwise covariances be PSD?

Question

Consider a random vector $\mathbf{X}=(X)_{i=1}^n$. Then the covariance matrix $$C=\mathbb{E}[(\mathbf{X}-\mu(\mathbf{X}))(\mathbf{X}-\mu(\mathbf{X}))^\top]$$ is by definition positive-semidefinite. (The random components in my case of interest all have unit variance and zero mean, so $C$ is also the correlation matrix). Moreover the same is true, up to numerical sensitivity, for a sample covariance matrix (e.g. this answer).

My understanding, however, is that this assumes each sample measures all $n$ components of the random vector. Suppose instead that each sample is pairwise i.e. only two of the components are measured. In that case, we can still compute the sample covariance between any two components by considering only those measurements which contained them. Is the resulting matrix of sample pairwise covariances still guaranteed to be PSD?

My suspicion would be that this represents an extreme case of 'partial pairwise deletion' and therefore one may certainly lose the PSD property. But I have little intuition for how sensitive the PSD condition is and so would appreciate more detail. For instance, in my case of interest the choice of pairs is not random and I can thus ensure that each pair has the same sample size; does this make a difference in whether the PSD property is preserved? I'd also be interested in the numerical sensitivity of such.

Answer 1

If you only have pairwise samples, the sample covariance matrix need not be PSD any more. A trivial example in R follows:

x <- matrix(rnorm(36), 12, 3)

cov_x <- matrix(0,3,3)

# We observe x1 and x2 for observations 1...4
# We observe x1 and x3 for observations 5...8
# We observe x2 and x3 for observations 9...12

cov_x[1,1] <- var(x[1:8,1])
cov_x[2,2] <- var(x[c(1:4,9:12),2])
cov_x[3,3] <- var(x[5:12,3])
cov_x[1,2] <- cov_x[2,1] <- cov(x[1:4,])[2,1]
cov_x[1,3] <- cov_x[3,1] <- cov(x[5:8,])[3,1]
cov_x[2,3] <- cov_x[3,2] <- cov(x[9:12,])[3,2]

I ran this ten times and seven of them generated a negative eigenvalue, for example:

 > eigen(cov(x))$values
[1] 1.1456649 0.8638590 0.7980396
> eigen(cov_x)$values
[1] 1.6430049  0.8456930 -0.2898667

If you want a PSD covariance matrix estimate, you can treat this as a missing data problem and construct such estimates in any of several ways, see for example the answer and comments to covariance-matrix-estimation-in-presence-of-missing-data.