# Clear description of PCA using SVD of covariance matrix

After reading thousands of articles on PCA and SVD, using them in a number of programming frameworks and even implementing similar techniques (like Random Indexing) I found out that I still have doubts about some parts of PCA for dimension reduction. So let me show what I know and what I have doubts about.

Let's say we have $N$ observations of $M$-dimensional data, organized as matrix $A \in R^{N * M}$. To perform PCA we should first compute MLE estimate of covariance matrix $\Sigma \in R^{M*M}$:

$$\Sigma=\frac{1}{N}\sum_{i=1}^N(x_i - \bar x)(x_i - \bar x)^T$$

where $x_i \in R^M$ is $i$-th observation, $\bar x = \frac{1}{N}\sum_{k=1}^{N}x_k \in R^M$ is mean observation.

Then we can decompose $\Sigma$ using SVD as follows:

$$\Sigma = USV^T$$

Now here are several things I'm not sure about:

1. What are dimensions of $U$, $S$ and $V^T$?
2. In $USV^T$ what exactly is considered as eigenvalues and which of them should I use as principal components?
3. How can I project original observations $x_i$ onto new reduced space and vice versa?

UPD. There's a different way to compute PCA using SVD - by factorizing data matrix ($A$ here) instead of covariance matrix ($\Sigma = AA^T$). Good description for this process may be found in this answer.

• Please excuse if it sounds rude, but... where are you stuck after reading thousands of articles on PCA? – ttnphns Oct 7 '12 at 15:40
• @ttnphns: the problem is that different articles use different terms and make emphasis on different parts. For example, in some articles they use terms "left eigenvalues" to refer to columns of $U$ and "right eigenvalues" to refer to rows of $V^T$, but they don't say which of them should I use for PCA. Also different notations are used for projection of original vector onto reduced space - normally it is written as $x' = Px$ (where $P$ is matrix of first $k$ eigenvectors), but I have also seen following form, that breaks down my understanding of used dimensions: $x' = \sum p_i x$ – ffriend Oct 7 '12 at 15:54
• I hoped you know that because covariance matrix is symmetric U=V (with columns corresponding to the PCs) and is the same eigenvectors matrix as eigen-decomposition returns, and S's diagonal are the same PCs eigenvalues as eigen-decomposition returns. – ttnphns Oct 7 '12 at 16:52
• Ah, symmetry of $U$ and $V$ is just what I missed. This explains many things in articles that confused me and proves assumptions I had about my 3 questions. Thanks, you saved me from doubts :) – ffriend Oct 7 '12 at 17:22
• @ttnphns If you have time and inclination, could you please convert your comment as an answer so that the OP could accept it and close this thread? – chl Jun 1 '13 at 21:25

• What are dimensions of $U$, $S$ and $V^T$?

Since $\Sigma$ is a M by M matrix, the three matrices $U$, $S$, $V^T$ wil be all M by M matrices. Because applying SVD on a N by M matrix, you will get $U_{N{\times}N}$, $S_{N{\times}M}$, and $V^T_{M{\times}M}$. You can verify that in matlab. When you truncate the singular values $S$ you also should remove the corresponding parts in $U$ and $V^T$.

• In $USV^T$ what exactly is considered as eigenvalues and which of them should I use as principal components?

PCA should be done by doing eigenvalue decomposition on the covariance matrix $\Sigma$, or done by applying SVD on $A$. The left singular vectors of $SVD(A)$ come from the eigen vectors of $AA^T$, and the right singular vectors of $SVD(A)$ are from the eigenvectors of $A^TA$. But you need to order them according to the eigenvalues from large to small, and make them orthonormal. $A^TA$ is called Gram Matrix and is related to the covariance matrix $\Sigma$. If the dimensional vectors in $A$ (M of them totally) are all centered already, Gram Matrix = N * Covariance matrix. Check Wikipedia and some tutorials of SVD and PCA.

• How can I project original observations $x_i$ onto new reduced space and vice versa?

If applying SVD on $A$ for PCA, it would be $u_i*S$; if applying eigen decomposition on covariance matrix $\Sigma$, and $V$ is eigenvectors of $\Sigma$, it is $x_i*V$.

• just want to add that PCA = eigen decomposition on the covariance matrix = centering the data matrix A + SVD on the centered A. In this way you will find the singular value of the centered A and the eigenvalue of \sigma are the same. – Wudanao Oct 14 '15 at 14:56