特征分解

特征值和特征向量的定义如下：

$A\vec x=\lambda\vec x$

假设 $A$ 是 $n\times n$ 的矩阵，现在如果我们求出了 $A$ 的 $n$ 个特征值 $\lambda_1\leq\lambda_2\leq\cdots\lambda_n$ 以及对应的特征向量 $\vec x_1,\vec x_2,\cdots,\vec x_n$，那么 $A$ 就可以用下式的特征分解表示：

$A=W\Sigma W^{-1}$

其中 $W$ 是这 $n$ 个特征向量所张成的 $n\times n$ 维矩阵，而 $\Sigma$ 为 $n$ 个特征值为主对角线的 $n$ 维方阵。一般我们会把 $W$ 的每个向量标准化，即 $||\vec w_i||_2=1$，或者 $\vec w_i^T\vec w_i=1$。此时满足 $W^TW=I$，即 $W^T=W^{-1}$，这样特征分解表达式可以写成：

$A=W\Sigma W^T$

要进行特征分解，矩阵A必须为方阵。那么如果A不是方阵，我们还可以对矩阵进行分解吗？答案是可以，此时就要用到 SVD

奇异值分解

奇异值分解（Singular Value Decomposition，以下简称SVD）是在机器学习领域广泛应用的算法，它不光可以用于降维算法中的特征分解，还可以用于推荐系统，以及自然语言处理等领域。是很多机器学习算法的基石。本文就 SVD 的原理做一个总结，并讨论在 PCA 降维算法中是如何运用SVD的。

和特征分解不同，SVD 不要求分解的矩阵为方阵。假设 $A$ 为 $m\times n$ 的矩阵，那么它的 SVD 为：

$A=U\Sigma V^T$

其中 $U$ 是一个 $m\times m$ 方阵，$\Sigma$ 是 $m\times n$ 矩阵，除了主对角线上的元素以外全是 0，主对角线上的元素称为奇异值。$V$ 是 $n\times n$ 方阵。

那么如何求出 $U,\Sigma,V$ 这三个矩阵呢？

通过 $A^TA$ 我们可以得到一个 $n\times n$ 方阵，然后特征分解：

$A^TA\vec v_i=\lambda_i\vec v_i$

所有特征向量 $\vec v_i$ 即可组成 $n\times n$ 方阵 $V$
同理，通过如下分解：

$AA^T\vec u_i=\lambda_i\vec u_i$

即可得到 $U$。
而 $\Sigma$ 即是 $A$ 的奇异值 $\sigma_i$：

$A=U\Sigma V^T\Rightarrow AV=U\Sigma V^TV\Rightarrow \sigma_i=\frac{Av_i}{u_i}$

一些性质

$A=U\Sigma V^T\Rightarrow A^T=V\Sigma U^T\Rightarrow A^TA=V\Sigma^2V^T$ 也就是说：$\sigma_i^2=\lambda_i$（求解奇异值的第二个方法）
对于奇异值,它跟我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说，我们也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵。由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪。