Home Features Data Analytics Data Analytics: Summaries on Strang's Linear Algebra - Singular Value Decomposition
Data Analytics: Summaries on Strang's Linear Algebra - Singular Value Decomposition PDF Print E-mail
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
 

joomla 1.5 stats