SVD, PCA, Eigenvectors and all that

Principal Component Analysis (PCA) provides matrices E,L given a symmetric real matrix C such that CE=EL. The columns of E are the eigenvectors and L is a diagonal matrix with eigenvalues on the diagonal.

Singular Value Decompsition (SVD) decomposes an arbitrary real matrix A as A=USV' where U'U=1, V'V=1 and S nonzero only on the diagonal. Thus A'A=V(S^2)V' so that (A'A)V=V(S^2). Comparing this with CE = EL from PCA shows that V holds the eigenvectors and S^2 are the eigenvalues of A'A. To summarize,

SVD(A) gives eigenvectors of A'A. (1)

In applications we often start with a data matrix A where feature vectors are the rows of A. For example, suppose we have a data matrix where each row is an RGB triple that records color samples of skin. We might be interested in extracting a single direction that best approximates this distribution. To do this we first center the data (subtract the mean RGB triple from all rows of A) and find the principal eigenvector of the distribution. Computationally, we let B=[centered version of A], then SVD(B) yields the eigenvectors of B'B. A numerical example is given in [1].

What happens if we start with a symmetric matrix C instead of a data matrix A? For example, each entry c(i,j) could be a direct measurement of similarity between item i and item j as opposed to being computed as a bunch of products as in C = B'B above. Can we still use SVD to get eigenvectors of C? Because according to (1), SVD(C) gives the eigenvectors of C'C, not C.

We can. SVD(C) gives us the eigendecomposition C'C=VSV'. But C symmetric means C'C=C^2 and so C^2=VSV'. Then we can apply the power trick: A^k=Q(D^k)inv(Q) letting k=1/2 so that C=V(S^(1/2))V'.

SVD(C) gives eigenvectors of C when C is symmetric (2)

Note: It is often said that U and V are "the same by symmetry" when C is symmetric. Precisely how? For example, let C = [0 1; 1 0]. Then SVD yields U=S=1 and V=C. In particular, U is NOT equal to V. (This also shows the fallacy of reasoning that USV'=C=C'=VSU' implies that U=V). However, it IS the case that U and V are the same up to a column permutation. Why? SVD(C) gives the eigenvectors of C'C in the columns of V. SVD(C') gives the eigenvectors of CC' in the columns of U. When C'=C it follows that C'C = CC' so that U and V both "hold" the same eigenvectors, up to column permutation.

[1] GNU Octave example

octave:32> a = rand(5,3);

octave:33> b = a - repmat(mean(a),5,1);

octave:34> c = b' * b;

octave:35> [eigen, lambda] = eig(c)

eigen =

0.55689 0.59340 0.58116

0.56566 -0.78331 0.25778

-0.60820 -0.18518 0.77189

lambda =

0.19666 0.00000 0.00000

0.00000 0.22855 0.00000

0.00000 0.00000 0.74406

octave:36> [u,s,v] = svd(b);

octave:37> v

v =

-0.58116 0.59340 -0.55689

-0.25778 -0.78331 -0.56566

-0.77189 -0.18518 0.60820

octave:38> diag(s) .* diag(s)

ans =

0.74406

0.22855

0.19666