how SVD is calculated in reality

Question

let us suppose that we have following matrix $ A= \left[ {\begin{array}{cc} 4 & 0 \\ 3 & -5 \\ \end{array} } \right] $

for calculation of SVD,first i have calculated $A'*A$ which is equal to

$ A'*A= \left[ {\begin{array}{cc} 25 & -15 \\ -15 & 25 \\ \end{array} } \right] $

eigenvalues of this matrix is equal to $40$ and $10$, eigenvector of following matrix

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

i got this matrix after subtraction of $40$ from diagonal elements, eigenvector is equal to
\begin{bmatrix}-1 \\ 1\\ \end{bmatrix}

after inserting of eigenvalues of $10$, i got following matrix

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

eigenvector of this matrix is equal to

\begin{bmatrix}1 \\ 1\\ \end{bmatrix}

so normalization of these vectors and putting in one matrix $V$ will have the following form

$ \left[ {\begin{array}{cc} -1/\sqrt{2} & 1/\sqrt{2} \\ 1/\sqrt{2} & 1/\sqrt{2} \\ \end{array} } \right] $

now i know that

$A*V=U*E$ where $E$ is equal to

$ \left[ {\begin{array}{cc} \sqrt{40} & 0 \\ 0 & \sqrt{10} \\ \end{array} } \right] $

we know that

$A*v1=u1*\sigma$

let us try to multiply

$ \left[ {\begin{array}{cc} 4 & 0 \\ 3 & -5 \\ \end{array} } \right] $ by

\begin{bmatrix}-1/\sqrt{2} \\ 1/\sqrt{2} \\ \end{bmatrix}

i got the following result

\begin{bmatrix}-4/\sqrt{2} \\ -8/\sqrt{2} \\ \end{bmatrix}

but i can't get equation for $\sigma$ and $u$ please help me

Answer 1

You did everything correctly. You already found $\sigma_1,\sigma_2$ - they are the square roots of the eigenvalues of $A^TA$ so $\sigma_1 = \sqrt{40},\sigma_2 = \sqrt{10}$. After you found $V$ with columns $v_1,v_2$, you must have

$$ Av_1 = \sigma_1 u_1, Av_2 = \sigma_2 u_2 $$

so $u_1$ is just $\frac{Av_1}{\sigma_1}$ and $u_2 = \frac{Av_2}{\sigma_2}$. In your case,

$$ u_1 = \begin{pmatrix} -\frac{4}{\sqrt{2}} \\ -\frac{8}{\sqrt{2}} \end{pmatrix} \frac{1}{\sqrt{40}} = \begin{pmatrix} -\frac{1}{\sqrt{5}} \\ -\frac{2}{\sqrt{5}} \end{pmatrix}, \\ u_2 = \begin{pmatrix} \frac{4}{\sqrt{2}} \\ -\frac{2}{\sqrt{2}} \end{pmatrix} \frac{1}{\sqrt{10}} = \begin{pmatrix} \frac{2}{\sqrt{5}} \\ -\frac{1}{\sqrt{5}} \end{pmatrix} $$

and indeed

$$ \begin{pmatrix} -\frac{1}{\sqrt{5}} & -\frac{2}{\sqrt{5}} \\ \frac{2}{\sqrt{5}} & -\frac{1}{\sqrt{5}} \end{pmatrix} \begin{pmatrix} 4 & 0 \\ 3 & -5\end{pmatrix} \begin{pmatrix} -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{pmatrix} = \begin{pmatrix} \sqrt{40} & 0 \\ 0 & \sqrt{10} \end{pmatrix}. $$

Answer 2

Big picture

