12
$\begingroup$

I am trying to decompose a covariance matrix based on a sparse / gappy data set. I'm noticing that the sum of lambda (explained variance), as calculated with svd, is being amplified with increasingly gappy data. Without gaps, svd and eigen yeild the same results.

This does not seem to happen with an eigen decomposition. I had been leaning towards using svd because the lambda values are always positive, but this tendency is worrying. Is there some sort of correction that needs to be applied, or should I avoid svd altogether for such a problem.

###Make complete and gappy data set
set.seed(1)
x <- 1:100
y <- 1:100
grd <- expand.grid(x=x, y=y)

#complete data
z <- matrix(runif(dim(grd)[1]), length(x), length(y))
image(x,y,z, col=rainbow(100))

#gappy data
zg <- replace(z, sample(seq(z), length(z)*0.5), NaN)
image(x,y,zg, col=rainbow(100))


###Covariance matrix decomposition
#complete data
C <- cov(z, use="pair")
E <- eigen(C)
S <- svd(C)

sum(E$values)
sum(S$d)
sum(diag(C))


#gappy data (50%)
Cg <- cov(zg, use="pair")
Eg <- eigen(Cg)
Sg <- svd(Cg)

sum(Eg$values)
sum(Sg$d)
sum(diag(Cg))



###Illustration of amplification of Lambda
set.seed(1)
frac <- seq(0,0.5,0.1)
E.lambda <- list()
S.lambda <- list()
for(i in seq(frac)){
    zi <- z
    NA.pos <- sample(seq(z), length(z)*frac[i])
    if(length(NA.pos) > 0){
        zi <- replace(z, NA.pos, NaN)
    }
    Ci <- cov(zi, use="pair")
    E.lambda[[i]] <- eigen(Ci)$values
	S.lambda[[i]] <- svd(Ci)$d
}


x11(width=10, height=5)
par(mfcol=c(1,2))
YLIM <- range(c(sapply(E.lambda, range), sapply(S.lambda, range)))

#eigen
for(i in seq(E.lambda)){
    if(i == 1) plot(E.lambda[[i]], t="n", ylim=YLIM, ylab="lambda", xlab="", main="Eigen Decomposition")
    lines(E.lambda[[i]], col=i, lty=1)
}
abline(h=0, col=8, lty=2)
legend("topright", legend=frac, lty=1, col=1:length(frac), title="fraction gaps")

    #svd
for(i in seq(S.lambda)){
    if(i == 1) plot(S.lambda[[i]], t="n", ylim=YLIM, ylab="lambda", xlab="", main="Singular Value Decomposition")
    lines(S.lambda[[i]], col=i, lty=1)
}
abline(h=0, col=8, lty=2)
legend("topright", legend=frac, lty=1, col=1:length(frac), title="fraction gaps")

enter image description here

$\endgroup$
  • $\begingroup$ I'm sorry for being not able to follow your code (don't know R), but here's one or two notions. Negative eigenvalues can appear in eigen-decomposition of a cov. matrix if the raw data had many missing values and those were deleted pairwisely when computing the cov. SVD of such a matrix will report (misleadingly) those negative eigenvalues as positive. Your pictures show that both eigen and svd decompositions behave similarly (if not exactly same) besides that only difference regarding negative values. $\endgroup$ – ttnphns Aug 20 '12 at 15:13
  • 1
    $\begingroup$ P.S. Hope you understood me: sum of eigenvalues must be equal to the trace (diagonal sum) of the cov. matrix. However, SVD is "blind" to the fact that some eigenvalues might be negative. SVD is rarely used to decompose non-gramian cov. matrix, it is typically used either with knowingly gramian (positive semidefinite) matrix or with raw data $\endgroup$ – ttnphns Aug 20 '12 at 15:31
  • 1
    $\begingroup$ @ttnphns - Thanks for your insight. I guess I wouldn't be so worried about the result given by svd if it weren't for the different shape of the eigenvalues. The result is obviously giving more importance to the trailing eigenvalues than it should. $\endgroup$ – Marc in the box Aug 20 '12 at 19:47
4
$\begingroup$

You need to do the sum of the absolute value of eigen values i.e, sum(abs(Eg$values)) and compare it with the sum of the singular values. They would be equal.

The reason is that if you multiply the rows or columns that correspond to the negative eigenvalues with $-1$, then the eigen-value of the new matrix becomes positive and the orthogonality of the eigen-vectors is not disturbed.

The proof of the converse of this beautiful theorem appeared in The algebra of hyperboloids of revolution, Javier F. Cabrera, Linear Algebra and its Applications, Princeton University (now at Rutgers).

Another way to reason this is by the fact that sqrt(eigen(t(Cg) %*% Cg)) are equal to the singular values of Cg. But when the eigenvalues are negative, the data must be represented in a hermitian form with the complex plane taken into account, which is what was missed in the original formulation, i.e the data formed by the symmetric square-root of the matrix with negative eigen values would have complex entries.

$\endgroup$
  • 1
    $\begingroup$ many thanks for this explanation. I was aware of the relationship between eigen and svd, but was unaware that they would still be related given the above-mentioned differences in decomposing the original matrix. Just curious - as far as I can tell, an eigen decomposition will give negative values when a matrix is not "positive definite". Is this the case with all covariance matrices based on gappy data? $\endgroup$ – Marc in the box Aug 21 '12 at 10:57
  • 1
    $\begingroup$ Marc, positive definiteness of a real symmetric matrix is equivalent to having all positive eigenvalues. There is no close relationship with "gappy data," understanding that to mean sparse matrices with many zero entries. After all, the very sparsest among the nonsingular matrices (symmetric or not) are the diagonal ones, which exhibit their eigenvalues as their entries. $\endgroup$ – whuber Aug 21 '12 at 16:11
  • $\begingroup$ @whuber - thanks for your comment. In this case, I interpret "gappy" differently to "sparse" in that the non-values are NaNs and not 0 (zero). Thus the covariance values are scaled by the number of common values (i.e. divided by n-1). In that respect, I don't believe that the covariance matrix actually contained any zeros. $\endgroup$ – Marc in the box Aug 21 '12 at 18:52
  • 1
    $\begingroup$ Finding a way even to estimate the covariance matrix from such missing data is a challenge: I asked a similar question long ago and received some stimulating answers. $\endgroup$ – whuber Aug 21 '12 at 19:19
  • $\begingroup$ I have asked an additional question elaborating on my interest in the subject for the use in Empirical Orthogonal Function (EOF) analysis here: stats.stackexchange.com/questions/34832/… $\endgroup$ – Marc in the box Aug 22 '12 at 9:49

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.