7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please excuse if it sounds rude, but... where are you stuck after reading thousands of articles on PCA? $\endgroup$ – ttnphns Oct 7 '12 at 15:40
  • 1
    $\begingroup$ @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$ $\endgroup$ – ffriend Oct 7 '12 at 15:54
  • 2
    $\begingroup$ 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. $\endgroup$ – ttnphns Oct 7 '12 at 16:52
  • 1
    $\begingroup$ 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 :) $\endgroup$ – ffriend Oct 7 '12 at 17:22
  • 1
    $\begingroup$ @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? $\endgroup$ – chl Jun 1 '13 at 21:25
8
$\begingroup$
  • 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$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Wudanao Oct 14 '15 at 14:56

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.