Proof of SVD

We have

A∈Rm×nA \in \mathbb{R}^{m \times n}

Let (λ1,v⃗1),(λ2,v⃗2),…,(λr,v⃗r),(∀i∈[1,r],λi≠0)(\lambda_1,\vec{v}_1), (\lambda_2,\vec{v}_2), \dots, (\lambda_r,\vec{v}_r), (\forall i \in [1,r], \lambda_i \ne 0) be non-zero eigenvalue-vector pairs of A⊤AA^{\top}A (and that λ1≥λ2≥⋯≥λr\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_r)

And let (λr+1,v⃗r+1),…,(λn,v⃗n)(\lambda_{r+1},\vec{v}_{r+1}),\dots,(\lambda_n,\vec{v}_n) be eigenvalue-vector pairs of ATAA^{T}A that its eigenvalue is 00.

Define:

V=[v⃗1v⃗2⋯v⃗n]V = \begin{bmatrix} \vec{v}_1 &\vec{v}_2 &\cdots &\vec{v}_n \end{bmatrix}
σi=λi\sigma_i = \sqrt{\lambda_i}
∀i≤r,u⃗i:Av⃗i=σiu⃗i\forall i \le r, \vec{u}_i: A\vec{v}_i=\sigma_i\vec{u}_i

Prove:

u⃗i are orthonormal∀i≠j,<u⃗i,u⃗j>=0∀i,∣∣u⃗i∣∣2=1\vec{u}_i \text{ are orthonormal} \\ \forall i \ne j, <\vec{u}_i,\vec{u}_j> = 0 \\ \forall i, ||\vec{u}_i||_2 = 1
<u⃗i,u⃗j>=u⃗i⊤u⃗j=(Av⃗i)⊤σiAv⃗jσj=1σiσjv⃗i⊤A⊤Av⃗j=1σiσjv⃗iλjv⃗j=σjσiσj0undefinedeigenvectors of a matrix with different eigenvalues=0\begin{split} <\vec{u}_i,\vec{u}_j> &= \vec{u}_i^{\top}\vec{u}_j \\ &=\frac{(A \vec{v}_i)^{\top}}{\sigma_i} \frac{A\vec{v}_j}{\sigma_j} \\ &=\frac{1}{\sigma_i \sigma_j}\vec{v}_i^{\top}A^{\top}A\vec{v}_j \\ &=\frac{1}{\sigma_i \sigma_j}\vec{v}_i \lambda_j \vec{v}_j \\ &=\frac{\sigma_j}{\sigma_i \sigma_j} \underbrace{0}_{\text{eigenvectors of a matrix with different eigenvalues}} \\ &=0 \end{split}
∣∣u⃗i∣∣22=(Av⃗i)⊤σi(Av⃗i)σi=1λiv⃗i⊤A⊤Av⃗i=1λiv⃗i⊤λiv⃗i=∣∣v⃗i∣∣22=1\begin{split} ||\vec{u}_i||_2^2 &= \frac{(A\vec{v}_i)^{\top}}{\sigma_i}\frac{(A\vec{v}_i)}{\sigma_i} \\ &=\frac{1}{\lambda_i}\vec{v}_i^{\top}A^{\top}A\vec{v}_i \\ &=\frac{1}{\lambda_i}\vec{v}_i^{\top}\lambda_i\vec{v}_i \\ &=||\vec{v}_i||_2^2 = 1 \end{split}

We will now proceed to define more u⃗i,∀i∈(r,n]\vec{u}_i, \forall i \in (r, n]

We will use gram-schmidt for computing those extra u⃗i\vec{u}_is.

Now we construct VV that

V=[VR=[v⃗1⋯v⃗r]Vnull=[v⃗r+1⋯v⃗n]]V = \begin{bmatrix} V_R = \begin{bmatrix} \vec{v}_1 &\cdots &\vec{v}_r \end{bmatrix} &V_{null}=\begin{bmatrix} \vec{v}_{r+1} &\cdots &\vec{v}_n \end{bmatrix} \end{bmatrix}

And now (because σiu⃗i=Av⃗i)\sigma_i\vec{u}_i = A\vec{v}_i):

AVR=[σ100⋯00σ20⋯000σ3⋯0⋮⋮⋮⋱⋮000⋯σr][u⃗1u⃗2⋯u⃗r]AV_R = \begin{bmatrix} \sigma_1 &0 &0 &\cdots &0 \\ 0 &\sigma_2 &0 &\cdots &0 \\ 0 &0 &\sigma_3 &\cdots &0 \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ 0 &0 &0 &\cdots &\sigma_r \end{bmatrix}\begin{bmatrix} \vec{u}_1 &\vec{u}_2 &\cdots &\vec{u}_r \end{bmatrix}

From the same reasoning

AV=ΣU=UΣAV=\Sigma U = U\Sigma

(proof is left as an exercise)

And now we can apply V−1V^{-1} to the right side of equation

V=UΣV⊤V = U\Sigma V^{\top}
🔥
Now think about the unit circle… This is helpful because it helps us know what every single vector is going to transform into

Note:

∀i≠j,v⃗i⊤v⃗j=0∀i≠j,(Av⃗i)⊤(Av⃗j)=0(proved in the u⃗ orthonormal proof)\forall i \ne j, \vec{v}_i^{\top}\vec{v}_j = 0 \\ \forall i \ne j, (A\vec{v}_i)^{\top}(A\vec{v}_j)=0 \quad (\text{proved in the $\vec{u}$ orthonormal proof)}