数据科学算法ch9-奇异值分解与主成分分析

奇异值分解与主成分分析

在机器学习中，随着数据维度的升高，分类器的性能会先增加后降低。这可能是因为维度过高会导致过拟合问题。为了缓解过拟合，我们可以用数据降维。因此现在我们来学习两种常用的数据降维方法：奇异值分解(SVD) 和 主成分分析(PCA)

对于是方阵的数据，我们可以用特征值分解，但如果数据不是方阵，只是普通的方阵，那么就可以使用奇异值分解和主成分分析

对角化与特征值分解

相似矩阵

对于矩阵 $\boldsymbol {A,B}\in\boldsymbol R^{n\times n}$ ，若存在$n\times n$ 的可逆矩阵$\boldsymbol P$，使得 $\boldsymbol A=\boldsymbol {PBP}^{-1}$,则称矩阵$\boldsymbol {A}$和$\boldsymbol B$ 是相似的

正交矩阵

对于矩阵$\boldsymbol P$ ,若$\boldsymbol P^{-1} = \boldsymbol P^T$ 则称$ \boldsymbol P$ 为正交矩阵。

由于$\boldsymbol {PP}^T = \boldsymbol I$​ ，因此正交矩阵是一类特殊的线性变换，它是保持原点不动，长度不变的旋转变换

对角化

若方阵$\boldsymbol A$ 相似于一个对角阵，即存在一个可逆矩阵P和对角矩阵 $\Sigma$ ，使得 $\boldsymbol A=\boldsymbol {P\Sigma P}^{-1}$ ，则称$\boldsymbol A$是可对角化的

矩阵对角化的重要性在于，若矩阵 $\boldsymbol A$ 是可对角化的，那么会满足以下两条性质：

$$\boldsymbol A^k = \boldsymbol {P\Sigma}^k\boldsymbol P^{-1}\\ \boldsymbol A^{-1} = \boldsymbol {P\Sigma}^{-1}\boldsymbol P^{-1}$$

接下来给出对角化的相关定理

• 矩阵 $\boldsymbol A \in \boldsymbol {R}^{n\times n}$ 可对角化的充分必要条件是$\boldsymbol A$ 有 n 个线性无关的特征向量

• 矩阵 $\boldsymbol A \in \boldsymbol {R}^{n\times n}$ 可对角化的充分必要条件是，该矩阵每一个特征值的几何重数 等于其 代数重数

正交对角化

若存在对角阵 $\boldsymbol \Sigma $ 、正交矩阵 $\boldsymbol P$ ，使得$\boldsymbol A = \boldsymbol P\boldsymbol \Sigma\boldsymbol P^{T}$​ 则称A是可正交对角化的

正交对角化也是一种矩阵分解方法，该方法又被称为特征值分解。若矩阵$\boldsymbol A$ 是可正交对角化的，意味着矩阵 $\boldsymbol A$ 对应的线性变换可以分解成三步：

1. 将空间向量经过正交矩阵$\boldsymbol P^T$ 进行旋转变换
2. 通过对角矩阵$\boldsymbol \Sigma$​ 进行伸缩变换
3. 经过正交矩阵$\boldsymbol P$ 进行旋转变换，其中 $\boldsymbol P$ 和 $\boldsymbol P^T$ 互为逆变换

接下来给出对角化的相关定理：若$\boldsymbol A$是实对称矩阵，那么$\boldsymbol A$具有一下性质

1. 不同特征值对应的特征向量之间是正交的
2. $\boldsymbol A$ 有n个实特征值(如果包含重数)
3. 对于任一特征值，其对应的特征向量的集合重数等于特征值的代数重数
4. 特征空间是相互正交的
5. $\boldsymbol A$​是可正交对角化的

特征值分解

求解对称方程 $A\in \mathbb R^{n\times n}$ 的特征分解步骤

• 计算矩阵A的特征值$\lambda_1\cdots,\lambda_n$ 即 求特征方程 $|A-\lambda I| = 0$ 的n个根

• 求特征值对应的n个相互正交的特征向量 $q_1,\cdots,q_n$即求解方程组并单位化

  $$Aq_i = \lambda_iq_i,i=1,\cdots,n$$

• 记矩阵 $Q=(q_1,\cdots,q_n)$

• 最终得到矩阵A的特征分解为

  $$A = Q\begin{pmatrix} \lambda_1 & & \\ & \cdots & \\ & & \lambda_n \end{pmatrix}Q^T$$

例：求实对称矩阵的特征分解

$$A =\begin{bmatrix} 2& 1\\ 1 & 2 \end{bmatrix}$$

1. 首先我们计算特征向量

$$|\lambda I-A| =\begin{bmatrix}\lambda-2& -1\\ -1 & \lambda-2 \end{bmatrix}=0\\$$

特征值：$\lambda_1=3,\lambda_2=1$

带入求解并单位化： $q_1 = (\frac{1}{\sqrt 2},\frac{1}{\sqrt 2})^T,q_2 = (-\frac{1}{\sqrt2},\frac{1}{\sqrt2})^T$

1. 写出特征向量方阵Q和特征值方阵 $\Lambda$

$$Q =[q_1,q_2] =\begin{bmatrix} \frac{1}{\sqrt2}& -\frac{1}{\sqrt 2}\\ \frac{1}{\sqrt 2} & \frac{1}{\sqrt2} \end{bmatrix},\Lambda =\begin{bmatrix} \lambda_1 & \\ & \lambda_2 \end{bmatrix} = \begin{bmatrix} 3 &\\ & 1 \end{bmatrix}$$

1. $p=(\alpha_1,\alpha_2,\alpha_3),(p^{-1})^T=(\beta_1,\beta_2,\beta_3)$

$$G_1 = \alpha_1\beta_1^T+\alpha_2\beta_2^T\\~\\ G_2 = \alpha_3\beta_3^T$$

A和$G_1,G_2$的关系就是特征分解

奇异值分解

给定矩阵 $\boldsymbol A\in \boldsymbol R^{m\times n}$ ,则矩阵 $\boldsymbol A$ 的奇异值分解为：

$$\boldsymbol A = \boldsymbol U\boldsymbol\Sigma\boldsymbol V^T$$

分解过程

1. 计算矩阵 $\boldsymbol {AA}^T$ 和 $\boldsymbol A^T\boldsymbol A$
2. 分别计算矩阵 $\boldsymbol {AA}^T$ 和 $\boldsymbol A^T\boldsymbol A$ 的特征值和对应的特征向量
3. 用矩阵 $\boldsymbol {AA}^T$ 的特征向量组成矩阵 $\boldsymbol U$;用 $\boldsymbol A^T\boldsymbol A$ 的特征向量组成$\boldsymbol V$
4. 对矩阵 $\boldsymbol {AA}^T$ 和 $\boldsymbol A^T\boldsymbol A$ 的非零特征值求算术平方根，并对应特征向量的位置填入$\boldsymbol \Sigma$ 的对角元

主成分分析