2.12d.1 Outer Product SVD

Outer Product Form of the SVD

A matrix $A\in {\mathbb{R}}^{m\times n}$ with rank $r\le \min \{m,n\}$ can be decomposed using the outer product form of the SVD as
$A={\sum }_{i=1}^r{\sigma }_i{\vec{u}}_i{\vec{v}}_i^T$
where $\{{\vec{u}}_1,{\vec{u}}_2,\dots ,{\vec{u}}_r\}\subseteq {\mathbb{R}}^m$ and $\{{\vec{v}}_1,{\vec{v}}_2,\dots ,{\vec{v}}_r\}\subseteq {\mathbb{R}}^n$ are sets of orthonormal vectors known respectively as the left singular vectors and right singular vectors of $A$, whereas ${\sigma }_1>\cdots >{\sigma }_r>0$ are positive ordered scalars known as the singular values of $A$.

Intuition

Essentially, we can algorithmically compute the SVD as follows:

1. Find and sort $({\lambda }_1,{\vec{v}}_1),...,({\lambda }_r,{\vec{v}}_r)$, the orthogonal eigenvalue-eigenvector pairs of $A^{T}A$.
2. For each pair, find:
   1. ${\sigma }_i=\sqrt{{\lambda }_i}$
   2. ${\vec{u}}_i=\frac{1}{{\sigma }_i}A{\vec{v}}_i$
      We can prove the second step using $\frac{1}{{\sigma }_k}A{\vec{v}}_k=\frac{1}{{\sigma }_k}{\sum }_{i=1}^r{\sigma }_i{\vec{u}}_i{\vec{v}}_i^T{\vec{v}}_k$. Then ${\vec{v}}_i^T{\vec{v}}_k=⟨{\vec{v}}_k,{\vec{v}}_i⟩$ will be 0 for $i\ne k$ and 1 for $i=k$ since the right singular vectors are orthonormal. As such, $\frac{1}{{\sigma }_k}{\sum }_{i=1}^r{\sigma }_i{\vec{u}}_i{\vec{v}}_i^T{\vec{v}}_k={\vec{u}}_k$.

Alternatively, we can find and sort $({\lambda }_1,{\vec{u}}_1),...,({\lambda }_r,{\vec{u}}_r)$, which are the eigenvalue-eigenvector pairs of $A{A}^T$. Then, ${\vec{v}}_i=\frac{1}{{\sigma }_i}{A}^T{\vec{u}}_i$ or ${\vec{v}}_i^T=\frac{1}{{\text{upsigma}}_i}A{\vec{u}}_i^T$.

This SVD form is messy, albeit the most efficient to compute since it decomposes $A$ into $r$ rank-1 matrices.

Properties

$\{{\vec{u}}_1,\dots ,{\vec{u}}_r\}$ is an orthonormal basis of $\mathrm{Col}(A)$

Since $\{{\vec{u}}_1,\dots ,{\vec{u}}_r\}$, we only need to prove that it spans $\mathrm{Col}(A)$:

$$\begin{array}{rl}A\vec{x}& =\left(\sum _{i=1}^r{\sigma }_i{\vec{u}}_i{\vec{v}}_i^T\right)\vec{x}\\ & =\sum _{i=1}^r{\sigma }_i{\vec{u}}_i\left({\vec{v}}_i^T\vec{x}\right)\\ & =\sum _{i=1}^r{\sigma }_i⟨\vec{x},{\vec{v}}_i⟩{\vec{u}}_i.\end{array}$$

The result is a linear combination of ${\vec{u}}_i$. Therefore, $\mathrm{Col}(A)\subseteq \mathrm{Span}({\vec{u}}_1,\dots ,{\vec{u}}_r)$. Since both $\mathrm{Col}(A)$ and $\mathrm{Span}({\vec{u}}_1,\dots ,{\vec{u}}_r)$ have the same dimension $r$, they are equal.

$\{{\vec{v}}_1,\dots ,{\vec{v}}_r\}$ is an orthonormal basis of $\mathrm{Row}(A)=\mathrm{Col}(A^T)$

Since $A^T={\sum }_{i=1}^r{\sigma }_i{\vec{v}}_i{\vec{u}}_i^T$, we can proceed using the same reasoning as above.

$({\sigma }_i^2,{\vec{u}}_i)$ is an eigenvalue-eigenvector pair of $A{A}^T$

For any ${\vec{u}}_k\in \{{\vec{u}}_1,\dots ,{\vec{u}}_r\}$:

$$\begin{array}{rl}A{A}^T{\vec{u}}_k& =\left(\sum _{i=1}^r{\sigma }_i{\vec{u}}_i{\vec{v}}_i^T\right)\left(\sum _{j=1}^r{\sigma }_j{\vec{v}}_j{\vec{u}}_j^T\right){\vec{u}}_k\\ & =\sum _{i=1}^r\sum _{j=1}^r{\sigma }_i{\sigma }_j{\vec{u}}_i{\vec{v}}_i^T{\vec{v}}_j{\vec{u}}_j^T{\vec{u}}_k\\ & =\sum _{i=1}^r\sum _{j=1}^r{\sigma }_i{\sigma }_j{\vec{u}}_i⟨{\vec{v}}_j,{\vec{v}}_i⟩⟨{\vec{u}}_k,{\vec{u}}_j⟩\\ & ={\sigma }_k^2{\vec{u}}_k.\end{array}$$

We obtain this from the fact that $⟨{\vec{v}}_j,{\vec{v}}_i⟩=\{\begin{array}{ll}0& i\ne j\\ 1& i=j\end{array}$ and $⟨{\vec{u}}_k,{\vec{u}}_j⟩=\{\begin{array}{ll}0& k\ne j\\ 1& k=j\end{array}$ since all elements of both sets are orthonormal to each other by set orthonormality. Therefore the equation is non-zero if and only if $k=i=j$.

$({\sigma }_i^2,{\vec{v}}_i)$ is an eigenvalue-eigenvector pair of $A^{T}A$

Proceed by same reasoning as above.

$A{\vec{v}}_i={\sigma }_i{\vec{u}}_i⟺A^T{\vec{u}}_i={\sigma }_i{\vec{v}}_i$

$$\begin{array}{rl}A{\vec{v}}_k& =\sum _{i=1}^r{\sigma }_i{\vec{u}}_i{\vec{v}}_i^T{\vec{v}}_k\\ & =\sum _{i=1}^r{\sigma }_i⟨{\vec{v}}_k,{\vec{v}}_i⟩{\vec{u}}_i\\ & ={\sigma }_i{\vec{u}}_i\end{array}$$

Since due to orthonormality the equation is non-zero only when $k=i$.

Application

TODO: Miki’s Movies Data