# Linear Algebra Decomposition (2)
###### tags: `Data Science`, `Linear Algebra`
## Eigendecomposition
Recall that the eigenvector and eigenvalue of a square matrix $\pmb{A}$ is the nonzero vector and the scalar such that $\pmb{Av}=\lambda\pmb{v}$. Suppose $\pmb{A}$ has $n$ linearly independent eigenvectors $\pmb{V}=\{\pmb{v}^{(1)}, \pmb{v}^{(2)},...\pmb{v}^{(n)}\}$ and its corresponding eigenvalue $\pmb{\lambda}=\{\lambda_1, \lambda_2,...\lambda_n\}$. It's obvious that $\pmb{A}\pmb{V}=\pmb{V}diag({\pmb{\lambda}})$. Therefore, the eigendecomposition of $\pmb{A}$ can be written as $\pmb{A}=\pmb{V}diag({\pmb{\lambda}})\pmb{V}^{-1}$.

Suppose $\pmb{A}$ is a _real symmetric_ matrix, then it can be decomposed into real-valued eigenvectors and eigenvalues: $\pmb{A}=\pmb{Q}{\pmb{\Lambda}}\pmb{Q}^{-1}$, where $\pmb{Q}$ is an orthogonal matrix of eigenvectors of $\pmb{A}$ and $\Lambda_{i,i}$ is the corresponding eigenvalues.

## Singular Value Decomposition (SVD)
Note that not all the real matrix has a eigendecomposition. Therefore, singular value decomposition provides a more general way to factorize the matrix. Every real matrix $\pmb{A}$ has a singular value decomposition.

The singular value decomposition for any real matrix $\pmb{A}$ can be written as $\pmb{A}=\pmb{U}{\pmb{D}}\pmb{V}^T$. Suppose $\pmb{A}$ is a $m \times n$ matrix. The left-singular matrix $\pmb{U}$ is a $m\times m$ matrix, singular values $\pmb{D}$ is a $m \times n$ matrix, and right-singular matrix $\pmb{V}$ is a $n \times n$ matrix.

Because $\pmb{AA}^T$ is a symmetric real matrix, therefore, $\pmb{AA}^T$ can be factorized using eigendecomposition:

$\pmb{A}^T=(\pmb{U}{\pmb{D}}\pmb{V}^T)^T=\pmb{V}\pmb{D}^T\pmb{U}^T=\pmb{V}\pmb{D}\pmb{U}^T$
$\pmb{AA}^T=\pmb{U}{\pmb{D}}\pmb{V}^T\pmb{V}\pmb{D}\pmb{U}^T$.

Recall that in eigendecomposition, the eigenvectors are orthogonal, therefore, $\pmb{U}\pmb{U}^T=\pmb{I}$ and $\pmb{V}\pmb{V}^T=\pmb{I}$.

$\pmb{AA}^T=\pmb{U}{\pmb{D}}^2\pmb{U}^T=\pmb{U}\pmb{D}^2\pmb{U}^{-1}$

This imply that the left-singular matrix $\pmb{U}$ is the eigenvectors of $\pmb{AA}^T$. Similarly, we can proove that the right-singular matrix $\pmb{V}$ is the eigenvectors of $\pmb{A}^T\pmb{A}$.

## Reference
* Ian Goodfellow and Yoshua Bengio and Aaron Courville. 2016. “Deep Learning”. MIT Press.
* Gilbert Strang. 2011. “MIT 18.06SC Linear Algebra”
* Gilbert Strang. 2018. “MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning”
* Jure Leskovec, Anand Rajaraman, Jeff Ullman. 201. "Stanford CS341 Mining of Massive Datasets"