Singular Value Decomposition

What is SVD? §

SVD is a matrix factorization method which decomposes a matrix into three other matrices.

$$A=U\Sigma V^{\ast }$$

• U: An $m\times m$ orthogonal matrix whose columns are called left-singular vectors of $A$.
• Σ: An $m\times n$ diagonal matrix (though not necessarily square), whose non-negative diagonal elements are known as singular values of $A$. The singular values are usually arranged in descending order along the diagonal.
• V*: The conjugate transpose of an n×n orthogonal matrix whose columns are called right-singular vectors of $A$.

Procedure Generalized §

1. Transpose the matrix and multiply: $B^{T}B$
2. Compute eigenvalues: $det(B^{T}B-\lambda I)$
3. Substitute eigenvalues to compute eigenvectors
4. Normalize each eigenvector and use the normalized columns to construct $V$
5. Construct $\Sigma$ from the square-root of the eigenvalues along the diagonals.
6. Construct U from the process of $U_1=\frac{1}{\sigma }\times A\times V_1$

Examples from Textbook §

(David C. Lay, Steven R. Lay, Judi J. McDonald-Linear Algebra and Its Applications-Pearson Education (c2016))

Example

Construct a singular value decomposition of

$$A=\left[\begin{array}{cc}3& -3\\ 0& 0\\ 1& 1\end{array}\right]$$ $$A^{T}A=\left[\begin{array}{ccc}3& 0& 1\\ -3& 0& 1\end{array}\right]\left[\begin{array}{cc}3& -3\\ 0& 0\\ 1& 1\end{array}\right]$$ $$=\left[\begin{array}{cc}10& -8\\ -8& 10\end{array}\right]$$ $$=\left[\begin{array}{cc}10-\lambda & -8\\ -8& 10-\lambda \end{array}\right]$$

$(10-\lambda )(10-\lambda )-64$

$${\lambda }^2-20\lambda +36$$

$(\lambda -18)(\lambda -2)$ $\lambda =18,\lambda =2$

$$\lambda =18:\left[\begin{array}{cc}-8& -8\\ -8& -8\end{array}\right]\to \left[\begin{array}{cc}1& 1\\ 1& 1\end{array}\right]\to \left[\begin{array}{cc}1& 1\\ 0& 0\end{array}\right]$$

$x_2$ is free

$x_1=-x_2$

$$v_1=\left[\begin{array}{c}1\\ -1\end{array}\right]$$

Normalize:

$$v_1=\left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right]$$ $$\lambda =2:\left[\begin{array}{cc}8& -8\\ -8& 8\end{array}\right]\to \left[\begin{array}{cc}1& -1\\ -1& 1\end{array}\right]\to \left[\begin{array}{cc}1& -1\\ 0& 0\end{array}\right]$$

$x_2$ is free

$x_1=x_2$

$$v_2=\left[\begin{array}{c}1\\ 1\end{array}\right]$$

Normalize:

$$\left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right]$$

Construct $\Sigma$:

$$\Sigma =\left[\begin{array}{cc}\sqrt{2}& 0\\ 0& \sqrt{18}\end{array}\right]$$

Construct V:

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

Compute $u_1$: $u_1=\frac{1}{\sigma }\times A\times V_1$

$$u_1=\frac{1}{\sqrt{2}}\times \left[\begin{array}{cc}3& -3\\ 0& 0\\ 1& 1\end{array}\right]\times \left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right]$$ $$u_1=\frac{1}{\sqrt{2}}\left[\begin{array}{c}3(\frac{1}{\sqrt{2}})+-3(\frac{1}{\sqrt{2}})=0\\ 0\\ \frac{1}{\sqrt{2}}+\frac{1}{\sqrt{2}}=\frac{2}{\sqrt{2}}\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ \frac{2}{\sqrt{2}\ast \sqrt{2}}=1\end{array}\right]$$ $$u_1=\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]$$ $$u_2=\frac{1}{\sqrt{18}}\times \left[\begin{array}{cc}3& -3\\ 0& 0\\ 1& 1\end{array}\right]\times \left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right]$$ $$u_2=\frac{1}{\sqrt{18}}\times \left[\begin{array}{c}3(\frac{1}{\sqrt{2}})+-3(-\frac{1}{\sqrt{2}})=\frac{9}{\sqrt{2}}\\ 0\\ 0\end{array}\right]$$ $$u_2=\left[\begin{array}{c}\frac{9}{\sqrt{18}\times \sqrt{2}=\sqrt{36}}\\ 0\\ 0\end{array}\right]$$ $$U=\left[\begin{array}{cc}0& \frac{3}{2}\\ 0& 0\\ 1& 0\end{array}\right]$$ $$V=\left[\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right]$$ $$\Sigma =\left[\begin{array}{cc}\sqrt{2}& 0\\ 0& \sqrt{18}\end{array}\right]$$

#evergreen