Singular Value Decomposition and PCA

Problems with computing PCA using Eigenvalue Decomposition:

• Computing $X^{T}X$ already takes $O(n{d}^2)$ time.
• $X^{T}X$ is poorly conditioned → numerically inaccurate eigenvalues.

Singular Value Decomposition (SVD)

• Every $X\in {\mathbb{R}}^{n\times d}$ has a singular value decomposition.
• $X=U\Sigma V^T=UD{V}^T$
• Full SVD vs Compact SVD.
• Just different ranks.

$$\text{Full SVD : }{\left[\begin{array}{c}X\end{array}\right]}^{n\times d}={\left[\begin{array}{cccc}|& |& \dots & |\\ u_1& u_2& \dots & u_n\\ |& |& \dots & |\end{array}\right]}^{n\times n}{\left[\begin{array}{ccccc}{\sigma }_1& 0& 0& 0& 0\\ 0& {\sigma }_2& 0& 0& 0\\ 0& 0& \ddots & 0& 0\\ 0& 0& 0& {\sigma }_r& 0\\ 0& 0& 0& 0& 0\end{array}\right]}^{n\times d}{\left[\begin{array}{ccc}& v_1& \\ & v_2& \\ & ⋮& \\ & v_d& \end{array}\right]}^{d\times d}$$

For Full SVD, $U$ and $V$ are orthogonal matrices. (i.e have unit length and mutually orthogonal)

$U^{T}U=U{U}^T=I$ $U^{-1}=U^T$

$\sigma \ge 0$ are singular values of $X$. (By convention). $u^{\prime }s$ are known as the left singular vectors of $X$. $v^{\prime }s$ are known as the right singular vectors of $X$.

$$X=\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T$$

Claim: $v_i$ is an eigenvector of $X^{T}X$ with eigenvalues ${\sigma }^2$.

Proof:

$$\begin{array}{rl}{X}^{T}X& =V{\Sigma }^T{U}^{T}U\Sigma V^T\\ & =V{\Sigma }^2{V}^T\text{ same as eigendecomposition with }\Lambda ={\Sigma }^2\\ \text{Therefore eigenvalues of }{X}^{T}X\text{ is the same as }{\sigma }^2.& \end{array}$$

So, if we want to find the singular value of X,

• Compute $X^{T}X$
• Find eigenvalues of $X^{T}X$
• ${\sigma }_i=\sqrt{|{\lambda }_i|}$

IMPORTANT: Row i of $U\Sigma$ gives the principal coordinates of sample $x_i$

In practice, there are fast algorithm for finding singular values of any matrix $X$. Therefore, if we want the PCA of $X$, we compute the singular value of $X$, square it to make it eigenvalues of $X^{T}X$.Once we have eigenvalues, we can find eigenvectors, which are Principal Components of $X$. This is also the same as $v_1,v_2,\dots ,v_r$ (rows of the matrix $V^T$) from SVD.

---

Compact SVD

$$X^{n\times d}=U^{n\times r}{\Sigma }^{r\times r}{V^T}^{r\times d}$$

Note:

• In Compact SVD, $U^{T}U=I\ne U{U}^T$.
• Similarly, $V^{T}V=I\ne V{V}^T$.
• $\Sigma$ is always full rank in compact SVD.

---

• Claim: We can find the k largest singular values and corresponding vectors in $O(ndk)$ time.
• There are also approximate randomized algorithms that work really well for very large dataset.

---

PsuedoInverse