Tag Archives: singular value decomposition

Computing PCA with SVD

PCA is a great tool for performing dimensionality reduction. Two reason you might want to use SVD to compute PCA:

  • SVD is more numerically stable if the columns are close to collinear. I have seen this happen in text data, when certain terms almost always appear together.
  • Spark's PCA implementation currently doesn't support very wide matrices. The SVD implementation does however.

Singular Value Decomposition (SVD)

Below we briefly recap Singular Value Decomposition (SVD).

Let \mathbf{A} be a m \times n matrix, the singular value decomposition gives

\mathbf{A} = \mathbf{U}_{m\times m}\mathbf{\Sigma}_{m\times n}\mathbf{V}^\top_{n\times n}

\mathbf{U} is an orthonormal matrix and is the eigenvectors of \mathbf{A}\mathbf{A}^\top.

\mathbf{V} is an orthonormal matrix and is the eigenvectors of \mathbf{A}^\top\mathbf{A}.

\mathbf{\Sigma} is a diagonal matrix and contains the square-roots of the eigenvalues of\mathbf{A}\mathbf{A}^\top and  \mathbf{A}^\top\mathbf{A} e.g.

\mathbf{\Sigma}=\begin{pmatrix}\sqrt{\lambda_1}&0&\cdots& 0\\0 &\sqrt{\lambda_2} & \cdots &0\\\vdots & \vdots & \ddots & \vdots \\0&0& \cdots &\sqrt{\lambda_k}\end{pmatrix}

Remember, as \mathbf{U} is an orthonormal matrix \mathbf{U}^\top=\mathbf{U}^{-1}

Computing PCA

Start with the standard steps of PCA:

  1. Mean centre the matrix \mathbf{A}
  2. Optionally scale each column by their standard deviation. You may want to do this if the variables are measured on different scales.

We noted in the previous section that \mathbf{V} is the eigenvectors of \mathbf{A}^\top\mathbf{A} (the covariance matrix). Thus the principal component decomposition is

\begin{equation} \begin{split}\mathbf{T} & = \mathbf{A}\mathbf{V}\\ & =\mathbf{U}\mathbf{\Sigma}\mathbf{V}^\top\mathbf{V} \\ & =\mathbf{U}\mathbf{\Sigma}\end{split}\end{equation}

To reduce the dimensionality of \mathbf{A}, select the k largest singular values (k \le n), select the first k columns from \mathbf{U} and the k \times k upper-left part of \mathbf{\Sigma}. The reduced dimensionality is given by

\mathbf{T}_k =\mathbf{U}_k\mathbf{\Sigma}_k