线性代数与数值方法

作者: 田田ww | 来源:发表于2019-04-25 15:38 被阅读0次

主要分以下几个方面进行说明：

一、矩阵分解

二、线性最小二乘

三、非线性最小二乘

四、直接稀疏矩阵方法

五、迭代方法

一、矩阵分解

1.奇异值分解(SVD)

奇异值分解可将任意 $M\times N$ 实数矩阵 $A$ 分解成如下形式：
$A_{m\times n}=U_{m\times p} \Sigma_{p\times p} V_{p\times n} ^T=[u_0\arrowvert \cdots \arrowvert u_{p-1}] \left[\begin{array}{ccc} \sigma_0 &&\\& \ddots&\\ &&\sigma_{p-1}\end{array}\right] \left[\begin{array}{c}v_0^T\\\hline \vdots\\\hline v_{p-1}^T \end{array}\right]$
其中， $p = \min (m,n)$ ，矩阵 $U$ 和 $V$ 是正交矩阵，即 $U^TU=I$ 和 $V^TV=I$ 。其中 $\Sigma$ 主对角线上的值为矩阵 $A$ 的奇异值，所有奇异值均是非负的，并按照降序排列。如果仅有前r个奇异值是正的，那么矩阵A的秩即为r，同时SVD下标可用r取代。

引用自《计算机视觉-算法与应用》

应用
1.求伪逆（求解线性最小平方、最小二乘问题）：
若矩阵 $A$ 的奇异值分解为 $A=U \Sigma V^T$ ，那么 $A$ 的伪逆为 $A^+=V \Sigma ^ + U^T$ ，其中 $\Sigma^+$ 是 $\Sigma$ 的伪逆，将原矩阵主对角线上每个非零元素求倒数之后再转置得到。
2.矩阵近似值（PCA降维）：
PCA算法的作用是把数据集映射到低维空间，数据集的特征值(在SVD中用奇异值表征)按照重要性排列，降维的过程就是舍弃不重要的特征向量的过程，而剩下的特征向量组成的空间即为降维后的空间。

2.特征值分解

如果矩阵 $C$ 是对称阵 $(m=n)$ 那么其特征值分解的形式：
$C=U\Lambda U^T=[u_0\arrowvert \cdots \arrowvert u_{n-1}] \left[\begin{array}{ccc} \lambda_0 &&\\& \ddots&\\ &&\lambda_{p-1}\end{array}\right] \left[\begin{array}{c}u_0^T\\\hline \vdots\\\hline u_{n-1}^T \end{array}\right]=\sum_{i=0}^{n-1}\lambda_iu_iu_i^T$
这里 $u$ 是特征向量， $\lambda$ 是特征值且 $\lambda_0\ge\lambda_1\ge\cdots\ge\lambda_{n-1}$
其中对称阵 $C$ 可以通过一系列外积之和来构造
$C= \sum_i{a_ia_i^T}=AA^T$
在这种情况下，我们可以保证所有特征值 $\lambda_i$ 都是非负的。
此时产生的矩阵 $C$ 是半正定矩阵，即对任意非0列向量 $x$ ，存在 $x^TCx\ge0, \forall x$ 如果矩阵 $C$ 满秩所有特征值均为正，称为对称正定矩阵(SPD)。
对称正定矩阵在数据统计分析中表示一组数据点 ${x_i}$ 围绕其中心 $\bar x$ 产生的协方差
$C=\frac{1}{n} \sum_i (x_i-\bar x)(x_i-\bar x)^T$
矩阵 $C$ 的特征值和特征向量与 $A$ 的奇异值和奇异向量有着紧密联系若有 $A=U\Sigma V^T$ 则 $C=AA^T=U\Sigma V^TV\Sigma U^T=U\Lambda U^T$ 由此我们可以知道 $\lambda_i=\sigma_i^2$ 且矩阵 $A$ 的左奇异向量就是矩阵 $C$ 的特征向量。