Every matrix $\mathbf{A}\in\mathbb{C}^{m\times n}_{\rho}$ has a singular value decomposition $$ \begin{align} \mathbf{A} &= \mathbf{U} \, \Sigma \, \mathbf{V}^{*} \\ % &= % U \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}}} & \color{red}{\mathbf{U}_{\mathcal{N}}} \end{array} \right] % Sigma \left[ \begin{array}{cccc|cc} \sigma_{1} & 0 & \dots & & & \dots & 0 \\ 0 & \sigma_{2} \\ \vdots && \ddots \\ & & & \sigma_{\rho} \\\hline & & & & 0 & \\ \vdots &&&&&\ddots \\ 0 & & & & & & 0 \\ \end{array} \right] % V \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{V}_{\mathcal{N}}}^{*} \end{array} \right] \\ % & = % U \left[ \begin{array}{cccccccc} \color{blue}{u_{1}} & \dots & \color{blue}{u_{\rho}} & \color{red}{u_{\rho+1}} & \dots & \color{red}{u_{n}} \end{array} \right] % Sigma \left[ \begin{array}{cc} \mathbf{S}_{\rho\times \rho} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right] % V \left[ \begin{array}{c} \color{blue}{v_{1}^{*}} \\ \vdots \\ \color{blue}{v_{\rho}^{*}} \\ \color{red}{v_{\rho+1}^{*}} \\ \vdots \\ \color{red}{v_{n}^{*}} \end{array} \right] % \end{align} $$ The four fundamental subspaces for $\mathbf{A}$ are resolved into an orthonormal basis: $$ \begin{align} % R A \color{blue}{\mathcal{R} \left( \mathbf{A} \right)} &= \text{span} \left\{ \color{blue}{u_{1}}, \dots , \color{blue}{u_{\rho}} \right\} \\ % R A* \color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} &= \text{span} \left\{ \color{blue}{v_{1}}, \dots , \color{blue}{v_{\rho}} \right\} \\ % N A* \color{red}{\mathcal{N} \left( \mathbf{A}^{*} \right)} &= \text{span} \left\{ \color{red}{u_{\rho+1}}, \dots , \color{red}{u_{m}} \right\} \\ % N A \color{red}{\mathcal{N} \left( \mathbf{A} \right)} &= \text{span} \left\{ \color{red}{v_{\rho+1}}, \dots , \color{red}{v_{n}} \right\} \\ % \end{align} $$ Compute the SVD involves resolving the $\color{blue}{range} spaces$:

1. Resolve the domain $\mathbb{C}^{n}$ by finding eigenvectors of $\mathbf{A}^{*}\mathbf{A}$. Outputs: matrix of singular values $\mathbf{S}$, $\color{blue}{\mathbf{V}_{\mathcal{R}}}$.
2. Resolve the domain $\mathbb{C}^{n}$ by computing $\color{blue}{\mathbf{U}_{\mathcal{R}}}$ using $\mathbf{S}$ and $\color{blue}{\mathbf{V}_{\mathcal{R}}}$

---

1. Resolve $\ \color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)}$

Step 1:

Compute product matrix $$ % \begin{align} % \mathbf{W} = \mathbf{A}^{T}\mathbf{A} = % At \left[ \begin{array}{cc} 4 & 0 \\ 3 & 5 \\ \end{array} \right] % A \left[ \begin{array}{cc} 4 & 3 \\ 0 & 5 \\ \end{array} \right] % = % \left[ \begin{array}{cc} 25 & 15 \\ 15 & 25 \\ \end{array} \right] % \end{align} % $$

Step 2:

Compute eigenvalue spectrum $\lambda \left(\mathbf{W}\right)$

$$ \det \mathbf{W} = 400, \qquad \text{trace } \mathbf{W} = 50 $$ The characteristic polynomial is $$ p(\lambda) = \lambda^{2} - \lambda \text{ trace } \mathbf{W} + \det \mathbf{W} = \lambda ^2-50 \lambda +400 = \left( \lambda - 40 \right) \left( \lambda - 10 \right) $$ The roots of the $p(\lambda)$ are the eigenvalues of $\mathbf{W}$: $$ \lambda \left(\mathbf{W}\right) = \left\{ 40, 10 \right\} $$

Step 3:

Compute singular value spectrum $\sigma$

To obtain the singular values: form $\tilde{\lambda}$, a list arranged in decreasing order with $0$ values culled: $$ \sigma = \sqrt{\tilde{\lambda}} = \left\{ 2 \sqrt{10},\sqrt{10} \right\} $$ The singular values are the diagonal entries of the $\mathbf{S}$: $$ \boxed{ \mathbf{S} = \sqrt{10}\left[ \begin{array}{cc} 2 & 0 \\ 0 & 1 \\ \end{array} \right] } $$

Step 4:

Compute eigenvectors of $\mathbf{W}$

Fundamental tool: eigenvalue equation $$ \mathbf{W} v_{k} = \lambda_{k} v_{k}, \qquad k = 1, 2 $$

