Singular value decomposition

$A=U\Sigma V^T$
where

• $A$ is $m\times n$
• $U$: An $m\times m$ Orthogonal matrix matrix whose columns are the left singular vectors of $A$.
• $\Sigma$: A diagonal $m\times n$ matrix containing the singular values of $A$ in descending order.
• $V^T$: The transpose of an $n\times n$ Orthogonal matrix where the columns are the right singular vectors of $A$.

Steps

1. calculate $A{A}^T$
2. calculate Eigenvalues of $A{A}^T$ by solving $det(A{A}^T-\lambda I)=0$, where $I$ is identify matrix
3. then $\Sigma$ is $\delta$ from those $\lambda$
4. calculate $V$ right singular vectors(should be unit vectors), for each $\lambda$, $(A^{T}A-\lambda I)v=0$
5. calculate $U$ left singular vectors(should be unit vectors), for each $\lambda$, $(A{A}^T-\lambda I)u=0$

3x2 example

ref https://www.geeksforgeeks.org/singular-value-decomposition-svd/

$$A=\left[\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right]$$ $$A{A}^T=\left[\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right]\left[\begin{array}{cc}1& 3\\ 2& 2\\ 3& 1\end{array}\right]=\left[\begin{array}{cc}1+4+9& 3+4+3\\ 3+4+3& 9+4+1\end{array}\right]=\left[\begin{array}{cc}14& 10\\ 10& 14\end{array}\right]$$ $$\det (A{A}^T-\lambda I)=\left[\begin{array}{cc}14-\lambda & 10\\ 10& 14-\lambda \end{array}\right]=(14-\lambda {)}^2-10^2=14^2-28\lambda +{\lambda }^2-10^2={\lambda }^2-28\lambda +96$$ $$(\lambda -24)(\lambda -4)=0$$

Then we can get some $\lambda$ Eigenvalues, ${\lambda }_1=24$ and ${\lambda }_2=4$ and Singular value ${\delta }_1=\sqrt{24}$ and ${\delta }_2=2$.
we can say

$$\Sigma =\left[\begin{array}{ccc}{\delta }_1& 0& 0\\ 0& {\delta }_2& 0\end{array}\right]=\left[\begin{array}{ccc}\sqrt{24}& 0& 0\\ 0& 2& 0\end{array}\right]$$

For each of them, calculate eigenvectors $(A^{T}A-\lambda I)v=0$
where

$$A^{T}A=\left[\begin{array}{ccc}10& 8& 6\\ 8& 8& 8\\ 6& 8& 10\end{array}\right]$$ $$(A^{T}A-24I)v_1=\left[\begin{array}{ccc}-14& 8& 6\\ 8& -16& 8\\ 6& 8& -14\end{array}\right]v_1=0$$

RREF it

$$\left[\begin{array}{ccc}1& 0& -1\\ 0& 1& -1\\ 0& 0& 0\end{array}\right]v_1=0$$

so $x-z=0$ and $y-z=0$

$$v_1=\left[\begin{array}{c}\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\end{array}\right]$$

so do ${\lambda }_2=4$

$$(A^{T}A-4I)v_2=\left[\begin{array}{ccc}6& 8& 6\\ 8& 4& 8\\ 6& 8& 6\end{array}\right]v_2=0$$

RREF it

$$\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 0\\ 0& 0& 0\end{array}\right]$$

so $x+z=0$ and $y=0$

$$v_2=\left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ 0\\ \frac{-1}{\sqrt{2}}\end{array}\right]$$

Then for $v_3$, since it must perpendicular to $v_1,v_2$, we can say $v_1^T{v}_3=0$ and $v_2^T{v}_3=0$ is true. Solve these two equations to get $v_3$.

$$v_3=\left[\begin{array}{c}\frac{1}{\sqrt{6}}\\ -\frac{2}{\sqrt{6}}\\ \frac{1}{\sqrt{6}}\end{array}\right]$$

Then

$$V=\left[\begin{array}{ccc}\ast v_1& \ast v_2& \ast v_3\end{array}\right]=\left[\begin{array}{ccc}\frac{1}{\sqrt{3}}& \frac{1}{\sqrt{2}}& \frac{1}{\sqrt{6}}\\ \frac{1}{\sqrt{3}}& 0& \frac{-2}{\sqrt{6}}\\ \frac{1}{\sqrt{3}}& \frac{-1}{\sqrt{2}}& \frac{1}{\sqrt{6}}\end{array}\right]$$

Lastly need to find $U$ with similar steps.

$$(A{A}^T-24I)u_1=\left[\begin{array}{cc}-10& 10\\ 10& -10\end{array}\right]u_1=0$$

RREF it

$$\left[\begin{array}{cc}-1& 1\\ 0& 0\end{array}\right]$$

so $u_1=\left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right]$

$$(A{A}^T-4I)u_2=\left[\begin{array}{cc}10& 10\\ 10& 10\end{array}\right]u_1=0$$

RREF it

$$\left[\begin{array}{cc}1& 1\\ 0& 0\end{array}\right]$$

so $u_2=\left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{-1}{\sqrt{2}}\end{array}\right]$
Then

$$U=\left[\begin{array}{cc}\ast u_1& \ast u_2\end{array}\right]=\left[\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& \frac{-1}{\sqrt{2}}\end{array}\right]$$

Therefore

$$A=U\Sigma V^T=\left[\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& \frac{-1}{\sqrt{2}}\end{array}\right]\left[\begin{array}{ccc}\sqrt{24}& 0& 0\\ 0& 2& 0\end{array}\right]{\left[\begin{array}{ccc}\frac{1}{\sqrt{3}}& \frac{1}{\sqrt{2}}& \frac{1}{\sqrt{6}}\\ \frac{1}{\sqrt{3}}& 0& \frac{-2}{\sqrt{6}}\\ \frac{1}{\sqrt{3}}& \frac{-1}{\sqrt{2}}& \frac{1}{\sqrt{6}}\end{array}\right]}^T$$

$\square$

Applications

Pseudo Inverse (Moore-Penrose Inverse)

$M=U\Sigma V^T$