---
disqus: ierosodin
---

# Singular value Decomposition (SVD)

> Organization contact [name= [ierosodin]([e-mail])]
###### tags: `Linear Algebra` `學習筆記`

* 對於一個 Matrix，不一定存在 full set of eigenvalue，而其 eigenvectors 也不一定為 orthogonal。
* $A = U\Sigma V^T$，其中，$U$ 為 left sigular vectors matrix，$V$ 為 right sigular vectors matrix，$\Sigma$ 為 singular value matrix
* 如何確定 $U$ 與 $V$ 存在, 並且為 orthogonal matrix
* 我們知道, Symmetric matrix 可以得到 full set of eigenvalue, eigenvectors 互為 orthogonal, 且其為正定矩陣 $\Rightarrow \lambda > 0$.
* 因此對於任意矩陣 $A$, $A^TA$ 為對稱矩陣, $A^TA = V\Sigma^T U^TU\Sigma V^T = V(\Sigma^T\Sigma)V^T$, $V^T$ 即為 $A^TA$ 的 eigenvectors matrix, $v_i^Tv_j = 0$ for $i \neq j$
* $Av_i = \sigma_iu_i \Rightarrow u_i = \frac{Av_i}{\sigma_i}$, $u_j = \frac{Av_j}{\sigma_j}$, $u_i^Tu_j = \frac{v_i^TA^TAv_j}{\sigma_i\sigma_j}$
* 可以發現, $v_j$ 為 $A^TA$ 的 eigenvector, $\Rightarrow u_i^tu_j = \frac{v_i^T\sigma_j^2v_j}{\sigma_i\sigma_j} = 0$
* 再來細看 $U$ 與 $V$
* 假設矩陣 $A$ 為 $m \times n$, 並且其 rank 為 r
* $U$ 存在 r 個非零 eigenvalues 的 eigenvectors, 以及 m - r 個 eigenvalue 為零的 eigenvectors
* $V$ 存在 r 個非零 eigenvalues 的 eigenvectors, 以及 n - r 個 eigenvalue 為零的 eigenvectors
* $A\left[
\begin{array}{cccccc}
v_1 & v_2 & ... & v_r & ... v_n \\
\end{array}
\right] = \left[
\begin{array}{cccccc}
u_1 & u_2 & ... & u_r & ... u_m \\
\end{array}
\right] \left[
\begin{array}{ccccc}
\sigma_1 & & & | \\
& ... & & | & 0 \\
& & \sigma_r & | \\
\_ & \_ & \_ & | & \_ \\
& 0 & & | & 0 \\
\end{array}
\right]$
* 對於 $i \leq r$, $v_i$ 為 C(A^T) 的 basic
* 對於 $i \leq r$, $u_i$ 為 C(A) 的 basic
* 對於 $i > r$, $v_i$ 為 N(A) 的 basic
* 對於 $i > r$, $u_i$ 為 N(A^T) 的 basic
* Reduced form of SVD
* $A\left[
\begin{array}{cccc}
v_1 & v_2 & ... & v_r \\
\end{array}
\right] = \left[
\begin{array}{cccc}
u_1 & u_2 & ... & u_r \\
\end{array}
\right] \left[
\begin{array}{cccc}
\sigma_1 \\
& \sigma_2 \\
& & ... \\
& & & \sigma_r \\
\end{array}
\right]$
* The geometry of SVD
* 假設 $A$ 為 $2 \times 2$ 的矩陣, $Ax = U\Sigma V^T$
* $V^Tx$: rotate $x$ to $V^Tx$
* 因為 $V$ 為 orthogonal matrix, 因此長度不變
* $\Sigma V^Tx$： stretche $V^Tx$ by $\Sigma$
* $U\Sigma V^T$: rotate to $Ax$
* Maximum value
* $\frac{||Ax||}{||x||}$
* $x = v_1$
* $\frac{{||Ax||}^2}{{x}^2} = \frac{x^TA^TAx}{x^Tx} = \frac{x^TSx}{x^Tx}$
* 對於任意的 $x = c_1v_1 + c_2v_2 + ... + c_nv_n$, $\sum c_i = 1$
* $x^TSx = \lambda_1c_1^2 + \lambda_2c_2^2 + ... + \lambda_nc_n^2$
* $x^Tx = c_1^2 + c_2^2 + ... + c_n^2$
* $\Rightarrow \frac{x^TSx}{x^Tx} = \frac{\lambda_1c_1^2 + \lambda_2c_2^2 + ... + \lambda_nc_n^2}{c_1^2 + c_2^2 + ... + c_n^2}$
* 因為 $\lambda_1 > \lambda_2 > ... > \lambda_n$, 當 $c_1 = 1, c_2 = c_3 = ... + c_n = 0$ 有最大值
* 若 $x^Tv_1 = 0$
* 則 $\frac{x^TSx}{x^Tx} = \frac{\lambda_2c_2^2 + ... + \lambda_nc_n^2}{c_2^2 + ... + c_n^2} \Rightarrow c_2 = 1, c_3 = ... + c_n = 0$ 時有最大值
* The polar decomposition
* $A = QS$
* 每個 real square matrix 都可以拆解成一個 orthogonal matrix 與一個 symmetric matrix 相乘
* $A = U\Sigma V^T = (UV^T)(V\Sigma V^T) = QS$
* 若 A 為可逆矩陣, 則 S 必為正定矩陣
* $S = V\Sigma V^T = A^TA$
* 因為 $V$ 為 orthogonal matrix, columns of $A$ are independent
* $S$ 為正定矩陣