28
$\begingroup$

I am studying PCA from Andrew Ng's Coursera course and other materials. In the Stanford NLP course cs224n's first assignment, and in the lecture video from Andrew Ng, they do singular value decomposition instead of eigenvector decomposition of covariance matrix, and Ng even says that SVD is numerically more stable than eigendecomposition.

From my understanding, for PCA we should do SVD of the data matrix of (m,n) size, not of the covariance matrix of (n,n) size. And eigenvector decomposition of covariance matrix.

Why do they do SVD of covariance matrix, not data matrix?

$\endgroup$
  • 8
    $\begingroup$ For square symmetric positive semidefinite matrix (such as covariance matrix), eigenvalue and singular value decompositions are exactly the same. $\endgroup$ – amoeba Nov 16 '17 at 10:52
  • 5
    $\begingroup$ I mean they are mathematically the same. Numerically they might indeed use different algorithms and one might be more stable than another (as Ng says). This would be interesting to know more about, +1. $\endgroup$ – amoeba Nov 16 '17 at 11:18
  • 4
    $\begingroup$ Some information about this here: de.mathworks.com/matlabcentral/newsreader/view_thread/21268. But note that any explanation about why one algorithm would be more stable than another is going to be very technical. $\endgroup$ – amoeba Nov 16 '17 at 11:22
  • 2
    $\begingroup$ In Matlab x=randn(10000); x=x'*x; tic; eig(x); toc; tic; svd(x); toc; on my machine outputs 12s for eig() and 26s for svd(). If it's so much slower, it must at least be more stable! :-) $\endgroup$ – amoeba Nov 16 '17 at 11:37
  • 4
    $\begingroup$ That might be based on an incorrect understanding: doing an SVD of the data matrix is more stable than using eig or svd on the covariance matrix, but as far as I know there is no big difference between using eig or svd on the covariance matrix --- they are both backward stable algorithms. If anything, I would put my money on eig being more stable, since it does fewer computations (assuming both are implemented with state-of-the-art algorithms). $\endgroup$ – Federico Poloni Nov 16 '17 at 14:28
17
$\begingroup$

amoeba already gave a good answer in the comments, but if you want a formal argument, here it goes.

The singular value decomposition of a matrix $A$ is $A=U\Sigma V^T$, where the columns of $V$ are eigenvectors of $A^TA$ and the diagonal entries of $\Sigma$ are the square roots of its eigenvalues, i.e. $\sigma_{ii}=\sqrt{\lambda_i(A^TA)}$.

As you know, the principal components are the orthogonal projections of your variables onto the space of the eigenvectors of the empirical covariance matrix $\frac{1}{n-1}A^TA$. The variance of the components is given by its eigenvalues, $\lambda_i(\frac{1}{n-1}A^TA)$.

Consider any square matrix $B$, $\alpha \in \mathbb R$ and a vector $v$ such that $Bv=\lambda v$. Then

  1. $B^kv=\lambda^kv$
  2. $\lambda(\alpha B) = \alpha\lambda( B)$

Let us define $S=\frac{1}{n-1}A^TA$. The SVD of $S$ will compute the eigendecomposition of $S^TS=\frac{1}{(n-1)^2}A^TAA^TA$ to yield

  1. the eigenvectors of $(A^TA)^TA^TA=A^TAA^TA$, which by property 1 are those of $A^TA$
  2. the square roots of the eigenvalues of $\frac{1}{(n-1)^2}A^TAA^TA$, which by property 2, then 1, then 2 again, are $\sqrt{\frac{1}{(n-1)^2} \lambda_i(A^TAA^TA)} = \sqrt{\frac{1}{(n-1)^2} \lambda_i^2(A^TA)} = \frac{1}{n-1}\lambda_i(A^TA) = \lambda_i(\frac{1}{n-1}A^TA)$.

Voilà!

Regarding the numerical stability, one would need to figure out what the employed alogrithms are. If you're up to it, I believe these are the LAPACK routines used by numpy:

Update: On the stability, the SVD implementation seems to be using a divide-and-conquer approach, while the eigendecomposition uses a plain QR algorithm. I cannot access some relevant SIAM papers from my institution (blame research cutbacks) but I found something that might support the assessment that the SVD routine is more stable.

In

Nakatsukasa, Yuji, and Nicholas J. Higham. "Stable and efficient spectral divide and conquer algorithms for the symmetric eigenvalue decomposition and the SVD." SIAM Journal on Scientific Computing 35.3 (2013): A1325-A1349.