$k=1$: $$ % \begin{align} % \mathbf{W} v_{1} &= \lambda_{1} v_{1} \\ % \left[ \begin{array}{cc} 25 & 15 \\ 15 & 25 \\ \end{array} \right] % \left[ \begin{array}{c} x \\ y \\ \end{array} \right] % &= % 8 % \left[ \begin{array}{c} x \\ y \\ \end{array} \right] \\[3pt] % % % \left[ \begin{array}{c} 25 x + 15 y \\ 15 x + 25 y \\ \end{array} \right] &= \left[ \begin{array}{c} 40x \\ 40y \\ \end{array} \right]\\[3pt] % % % \left[ \begin{array}{c} x \\ y \\ \end{array} \right] &= \left[ \begin{array}{c} 1 \\ 1 \\ \end{array} \right] % \end{align} % $$ The normalized vector is the first column vector in $\color{blue}{\mathbf{V}_{\mathcal{R}}}$. $$ \hat{v}_{1} = \frac{1}{\sqrt{2}} \left[ \begin{array}{r} 1 \\ 1 \\ \end{array} \right] $$

$k=2$: $$ % \begin{align} % \mathbf{W} v_{2} &= \lambda_{2} v_{2} \\ % \left[ \begin{array}{cc} 25 & 15 \\ 15 & 25 \\ \end{array} \right] % \left[ \begin{array}{c} x \\ y \\ \end{array} \right] % &= % 10 % \left[ \begin{array}{c} x \\ y \\ \end{array} \right] \\[3pt] % % % \left[ \begin{array}{c} 25 x + 15 y \\ 15 x + 25 y \\ \end{array} \right] &= \left[ \begin{array}{c} 10x \\ 10y \\ \end{array} \right]\\[3pt] % % % \left[ \begin{array}{c} x \\ y \\ \end{array} \right] &= \left[ \begin{array}{c} -1 \\ 1 \\ \end{array} \right] % \end{align} % $$ The normalized vector is the second column vector in $\color{blue}{\mathbf{V}_{\mathcal{R}}}$. $$ \hat{v}_{2} = \frac{1}{\sqrt{2}} \left[ \begin{array}{r} -1 \\ 1 \\ \end{array} \right] $$ Assemble: $$ \boxed{ \color{blue}{\mathbf{V}_{\mathcal{R}}} = \frac{1}{\sqrt{2}} % \left[ \begin{array}{cr} 1 & -1 \\ 1 & 1 \\ \end{array} \right] } $$

2. Resolve $\ \color{blue}{\mathcal{R} \left( \mathbf{A} \right)}$

Rearrange the definition of the SVD (1) to recover $$ \color{blue}{\mathbf{U}_{\mathcal{R}}} = \mathbf{A} \, \color{blue}{\mathbf{V}_{\mathcal{R}}} \, \mathbf{S}^{-1} $$

Compute directly: $$ \begin{align} \color{blue}{\mathbf{U}_{\mathcal{R}}} = \mathbf{A} \color{blue}{\mathbf{V}_{\mathcal{R}}} \mathbf{S}^{-1} % &= \left[ \begin{array}{cc} 4 & 0 \\ 3 & 5 \\ \end{array} \right] % \frac{1}{\sqrt{2}} \left[ \begin{array}{cr} 1 & -1 \\ 1 & 1 \\ \end{array} \right] % Sinv \left[ \begin{array}{cc} \frac{1}{2 \sqrt{10}} & 0 \\ 0 & \frac{1}{\sqrt{10}} \\ \end{array} \right] % \end{align} % $$ At last, $$ \boxed{ \color{blue}{\mathbf{U}_{\mathcal{R}}} = \frac{1}{\sqrt{5}} \left[ \begin{array}{cr} 1 & -2 \\ 2 & 1 \\ \end{array} \right] } $$

---

Final answer

$$ \mathbf{A} = \color{blue}{\mathbf{U}_{\mathcal{R}}} \mathbf{S} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} = % \frac{1}{\sqrt{5}} \left[ \begin{array}{cr} 1 & -2 \\ 2 & 1 \\ \end{array} \right] % \sqrt{10} \left[ \begin{array}{cc} 20 & 0 \\ 0 & 10 \\ \end{array} \right] % S % \frac{1}{\sqrt{2}} \left[ \begin{array}{cr} 1 & -1 \\ 1 & 1 \\ \end{array} \right] % = \left[ \begin{array}{cc} 4 & 0 \\ 3 & 5 \\ \end{array} \right] % $$