### Key Concepts

 Data Analytics: Summaries on Strang's Linear Algebra - Singular Value Decomposition
Written by FemiByte
Monday, 01 April 2013 02:48

## Singular Value Decomposition

Singular Value Decomposition is the culmination of concepts in the course. It involves a factorization into orthogonal x diagonal x orthogonal matrices We look for the case where matrix A takes an orthogonal basis of vectors from the row space into an orthogonal basis of vectors in the column space.
On SVD the goal is to find

1. orthonormal vectors $v_1, v_2, \cdots v_n$ in the row space $R^n$
2. orthonormal vectors $uv_1, uv_2, \cdots u_m$ in the column space $R^m$
3. multiplicands $\sigma_1 > 0, \sigma_2>0, \cdots \sigma_n > 0$ s.t $Av_1=\sigma_1 u_1 \text{ }Av_2=\sigma_2 u_2 \cdots Av_r=\sigma_r u_r$
In this case $A$ is diagonalized

The singular vectors $v_1,\cdots v_r$ are in the row space of $A$ and are the eigenvectors of $A^TA$ and the outputs $u_1,\cdots u_r$ are in the column space of $A$ and are the eigenvectors of $AA^T$. The singular values $\sigma_1,\cdots \sigma_r$ are all +ve. We have that $A \left[ \begin{array}{ccc} \\v_1&&\cdots&&v_r\\ \end{array}\right]= \left[ \begin{array}{ccc} \\u_1&&\cdots&&u_r\\ \end{array}\right] \left[ \begin{array}{ccc}\sigma_1&& && \\ &&.&& \\ && &&\sigma_r\end{array}\right]$ The above relationship is the heart if the SVD and can be expressed as $AV=U\Sigma$. We also need $n-r$ more $v$'s and $m-r$ more $u$'s, from the nullspace $N(A)$ and the left nullspace $N(A^T)$. This makes $V$ now a square orthogonal matrix and the core relationship for SVD becomes: $A=U \Sigma V^T = u_1 \sigma_1 v_1^T + \cdots + u_r \sigma_r v_r^T$

### The Bases and the SVD

In the 2x2 case we diagonalize the crucial symmetric matrix $A^TA$, whose eigenvalues are $\sigma_1^2$ and $\sigma_2^2$:
Eigenvalues $\sigma_1^2 \sigma_2^2$, Eigenvectors $v_1, v_2$ $A^TA = V \left[\begin{array}{cc}\sigma_1^2&&0\\0&&\sigma_2^2\end{array} \right] V^T$ Rule:
Compute the eigenvectors $v$ and eigenvalues $\sigma^2$ of $A^TA$. Then each $u=Av/\sigma$. The matrices $U$ and $V$ contain orthornormal bases for all 4 subspaces:

• first $r$ columns of $V$: row space of $A$
• first $n-r$ columns of $V$: nullspace of $A$
• first $r$ columns of $U$: column space of $A$
• first $m-r$ columns of $U$: nullspace of $A^T$

## Key Ideas

1. The SVD factors $A$ into $U\Sigma V^T$, with $r$ singular values $\sigma_1 \geq \cdots \sigma_r > 0$.
2. The numbers $\sigma_1 ^2 \cdots \sigma_r ^2$ are the nonzero eigenvalues of $AA^T$ and $A^TA$.
3. The orthonormal columns of $U$ and $V$ are eigenvectors of $AA^T$ and $A^TA$.
4. Those columns hold orthonormal bases for the 4 fundamental subspaces of $A$.
5. Those bases diagonalize the matrix: $Av_i=\sigma_i u_i$ for $i \leq r$. This is $AV=U\Sigma$
Last Updated on Monday, 01 April 2013 02:52