they compare the stability of various eigenvalue algorithms, and it seems that the divide-and-conquer approach (they use the same one as numpy in one of the experiments!) is more stable than the QR algorithm. This, together with claims elsewhere that D&C methods are indeed more stable, supports Ng's choice.

$\endgroup$
12
$\begingroup$

@amoeba had excellent answers to PCA questions, including this one on relation of SVD to PCA. Answering to your exact question I'll make three points:

  • mathematically there is no difference whether you calculate PCA on the data matrix directly or on its covariance matrix
  • the difference is purely due to numerical precision and complexity. Applying applying SVD directly to the data matrix is numerically more stable than to the covariance matrix
  • SVD can be applied to the covariance matrix to perform PCA or obtain eigen values, in fact, it's my favorite method of solving eigen problems

It turns out that SVD is more stable than typical eigenvalue decomoposition procedures, especially, for machine learning. In machine learning it is easy to end up with highly collinear regressors. SVD works better in these cases.

Here's Python code to demo the point. I created a highly collinear data matrix, got its covariance matrix and tried to obtain the eigenvalues of the latter. SVD is still working, while ordinary eigen decomposition fails in this case.

import numpy as np
import math
from numpy import linalg as LA

np.random.seed(1)

# create the highly collinear series
T = 1000
X = np.random.rand(T,2)
eps = 1e-11
X[:,1] = X[:,0] + eps*X[:,1]

C = np.cov(np.transpose(X))
print('Cov: ',C)

U, s, V = LA.svd(C)
print('SVDs: ',s)

w, v = LA.eig(C)
print('eigen vals: ',w)

Output:

Cov:  [[ 0.08311516  0.08311516]
 [ 0.08311516  0.08311516]]
SVDs:  [  1.66230312e-01   5.66687522e-18]
eigen vals:  [ 0.          0.16623031]

Update

Answering to Federico Poloni's comment, here's the code with stability testing of SVD vs Eig on 1000 random samples of the same matrix above. In many cases Eig shows 0 small eigen value, which would lead to singularity of the matrix, and SVD doesn't do it here. SVD is about twice more precise on a small eigen value determination, which may or may not be important depending on your problem.

import numpy as np
import math
from scipy.linalg import toeplitz
from numpy import linalg as LA

np.random.seed(1)

# create the highly collinear series
T = 100
p = 2
eps = 1e-8

m = 1000 # simulations
err = np.ones((m,2)) # accuracy of small eig value
for j in range(m):
    u = np.random.rand(T,p)
    X = np.ones(u.shape)
    X[:,0] = u[:,0]
    for i in range(1,p):
        X[:,i] = eps*u[:,i]+u[:,0]

    C = np.cov(np.transpose(X))

    U, s, V = LA.svd(C)

    w, v = LA.eig(C)

    # true eigen values
    te = eps**2/2 * np.var(u[:,1])*(1-np.corrcoef(u,rowvar=False)[0,1]**2)
    err[j,0] = s[p-1] - te
    err[j,1] = np.amin(w) - te


print('Cov: ',C)
print('SVDs: ',s)
print('eigen vals: ',w)
print('true small eigenvals: ',te)

acc = np.mean(np.abs(err),axis=0)    
print("small eigenval, accuracy SVD, Eig: ",acc[0]/te,acc[1]/te)

Output:

Cov:  [[ 0.09189421  0.09189421]
 [ 0.09189421  0.09189421]]
SVDs:  [ 0.18378843  0.        ]
eigen vals:  [  1.38777878e-17   1.83788428e-01]
true small eigenvals:  4.02633695086e-18
small eigenval, accuracy SVD, Eig:  2.43114702041 3.31970128319

Here code the code works. Instead of generating the random covariance matrix to test the routines, I'm generating the random data matrix with two variables: $$x_1=u\\ x_2=u+\varepsilon v$$ where $u,v$ - independent uniform random variables. So, the covariance matrix is $$\begin{pmatrix} \sigma_1^2 & \sigma_1^2 + \varepsilon \rho \sigma_1 \sigma_2\\ \sigma_1^2 + \varepsilon \rho \sigma_1 \sigma_2 & \sigma_1^2 + 2 \varepsilon \rho \sigma_1 \sigma_2 + \varepsilon^2 \sigma_2^2\sigma^2\end{pmatrix}$$ where $\sigma_1^2,\sigma_2^2,\rho$ - variances of the uniforms and the correlation coeffient between them.

