矩阵分解 (decomposition, factorization)是将矩阵拆解为数个矩阵的乘积。(就像可以把整数分解为素数的乘积来研究整数的一些性质)
eigendecomposition
特征分解（Eigendecomposition），又称谱分解（Spectral decomposition）是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。(需要注意只有对可对角化矩阵才可以施以特征分解）
N 维非零向量 v 是 N×N 矩阵 A 的特征向量，当且仅当下式成立：
\begin{equation}
Av = \lambda v
\end{equation}
其中$\lambda$ 是一个scalar，特征向量 v 对应的特征值。也即特征向量被施以线性变换 A 只会使向量伸长或缩短而其方向不被改变。（左特征向量也成立：$v^\top A = \lambda v^\top$）
如果v是A的一个特征向量，则v的伸长或缩短 (sv for $ s \in \mathbb{R},s \ne 0$ )仍然是A的特征向量。因此只关注单位特征向量。
假设矩阵A的n个线性独立特征向量（列向量）组成矩阵V，对应的特征值组成列向量$\lambda = [\lambda_1,…,\lambda_n]^\top$. 则A的特征分解为：
\begin{equation}
A = V \mathbf{ diag}(\lambda) V^{-1}
\end{equation}
不是所有的矩阵都能分解成特征值和特征向量，这里我们只关注实对称矩阵（能分解成only real-valued eigenvectors and eigenvalues）
\begin{equation}
A = Q \Lambda Q^{-1}
\end{equation}
其中Q是orthogonal matrix composed of eigenvectors of A, $\Lambda = diag(\lambda)$。由于Q是正交矩阵，可以将A看成是在Q的不同方向(列向量$v^i$)伸缩$\lambda_i$倍。
特征分解的用处：
- The matrix is singular if and only if any of the eigenvalues are 0.
- optimize quadratic expressions of the form $f(x)=x^\top Ax $ subject to $||x||_2 =1$. f的最大值是最大的特征值，f的最小值是最小的特征值。
- 判定矩阵是否正定。
- positive semidefinite：eigenvalues are all positive or zero-valued. 半正定矩阵能保证$\forall x,x^\top A x \ge 0$
- positive definite：eigenvalues are all positive. 正定矩阵能额外保证 $x^\top A x = 0 \Rightarrow x = 0$
- negative definite： all eigenvalues are negative
- negative semidefinite： all eigenvalues are negative or zero-valued
Singular Value Decomposition (SVD分解)
奇异值分解（Singular Value Decomposition）将矩阵分解为奇异向量和奇异值（singular vectors and singular values.）,对矩阵的扰动不敏感。
SVD分解比特征分解更通用，任意实数矩阵（即使不是方阵）都有奇异值分解，但特征分解不是。
\begin{equation}
A = U D V^\top
\end{equation}
如果A是$m \times n$矩阵，则U是$m \times m$,D 是 $m \times n$, V 是$n \times n$.
U和V是正交矩阵（orthogonal matrices），D是对角矩阵（diagonal matrix），D不一定是方阵。
- D中对角线上的元素是矩阵A的奇异值（singular values），矩阵A的非零奇异值是$A^\top A$或$A^\top A$的特征值的平方根。
- U中的列向量是左奇异向量（left-singular vectors），左奇异向量是$AA^\top$的特征向量。
- V中的列向量是右奇异向量（right-singular vectors），右奇异向量是$A^\top A$的特征向量。
SVD主要用于求矩阵（non-square matrices）的伪逆和主成分分析（PCA）。
matlab code:
[U,D,V] = svd(X)
SVD分解用于求伪逆 （The Moore-Penrose Pseudoinverse）
矩阵A的伪逆定义：
\begin{equation}
A^+ = \lim_{\alpha \to 0}(A^\top A+ \alpha I)^{-1}A^\top
\end{equation}
实际算法更趋于使用下式：
\begin{equation}
A^+ = VD^+U^\top
\end{equation}
其中U,D,V是矩阵A的SVD分解。D的伪逆$D^+$是通过把矩阵D主对角线上每个非零元素都求倒数之后再转置得到的。
求伪逆通常可以用来求解线性最小平方、最小二乘法问题。
- 当矩阵A的列数量多于行数量时，可能存在许多解。用伪逆可以算出其中一个。在所有的答案中，答案$x = A^+y$拥有最小的$L^2$ norm $||x||_2$.
- 当矩阵A的行数量多于列数量时，可能不存在解。通过伪逆算出来的解会使得$Ax$尽可能接近y，$||Ax-y||_2$最小。