Its smallest eigenvalue: $$\lambda= \frac 1 2 \left(\sigma_2^2 \varepsilon^2 - \sqrt{\sigma_2^4 \varepsilon^4 + 4 \sigma_2^3 \rho \sigma_1 \varepsilon^3 + 8 \sigma_2^2 \rho^2 \sigma_1^2 \varepsilon^2 + 8 \sigma_2 \rho \sigma_1^3 \varepsilon + 4 \sigma_1^4} + 2 \sigma_2 \rho \sigma_1 \varepsilon + 2 \sigma_1^2\right)$$ The small eigenvalue can't be calculated by simply plugging the $\varepsilon$ into formula due to limited precision, so you need to Taylor expand it: $$\lambda\approx \sigma_2^2 \varepsilon^2 (1-\rho^2)/2$$

I run $j=1,\dots,m$ simulations of the realizations of the data matrix, calculate the eigenvalues of the simulated covariance matrix $\hat\lambda_j$, and obtain the errors $e_j=\lambda-\hat\lambda_j$.

$\endgroup$
  • 4
    $\begingroup$ Yes, but here OP is asking about SVD vs EIG applied both to the covariance matrix. $\endgroup$ – amoeba Nov 16 '17 at 18:24
  • 1
    $\begingroup$ @amoeba, I clarified the relation of SVD and PCA $\endgroup$ – Aksakal Nov 16 '17 at 18:56
  • $\begingroup$ This is a good answer. I wish, to mention, however, that svd can't detect negative eigenvalues when there are any and you want to see them (if covariance matrix is not original but is, say, smoothed or estimated somehow or inferred or comes out of pairwise deletion of missing values). Moreover, eig on cov matrix remains a little bit faster than svd on it. $\endgroup$ – ttnphns Nov 16 '17 at 22:03
  • $\begingroup$ @ttnphns, non positive definite matrix is an issue, of course $\endgroup$ – Aksakal Nov 16 '17 at 22:27
  • 1
    $\begingroup$ @FedericoPoloni, on FP arithmetic and not knowing the exact answer I disagree. In this case I do know the answer with enough precision for this task. On 2x2 you have a fair point. I'll think of something. $\endgroup$ – Aksakal Nov 19 '17 at 1:22
6
$\begingroup$

For Python users, I'd like to point out that for symmetric matrices (like the covariance matrix), it is better to use numpy.linalg.eigh function instead of a general numpy.linalg.eig function.

eigh is 9-10 times faster than eig on my computer (regardless of matrix size) and has better accuracy (based on @Aksakal's accuracy test).

I am not convinced with the demonstration of the accuracy benefit of SVD with small eigenvalues. @Aksakal's test is 1-2 orders of magnitude more sensitive to random state than to the algorithm (try plotting all errors instead of reducing them to one absolute maximum). It means that small errors in the covariance matrix will have a greater effect on accuracy than the choice of an eigendecomposition algorithm. Also, this is not related to the main question, which is about PCA. The smallest components are ignored in PCA.

A similar argument can be made about numerical stability. If I have to use the covariance matrix method for PCA, I would decompose it with eigh instead of svd. If it fails (which has not been demonstrated here yet), then it is probably worth rethinking the problem that you are trying to solve before starting to look for a better algorithm.

$\endgroup$
2
$\begingroup$

To answer the last part of your question, "Why do they do SVD of covariance matrix, not data matrix?" I believe it is for performance and storage reasons. Typically, $m$ will be a very large number and even if $n$ is large, we would expect $m \gg n$.

Calculating the covariance matrix and then performing SVD on that is vastly quicker than calculating SVD on the full data matrix under these conditions, for the same result.

Even for fairly small values the performance gains are factors of thousands (milliseconds vs seconds). I ran a few tests on my machine to compare using Matlab: enter image description here

That's just CPU time, but storage needs are just as, if not more, important. If you attempt SVD on a million by a thousand matrix in Matlab it will error by default, because it needs a working array size of 7.4TB.

$\endgroup$
  • $\begingroup$ This does not answer the question which is about EIG of the cov matrix vs. SVD of the covariance matrix. $\endgroup$ – amoeba Feb 16 '18 at 8:06
  • 1
    $\begingroup$ His question at the end, highlighted in bold, states, "Why do they do SVD of covariance matrix, not data matrix?" which I answered. $\endgroup$ – Gruff Feb 16 '18 at 11:38
  • $\begingroup$ I'll edit the opening sentence to make it clear I was answering that part of the OP's question. I see how that could be confusing. Thanks. $\endgroup$ – Gruff Feb 17 '18 at 6:02
  • $\begingroup$ If you attempt SVD on a million by a thousand matrix in Matlab it will error by default Good numerical practice is using the thin SVD, in these cases. This will vastly improve storage size and performance. $\endgroup$ – Federico Poloni Oct 15 '18 at 11:50

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.