『矩阵论笔记』详细介绍矩阵的三角分解(LR分解)+平方根分解(Cholesky分解)！

千次阅读 多人点赞 2019-11-14 20:06:12

矩阵的三角分解！文章目录一、三角分解1.1、内容回顾一、三角分解 LU分解(LU Decomposition)是矩阵分解的一种，可以将一个矩阵分解为一个单位下三角矩阵和一个上三角矩阵的乘积（有时是它们和一个置换矩阵的乘积）...

详细介绍矩阵的三角分解(LR分解)+平方根分解(Cholesky分解)！ 


 文章目录
 一. 三角分解(LR分解)
1.1. 方阵的两个重要分解
1.2. 上(下)三角阵的性质
1.3. 三角分解的概念
1.4. 三角分解的充要条件：定理1
   
二. 三角分解(LR分解)的求解
2.1. 三角分解的方法之高斯消元法
2.2. 带行交换的LR分解：定理2
2.3. 三角分解的方法之待定系数法
   
三. 平方根分解(Cholesky分解)
3.1. LDR分解的定义(预备知识)
3.2. 平方根分解(Cholesky分解)
3.3. 平方根分解的求解之高斯消元法
3.4. 平方根分解的求解之待定系数法
   
四. Cholesky分解用在计算马氏距离
4.1. 马氏距离
4.2. matlab实现计算马氏距离
   
参考文献
 

 
一. 三角分解(LR分解) 
LR 分解( LR Decomposition )是矩阵分解的一种，可以将一个矩阵分解为一个单位下三角矩阵和一个上三角矩阵的乘积(有时是它们和一个置换矩阵的乘积)。LR 分解主要应用在数值分析中，用来解线性方程、求反矩阵或计算行列式。 
1.1. 方阵的两个重要分解 
内容回顾： 
①是相似对角化：  $\mathbf A=\mathbf P \operatorname{diag}\left\{\lambda_{1}, \lambda_{2}, \cdots, \lambda_{n}\right\} \mathbf P^{-1}$ 
②是 Jordan 标准形：  $\mathbf A=\mathbf P \operatorname{diag}\left\{J_{1}\left(\lambda_{1}\right), J_{2}\left(\lambda_{2}\right), \cdots, J_{s}\left(\lambda_{s}\right)\right\} \mathbf P^{-1}$ 
这些矩阵分解也是有问题，首先矩阵  $\mathbf P$ (是由特征向量构成，它的性质我们不是很熟悉) 的性质我们不是很熟悉，当然中间的对角阵和对角块我们比较熟悉。我们希望把矩阵分解为形式比较简单或性质比较熟悉的若干个矩阵的乘积形式，这就叫做矩阵分解。
分解意义： 清晰地反映出原矩阵的某些特征，提供有效的数值计算方法和理论分析依据。
哪些矩阵我们比较熟悉呢？首先 Jordan 标准形，还有分块对角阵，另外还有一种三角矩阵(上三角矩阵，下三角矩阵)。而且对角元素全为1的上三角和下三角矩阵叫做单位上三角矩阵和单位下三角矩阵。 
上三角矩阵 下三角矩阵
 $\left[\begin{array}{ccc}{a_{11}} & {\cdots} & {a_{1 n}} \\ {} & {\ddots} & {\vdots} \\ {} & {} & {a_{m n}}\end{array}\right]$  $\left[\begin{array}{ccc}{a_{11}} & {} & {} \\ {\vdots} & {\ddots} & {} \\ {a_{n 1}} & {\cdots} & {a_{n n}}\end{array}\right]$ 
单位上三角矩阵(对角全1) 单位下三角矩阵(对角全1)
 $\left[\begin{array}{rrrr}{1} & {*} & {\dots} & {*} \\ {} & {\ddots} & {\ddots} & {\vdots} \\ {} & {} & {\ddots} & {*} \\ {} & {} & {} & {1}\end{array}\right]$  $\left[\begin{array}{cccc}{1} \\ {*} & {\ddots} & {} \\ {\vdots} & {} & {\ddots} \\ {*} & {\cdots} & {*} & {1}\end{array}\right]$ 
1.2. 上(下)三角阵的性质 
上(下)三角阵的和、差、乘积、逆仍是上(下)三角阵；
单位上(下)三角阵的乘积、逆仍为单位上(下)三角阵；
另外系数矩阵  $\mathbf A$ 为三角阵的非齐次线性方程组  $\mathbf A \mathbf x= \mathbf b$  容易求解，也就是说如果矩阵  $\mathbf A$  为上三角矩阵或者下三角矩阵，这个方程非常容易求解(本科学过对的课程非线性方程组求解高斯消元法目的就是化成三角阵)； 
1.3. 三角分解的概念 
若方阵  $\mathbf A$  可分解为 $\mathbf A=\mathbf L \mathbf R$  其中  $\mathbf L$  是单位下三角阵，  $\mathbf R$  是上三角阵，则称  $\mathbf A$  可三角分解(或 LR 分解，或 Doolittle 分解). 
对于非齐次线性方程组  $\mathbf A \mathbf x= \mathbf b$  
若方阵  $\mathbf A$  有三角分解  $\mathbf A=\mathbf L \mathbf R$ ，刚才的方程就可以变为2个方程，令  $\mathbf R \mathbf x=\mathbf y$ ；则  $\mathbf A \mathbf x= \mathbf b$  可分解为两个非齐次线性方程组： 

  

这2个方程很容易解决，首先因为  $\mathbf L$  是单位下三角矩阵，则方程  $\mathbf L \mathbf y=\mathbf b$  可以变为如下：
  $\left[\begin{array}{cccc}{1} & {} & {} & {} \\ {l_{21}} & {1} & {} & {} \\ {\vdots} & {\ddots} & {\ddots} & {} \\ {l_{n 1}} & {\cdots} & {l_{m n-1}} & {1}\end{array}\right]\left[\begin{array}{c}{y_{1}} \\ {y_{2}} \\ {\vdots} \\ {y_{n}}\end{array}\right]=\left[\begin{array}{c}{b_{1}} \\ {b_{2}} \\ {\vdots} \\ {b_{n}}\end{array}\right]$ 
其中：可以明显发现  $y_1 = b_1$ ，然后可以推出  $y_2$ ，以此类推！ $y_{1} \Rightarrow y_{2} \Rightarrow \cdots \Rightarrow y_{n}$ 
再由方程组  $\mathbf R \mathbf x=\mathbf y$ 
  $\left[\begin{array}{cccc}{r_{11}} & {r_{12}} & {\cdots} & {r_{1 n}} \\ {} & {r_{22}} & {\ddots} & {r_{2 n}} \\ {} & {} & {\ddots} & {\vdots} \\ {} & {} & {} & {r_{n n}}\end{array}\right]\left[\begin{array}{c}{x_{1}} \\ {x_{2}} \\ {\vdots} \\ {x_{n}}\end{array}\right]=\left[\begin{array}{c}{y_{1}} \\ {y_{2}} \\ {\vdots} \\ {y_{n}}\end{array}\right]$ 
其中  $x_n=r_{nn}$ ，最终我们可以得到： $x_{n} \Rightarrow x_{n-1} \Rightarrow \cdots \Rightarrow x_{1}$ 
所以三角分解的一个很重要的应用就是用来解非齐次线性方程组，其可以简化运算。 
1.4. 三角分解的充要条件：定理1 
定理1： 

  

先证明充要性： 

  


  


  


  


  

下面证明唯一性： 

  

下面证明必要性 

  


  

二. 三角分解(LR分解)的求解 
2.1. 三角分解的方法之高斯消元法 
下面的例子1： 

  

这里也是按照前一小节中证明充分性的方法。首先我们判断一下 n-1 阶顺序主子式是否有0： 

  

下面要用到高斯消元法，再系数矩阵的右边添加一个单位矩阵变成一个增广矩阵：
参考链接：增广矩阵！ 

  

这里我们已经把  $\mathbf R$  算出来了就是前面的上三角矩阵，后面的是  $\mathbf L^{-1}$ ，我们只需要对  $\mathbf L^{-1}$  再求逆就可以得到了  $\mathbf L$ ；这就是第一种方法高斯消元法求解三角分解，其中有求逆相对麻烦一些。 

  


  

下面的例子2： 

  

不存在LR分解，但是刚才我们介绍过三角分解主要作用就是用来求解线性方程的。解方程的时候只要这个矩阵是可逆的，肯定存在解。那么这个矩阵是可逆的，因此这个方程是有唯一解的。
如果我们想用三角分解求解这个方程，怎么办呢？我们发现只要把这个矩阵的第一行和第二行交换一下，矩阵  $\mathbf A$ 变为  $\mathbf {\tilde{A}}$ ，这个矩阵是满足三角分解的条件的。 

  

那么问题来了？方阵  $\mathbf A$  和  $\mathbf {\tilde{A}}$ 有什么关系呢？ 

  

 
 注意： 置换矩阵就是单位阵置换行以后的矩阵。 
 
2.2. 带行交换的LR分解：定理2 
定理2： 

  

下面的例子1： 

  


  

下面利用高斯消元法求解： 

  


  


  

2.3. 三角分解的方法之待定系数法 
通过前面的求解我们发现高斯消元法有一个问题：就是我们求解完得到的有个  $\mathbf L^{-1}$ ，我们需要转变求解其逆矩阵得到  $\mathbf L$ ，这样求解比较麻烦，所以编程实现也比较麻烦！ 

  


  

由矩阵的乘法可以知道， $\mathbf L \mathbf R$ 相乘的结果和  $\mathbf A$  对应位置相等。 

  

我们是如何推导的呢？先算  $\mathbf R$  的第一行，它和  $\mathbf A$  的第一行是一样的，算完之后我们就可以算出来  $\mathbf L$  的第一列。剩下我们再计算  $\mathbf R$  的第二行，用算  $\mathbf L$  的第二行乘以  $\mathbf R$  的第二列，得到如下的3)和4)； 

  

由此得到一般的公式(这个公式看着复杂，这个公式记不住没关系，我们知道先计算  $\mathbf R$  的第一行，再计算  $\mathbf L$  的第一列，依次进行下去(记住这个顺序)… )： 
 $r_{k j}=a_{k j}-\sum_{i=1}^{k-1} l_{k i} r_{i j}, \quad j=k, \quad k+1, \cdots, n$  
 $l_{i k}=\frac{1}{r_{k k}}\left(a_{i k}-\sum_{m=1}^{k-1} l_{i m} r_{m k}\right), \quad i=k+1, \cdots, n$  
下面的例子1： 
这里我们直接用待定系数法，不用高斯消元法，当然可以用这个。 

  

我们首先计算  $\mathbf R$  的第一行，我们刚才知道  $\mathbf R$  的第一行和  $\mathbf A$  的第一行是一样的。 再算  $\mathbf L$  的第一列，依次进行下去。 

  

三. 平方根分解(Cholesky分解) 
下面我们介绍另外一种分解叫做平方根分解，首先介绍一下预备知识LDR分解。 
3.1. LDR分解的定义(预备知识) 

  

这样得到的矩阵分解就是比较对称的了，所以怎么求LDR分解其实很简单：首先求解  $\mathbf A$  的三角分解(LR分解)  $\mathbf A=\mathbf L \mathbf R$ ；然后把  $\mathbf R$  的对角元素取出来组成一个对角阵，然后  $m a t h b f R$  的每一行除以相应的对角元素。 

  

下面的例子1： 

  


  

3.2. 平方根分解(Cholesky分解) 
如何矩阵  $\mathbf A$  是对称矩阵我们会得到什么结果？如果矩阵  $\mathbf A$  又是一个正定矩阵我们又会得到什么结论？这就是我们引出的平方根分解 
正定矩阵 $\mathbf A$ 分解 

  

 
 注意： 为什么可以得到  $\mathbf {L}^{\mathbf{T}}=\mathbf {R}$   $\begin{array}{l}{\mathbf A^{T}=(\mathbf L \mathbf D \mathbf R)^{T}} = { \mathbf R^{T} \mathbf D^{T} \mathbf L^{T}} = { \mathbf R^{T} \mathbf D \mathbf L^{T}}\end{array}$  再利用分解是唯一的  $\begin{array}{l}{\mathbf A=\mathbf L \mathbf D \mathbf R}\end{array}$  又因为 $\mathbf A$ 是对称矩阵，则 $\begin{array}{l}{\mathbf A= \mathbf A^T=\mathbf L \mathbf D \mathbf R=\mathbf R^{T} \mathbf D \mathbf L^{T}}\end{array}$ 所以我们可以得到： $\mathbf {L}^{\mathbf{T}}=\mathbf {R}$  
 
有了上面的以后，我们再做一个分解，因为  $\mathbf D$  是大于0的，我们对里面的元素进行开根号，标记为  $\mathbf D^{\frac{1}{2}}$ ； $\mathbf D^{\frac{1}{2}}=\left[\begin{array}{cccc}{\sqrt{d_{1}}} & {} & {} & {} \\ {} & {\sqrt{d_{2}}} & {} & {} \\ {} & {} & {\ddots} & {} \\ {} & {} & {} & {\sqrt{d_{n}}}\end{array}\right]$ 
则有： $\begin{array}{l}{\mathbf A=\mathbf L \mathbf D \mathbf R=\mathbf L \mathbf D^{\frac{1}{2}} \mathbf D^{\frac{1}{2}} \mathbf L^{\mathrm{T}}=\left(\mathbf L \mathbf D^{\frac{1}{2}}\right)\left(\mathbf L \mathbf D^{\frac{1}{2}}\right)^{\mathrm{T}}}\end{array}$  
 
 注意： 其中  $\mathbf L \mathbf D^{\frac{1}{2}}$  是下三角矩阵。如果  $\mathbf A$  是一维的，这里直接相当于一个数字乘以另外一个数字， $\mathbf A$  就相当于开根号，所以这就叫平方根分解(类似一个非负数开根号)。 
 
如果我们令  $\mathbf G=\mathbf L \mathbf D^{\frac{1}{2}}$ ，则  $\mathbf G$  是对角元素大于0的下三角矩阵，且 $\mathbf A=\mathbf G \mathbf G^{\mathrm{T}}$  

  

 
 注意： 其实平方根分解是在LDR分解的基础之上，只要是矩阵满足正定矩阵，那么LDR分解就是平方根分解。 
 
3.3. 平方根分解的求解之高斯消元法 
先求矩阵  $\mathbf A$  的 LDR 分解，然后对  $\mathbf D$  开根号，然后组合  $\mathbf L \mathbf D^{\frac{1}{2}}$  就得到矩阵  $\mathbf G$ 。 
下面的例子1： 

  

方法1：高斯消元法，因为如果矩阵  $\mathbf A$  的LDR分解 $\begin{array}{l}{\mathbf A=\mathbf L \mathbf D \mathbf R}\end{array}$ 那么则有： $\mathbf G=\mathbf L \mathbf D^{\frac{1}{2}}=\mathbf R^{T} \mathbf D^{\frac{1}{2}}$  因为最早求LR分解的时候，我们只求出  $\mathbf R$  后面求解的是  $\mathbf L^{-1}$ (涉及到求解逆矩阵这里比较麻烦)，所以这里我们只要求解  $\mathbf R$  就可以了。 

  

然后把矩阵  $\mathbf R$ (上三角矩阵)分解为对角矩阵和单位上三角矩阵，就是进行LDR分解的一部分。 $\mathbf R=\left[\begin{array}{ccc}{5} & {-2} & {0} \\ {0} & {11 / 5} & {-1} \\ {0} & {0} & {6 / 11}\end{array}\right]=\left[\begin{array}{ccc}{5} & {0} & {0} \\ {0} & {11 / 5} & {0} \\ {0} & {0} & {6 / 11}\end{array}\right]\left[\begin{array}{ccc}{1} & {-2 / 5} & {0} \\ {0} & {1} & {-5 / 11} \\ {0} & {0} & {1}\end{array}\right]$  

  

 
 注意：这里  $\mathbf L$  为：  $\mathbf L= \left[\begin{array}{rrr}{1} & {-2 / 5} & {0} \\ {0} & {1} & {-5 / 11} \\ {0} & {0} & {1}\end{array}\right] ^{T}$  
 
因此我们可以得到下三角矩阵  $\mathbf G=\mathbf R^{T} \mathbf D^{\frac{1}{2}}$  
 $\begin{aligned} \mathbf G &=\left[\begin{array}{ccc}{1} & {0} & {0} \\ {-2 / 5} & {1} & {0} \\ {0} & {-5 / 11} & {1}\end{array}\right]\left[\begin{array}{ccc}{\sqrt{5}} & {0} & {0} \\ {0} & {\sqrt{11 / 5}} & {0} \\ {0} & {0} & {\sqrt{6 / 11}}\end{array}\right] \\\\ &= \left[\begin{array}{ccc}{\sqrt{5}} & {0} & {0} \\ {-2 / \sqrt{5}} & {\sqrt{11 / 5}} & {0} \\ {0} & {-\sqrt{5 / 11}} & {\sqrt{6 / 11}}\end{array}\right] \end{aligned}$  
所以  $\mathbf A$  的平方根分解(Cholesky分解)为： 
 $\mathbf A=\left[\begin{array}{ccc}{5} & {-2} & {0} \\ {-2} & {3} & {-1} \\ {0} & {-1} & {1}\end{array}\right]=\mathbf G \mathbf G^{\mathrm{T}}=\left[\begin{array}{ccc}{\sqrt{5}} & {0} & {0} \\ {-2 / \sqrt{5}} & {\sqrt{11 / 5}} & {0} \\ {0} & {-\sqrt{5 / 11}} & {\sqrt{6 / 11}}\end{array}\right]\left[\begin{array}{ccc}{\sqrt{5}} & {-2 / \sqrt{5}} & {0} \\ {0} & {\sqrt{11 / 5}} & {-\sqrt{5 / 11}} \\ {0} & {0} & {\sqrt{6 / 11}}\end{array}\right]$  
3.4. 平方根分解的求解之待定系数法 
方法2：待定系数法 

  

我们可以得到如下的方程： 

  

所以  $\mathbf A$  的平方根分解(Cholesky分解)为： 
 $\mathbf A=\left[\begin{array}{ccc}{5} & {-2} & {0} \\ {-2} & {3} & {-1} \\ {0} & {-1} & {1}\end{array}\right]=\mathbf G \mathbf G^{\mathrm{T}}=\left[\begin{array}{ccc}{\sqrt{5}} & {0} & {0} \\ {-2 / \sqrt{5}} & {\sqrt{11 / 5}} & {0} \\ {0} & {-\sqrt{5 / 11}} & {\sqrt{6 / 11}}\end{array}\right]\left[\begin{array}{ccc}{\sqrt{5}} & {-2 / \sqrt{5}} & {0} \\ {0} & {\sqrt{11 / 5}} & {-\sqrt{5 / 11}} \\ {0} & {0} & {\sqrt{6 / 11}}\end{array}\right]$  
四. Cholesky分解用在计算马氏距离 
4.1. 马氏距离 
马氏距离度量学习的核心是获得如下式所示的马氏距离函数：
  $d_{\boldsymbol M}^{2}(\boldsymbol{x}, \boldsymbol{z})=(\boldsymbol{x}-\boldsymbol{z})^{T} \boldsymbol{M}(\boldsymbol{x}-\boldsymbol{z})$  其中  $\boldsymbol{x} \in \mathbb{R}^{n}$  和  $\boldsymbol{z} \in \mathbb{R}^{n}$  为  $n$  维特征空间中的  $2$  个样本， $\boldsymbol M \succeq 0$  为一个  $n \times n$  的对称半正定(Positive Semi-definite,PSD)矩阵。严格来说，马氏距离指代的是  $d_{\boldsymbol M}(\boldsymbol{x}, \boldsymbol{z})=\sqrt{(\boldsymbol{x}-\boldsymbol{z})^{T} \boldsymbol{M}(\boldsymbol{x}-\boldsymbol{z})}$ ，这里实际上是马氏距离的平方。不过由于  $\boldsymbol{M}$  是一个半正定矩阵，所以  $d_{\boldsymbol M}^{2}\geq 0$ 。  $d_{\boldsymbol M}$  比  $d_{\boldsymbol M}^2$  多一次计算步骤而且对最终结果没有实质影响。因此一般将上述公式所示的函数称为马氏距离函数并用它来计算距离。
同时由上述公式可知，在给定样本  $\boldsymbol{x}$  和  $\boldsymbol{z}$  之后， $d_{\boldsymbol M}^{2}(\boldsymbol{x}, \boldsymbol{z})$  将由矩阵  $\boldsymbol{M}$  确定，即 $d_{\boldsymbol M}^{2}(\boldsymbol{x}, \boldsymbol{z})$  是由  $\boldsymbol{M}$  参数化的函数。文献中一般将矩阵  $\boldsymbol{M}$  称为度量矩阵，或简称为度量，马氏距离度量学习的核心任务即为获得具有判别性的矩阵  $\boldsymbol{M}$ 。 
对于  $n$  维特征空间中两个样本间的马氏距离  $d_{\boldsymbol M}(\boldsymbol{x}, \boldsymbol{z})$  ，我们要求其需要满足以下的性质： 
  $\text { (1) } d_{\boldsymbol M}(\boldsymbol{x}, \boldsymbol{z}) \geq 0 (距离的非负性)$ 
 
  $\text { (2) }d_{\boldsymbol M}(\boldsymbol{x}, \boldsymbol{z})=0 \Longleftrightarrow \boldsymbol{x}=\boldsymbol{z}(同一性)$ 
 
   $\text { (3) }d_{\boldsymbol M}(\boldsymbol{x}, \boldsymbol{z})=d_{\boldsymbol M}(\boldsymbol{z}, \boldsymbol{x})(距离的对称性)$ 
 
   $\text { (4) }d_{\boldsymbol M}(\boldsymbol{x}, \boldsymbol{y}) \leq d_{\boldsymbol M}(\boldsymbol{x}, \boldsymbol{z})+d_{\boldsymbol M}(\boldsymbol{z}, \boldsymbol{y})(距离三角不等式)$ 
 
 为了使马氏距离函数满足上述各个性质，关键在于约束度量矩阵  $\boldsymbol{M}$  的半正定性，因此在马氏距离学习方法中一般都明确约束 $\boldsymbol M \succeq 0$ 。另外，马氏距离与欧氏距离也存在密切的联系，如果对度量矩阵  $\boldsymbol{M}$  作 Cholesky分解有  $\boldsymbol M=\boldsymbol L \boldsymbol L^{T}$   $(\boldsymbol L$ 为下三角矩阵 $)$ 
  $\begin{aligned} d_{\boldsymbol M}^{2}(\boldsymbol{x}, \boldsymbol{z}) &=(\boldsymbol{x}-\boldsymbol{z})^{T} \boldsymbol{M}(\boldsymbol{x}-\boldsymbol{z}) \\&=\operatorname{tr}\left(\boldsymbol M^{T}(\boldsymbol{x}-\boldsymbol{z})(\boldsymbol{x}-\boldsymbol{z})^{T}\right) \\ &=(\boldsymbol{x}-\boldsymbol{z})^{T} \boldsymbol L \boldsymbol L^{T}(\boldsymbol{x}-\boldsymbol{z}) \\ &=\left(\boldsymbol{L}^{T}(\boldsymbol{x}-\boldsymbol{z})\right)^{T} \boldsymbol{L}^{T}(\boldsymbol{x}-\boldsymbol{z}) \end{aligned}$ 
 
 令  $\boldsymbol G=\boldsymbol{L}^{T}$ ，则上面的等式可以变为如下：
  $\begin{aligned} d_{\boldsymbol M}^{2}(\boldsymbol{x}, \boldsymbol{z}) &=\left[\boldsymbol{G}(\boldsymbol{x}-\boldsymbol{z})\right]^{T} \left[\boldsymbol G(\boldsymbol{x}-\boldsymbol{z}) \right] \\ &=\left\|\boldsymbol{G}\left(\boldsymbol{x}-\boldsymbol{z}\right)\right\|_{2}^{2} \end{aligned}$ 
 
 即两个特征表达向量间的马氏距离等价于使用  $\boldsymbol G$  投影后的欧氏距离。当  $\boldsymbol{M}$  为单位矩阵时，马氏距离就转化成了欧氏距离  $d_{\boldsymbol I}^{2}\left(\boldsymbol{x}_{i}, \boldsymbol{z}_{j}\right)=\left\|\boldsymbol{x}_{i}-\boldsymbol{z}_{j}\right\|_{2}^{2}$ ，但此时只能获得样本相同维度间的关系。
  
4.2. matlab实现计算马氏距离 
测试样本971个 

  

训练样本2913个 

  

假设这个时候已经更新出来度量矩阵  $\boldsymbol{M_{100×100}}$ ，则可以计算马氏距离，我们可以轻易的发现计算出来的矩阵维度应该是  $2913 \times 971$  
function dist = MahDist(M, Xg, Xp)
% function dist = MahDist(M, Xg, Xp)
% Mahalanobis distance
Xg = Xg';
Xp = Xp';
% Input:
%   <M>: the metric kernel
%   <Xg>: features of the gallery samples. Size: [n, d]
%   [Xp]: features of the probe samples. Optional. Size: [m, d]
%
%   Note: MahDist(M, Xg) is the same as MahDist(M, Xg, Xg).
%
% Output:
%   dist: the computed distance matrix between Xg and Xp

if nargin == 2                              % nargin是用来判断输入变量个数的函数
    D = Xg * M * Xg';
    u = diag(D);
    dist = bsxfun(@plus, u, u') - 2 * D;
else
    u = sum((Xg * M) .* Xg, 2);
    v = sum((Xp * M) .* Xp, 2);
    dist = bsxfun(@plus, u, v') - 2 * Xg * M * Xp';
end

 
最终计算出来的马氏距离： 

  

matlab学习笔记 bsxfun函数；从计算时间上来说前两种实现差不多，远高于for的实现。但如果数据很大，第二种实现可能会有内存上的问题。所以bsxfun最好。 
 
参考文献 
本文主要参考国防科技大学杨文强教授课程PPT资料，这里表示感谢！

上三角矩阵	下三角矩阵
$\left[\begin{array}{ccc}{a_{11}} & {\cdots} & {a_{1 n}} \\ {} & {\ddots} & {\vdots} \\ {} & {} & {a_{m n}}\end{array}\right]$	$\left[\begin{array}{ccc}{a_{11}} & {} & {} \\ {\vdots} & {\ddots} & {} \\ {a_{n 1}} & {\cdots} & {a_{n n}}\end{array}\right]$
单位上三角矩阵(对角全1)	单位下三角矩阵(对角全1)
$\left[\begin{array}{rrrr}{1} & {} & {\dots} & {} \\ {} & {\ddots} & {\ddots} & {\vdots} \\ {} & {} & {\ddots} & {*} \\ {} & {} & {} & {1}\end{array}\right]$	$\left[\begin{array}{cccc}{1} \\ {} & {\ddots} & {} \\ {\vdots} & {} & {\ddots} \\ {} & {\cdots} & {*} & {1}\end{array}\right]$

收起

展开全文

Cholesky 马氏距离

计算机组成原理-基本组成

千次阅读 多人点赞 2019-09-18 15:12:34

具体可以用这样一个公式来表示：优化后的执行时间 = 受优化影响的执行时间 / 加速倍数 + 不受影响的执行时间需要进行的计算，本身可以分解成几个可以并行的任务。好比乘法和加法计算，几个人可以同时进行，不会影响...

计算机组成原理-基本组成

本文根据徐文浩老师的计算机组成原理记录:计算机组成原理

计算机组成原理-基本组成
1 计算机组成原理知识地图
2 计算机的基本硬件组成
3 冯·诺依曼体系结构
- 3.1 First Draft 计算机组成部分
- 3.2 图灵与冯·诺依曼体系结构
4 计算机性能
5 功耗
- 5.1 阿姆达尔定律（Amdahl’s Law）
- 5.2 原则性的性能提升方法
附录1: 系统芯片

1 计算机组成原理知识地图

计算机组成原理知识地图

错误描述: 在硬件和软件之间需要一座桥梁，而“计算机组成原理”就扮演了这样一个角色，它既隔离了软件和硬件，也提供了让软件无需关心硬件，就能直接操作硬件的接口。这里的计算机组成原理改成操作系统是不是更好，而且感觉这句话说的就是操作系统呀

正确描述: 其实操作系统也是一个“软件”，而开发操作系统，其实只需要关注到“组成原理”或者说“体系结构”就好了，而不需要真的了解硬件，比如电路层面的实现。操作系统，其实是在“组成原理”所讲到的“指令集”上的一层封装。

2 计算机的基本硬件组成

2.1 CPU: 中央处理器（Central Processing Unit）

计算机的所有“计算”都是由 CPU 来进行的

2.2 内存: 内存（Memory）

撰写的程序、打开的浏览器、运行的游戏，都要加载到内存里才能运行; 程序读取的数据、计算得到的结果，也都要放在内存里

2.3 主板: 主板（Motherboard）

存放在内存里的程序和数据，需要被 CPU 读取，CPU 计算完之后，还要把数据写回到内存。然而 CPU 不能直接插到内存上，反之亦然。于是才有了主板

主板的芯片组（Chipset）和总线（Bus）解决了 CPU 和内存之间如何通信的问题。芯片组控制了数据传输的流转，也就是数据从哪里到哪里的问题。总线则是实际数据传输的高速公路。因此，总线速度（Bus Speed）决定了数据能传输得多快。

2.4 I/O设备

外部 I/O 设备，它们是通过主板上的南桥（SouthBridge）芯片组，来控制和 CPU 之间的通信的。“南桥”芯片的名字很直观，一方面，它在主板上的位置，通常在主板的“南面”。另一方面，它的作用就是作为“桥”，来连接鼠标、键盘以及硬盘这些外部设备和 CPU 之间的通信。

以前的主板上通常也有“北桥”芯片，用来作为“桥”，连接 CPU 和内存、显卡之间的通信。不过，随着时间的变迁，现在的主板上的“北桥”芯片的工作，已经被移到了 CPU 的内部，所以你在主板上，已经看不到北桥芯片了。

2.5 特殊的设备

显卡（Graphics Card）。显卡之所以特殊，是因为显卡里有除了 CPU 之外的另一个“处理器”，也就是GPU（Graphics Processing Unit，图形处理器），GPU 一样可以做各种“计算”的工作。

3 冯·诺依曼体系结构

冯·诺依曼（John von Neumann）提出的冯·诺依曼体系结构（Von Neumann architecture），也叫存储程序计算机。存储程序计算机其实暗含了两个概念，一个是“可编程”计算机，一个是“存储”计算机。

计算机是由各种门电路组合而成的，然后通过组装出一个固定的电路版，来完成一个特定的计算程序。一旦需要修改功能，就要重新组装电路。这样的话，计算机就是“不可编程”的，因为程序在计算机硬件层面是“写死”的。最常见的就是老式计算器，电路板设好了加减乘除，做不了任何计算逻辑固定之外的事情。

“存储”计算机。程序本身是存储在计算机的内存里，可以通过加载不同的程序来解决不同的问题。有“存储程序计算机”，自然也有不能存储程序的计算机。典型的就是早年的“Plugboard”这样的插线板式的计算机。整个计算机就是一个巨大的插线板，通过在板子上不同的插头或者接口的位置插入线路，来实现不同的功能。这样的计算机自然是“可编程”的，但是编写好的程序不能存储下来供下一次加载使用，不得不每次要用到和当前不同的“程序”的时候，重新插板子，重新“编程”。

![冯·诺依曼体系结构示意图][冯·诺依曼体系结构示意图]

任何一台计算机的任何一个部件都可以归到运算器、控制器、存储器、输入设备和输出设备中，而所有的现代计算机也都是基于这个基础架构来设计开发的。

所有的计算机程序，都可以抽象为从输入设备读取输入信息，通过运算器和控制器来执行存储在存储器里的程序，最终把结果输出到输出设备中。目前所有的无论高级还是低级语言的程序，也都是基于这样一个抽象框架来进行运作的。

3.1 First Draft 计算机组成部分

首先是一个包含算术逻辑单元（Arithmetic Logic Unit，ALU）和处理器寄存器（Processor Register）的处理器单元（Processing Unit），用来完成各种算术和逻辑运算。因为它能够完成各种数据的处理或者计算工作，因此也有人把这个叫作数据通路（Datapath）或者运算器。

然后是一个包含指令寄存器（Instruction Register）和程序计数器（Program Counter）的控制器单元（Control Unit/CU），用来控制程序的流程，通常就是不同条件下的分支和跳转。在现在的计算机里，上面的算术逻辑单元和这里的控制器单元，共同组成了我们说的 CPU。

接着是用来存储数据（Data）和指令（Instruction）的内存。以及更大容量的外部存储，在过去，可能是磁带、磁鼓这样的设备，现在通常就是硬盘。

最后就是各种输入和输出设备

3.2 图灵与冯·诺依曼体系结构

两者有交叉但是不同，根据了解整理如下：

图灵机是一种思想模型（计算机的基本理论基础），是一种有穷的、构造性的问题的问题求解思路，图灵认为凡是能用算法解决的问题也一定能用图灵机解决；
冯诺依曼提出了“存储程序”的计算机设计思想，并“参照”图灵模型设计了历史上第一台电子计算机，即冯诺依曼机

ps：有看到一种有争议说法：冯诺依曼机是图灵机的实现，感觉这有点过于片面，所以上述姑且改为参照

4 计算机性能

4.1 响应时间

响应时间（Response time）或者叫执行时间（Execution time）。想要提升响应时间这个性能指标，你可以理解为让计算机“跑得更快”。

4.2 吞吐率

吞吐率（Throughput）或者带宽（Bandwidth），想要提升这个指标，你可以理解为让计算机“搬得更多”。

4.3 CPU 主频

CPU 主频即 CPU 的时钟频率, 2.8GHz: 可以粗浅地认为，CPU 在 1 秒时间内，可以执行的简单指令的数量是 2.8G 条

在 CPU 内部，和我们平时戴的电子石英表类似，有一个叫晶体振荡器（Oscillator Crystal）的东西，简称为晶振。我们把晶振当成 CPU 内部的电子表来使用。晶振带来的每一次“滴答”，就是时钟周期时间

性能 = 1/ 响应时间

运行一下 time 命令。它会返回三个值，第一个是real time，也就是我们说的 Wall Clock Time，也就是运行程序整个过程中流逝掉的时间；第二个是user time，也就是 CPU 在运行你的程序，在用户态运行指令的时间；第三个是sys time，是 CPU 在运行你的程序，在操作系统内核里运行指令的时间。而程序实际花费的 CPU 执行时间（CPU Time），就是 user time 加上 sys time

$ time seq 1000000 | wc -l

1000000
real  0m0.101s
user  0m0.031s
sys  0m0.016s

实际上程序用了 0.101s，但是 CPU time 只有 0.031+0.016 = 0.047s。运行程序的时间里，只有不到一半是实际花在这个程序上的

“并行原因”的运行的。虽然 seq 和 wc 这两个命令都是单线程运行的，但是这两个命令在多核 cpu 运行的情况下，会分别分配到两个不同的 cpu，于是 user 和 sys 的时间都是两个 cpu 上运行的时间之和，就可能超过 real 的时间。可以这样来快速验证

运行 time seq 100000000 | wc -l & 让这个命令多跑一会儿，并且在后台运行。然后利用 top 命令看不同进程的 cpu 占用情况，你会在 top 的前几行里看到 seq 和 wc 的 cpu 占用都接近 100，实际是各被分配到了一个不同的 cpu 执行

即使拿到了 CPU 时间，我们也不一定可以直接“比较”出两个程序的性能差异。即使在同一台计算机上，CPU 可能满载运行也可能降频运行，降频运行的时候自然花的时间会多一些

除了 CPU 之外，时间这个性能指标还会受到主板、内存这些其他相关硬件的影响。所以，我们需要对“时间”这个我们可以感知的指标进行拆解，把程序的 CPU 执行时间变成 CPU 时钟周期数（CPU Cycles）和时钟周期时间（Clock Cycle）的乘积

程序的 CPU 执行时间 =CPU 时钟周期数×时钟周期时间

简单的提升性能方案，自然缩短时钟周期时间，也就是提升主频。换句话说，就是换一块好一点的 CPU。不过，这个是软件工程师控制不了的事情，所以我们就把目光挪到了乘法的另一个因子——CPU 时钟周期数上。如果能够减少程序需要的 CPU 时钟周期数量，一样能够提升程序性能

对于 CPU 时钟周期数，我们可以再做一个分解，把它变成“指令数×每条指令的平均时钟周期数（Cycles Per Instruction，简称 CPI）”。不同的指令需要的 Cycles 是不同的，加法和乘法都对应着一条 CPU 指令，但是乘法需要的 Cycles 就比加法要多，自然也就慢。在这样拆分了之后，程序的 CPU 执行时间就可以变成这样三个部分的乘积

程序的 CPU 执行时间 = 指令数×CPI×Clock Cycle Time

时钟周期时间，就是计算机主频，这个取决于计算机硬件。我们所熟知的摩尔定律就一直在不停地提高我们计算机的主频。比如说，我最早使用的 80386 主频只有 33MHz，现在手头的笔记本电脑就有 2.8GHz，在主频层面，就提升了将近 100 倍
每条指令的平均时钟周期数 CPI，就是一条指令到底需要多少 CPU Cycle。在后面讲解 CPU 结构的时候，我们会看到，现代的 CPU 通过流水线技术（Pipeline），让一条指令需要的 CPU Cycle 尽可能地少。因此，对于 CPI 的优化，也是计算机组成和体系结构中的重要一环
指令数，代表执行我们的程序到底需要多少条指令、用哪些指令。这个很多时候就把挑战交给了编译器。同样的代码，编译成计算机指令时候，就有各种不同的表示方式

5 功耗

CPU，一般都被叫作超大规模集成电路（Very-Large-Scale Integration，VLSI）。这些电路，实际上都是一个个晶体管组合而成的。CPU 在计算，其实就是让晶体管里面的“开关”不断地去“打开”和“关闭”，来组合完成各种运算和功能

想要计算得快，一方面，我们要在 CPU 里，同样的面积里面，多放一些晶体管，也就是增加密度；另一方面，要让晶体管“打开”和“关闭”得更快一点，也就是提升主频。而这两者，都会增加功耗，带来耗电和散热的问题

可以把一个计算机 CPU 想象成一个巨大的工厂，里面有很多工人，相当于 CPU 上面的晶体管，互相之间协同工作

为了工作得快一点，我们要在工厂里多塞一点人。你可能会问，为什么不把工厂造得大一点呢？这是因为，人和人之间如果离得远了，互相之间走过去需要花的时间就会变长，这也会导致性能下降。这就好像如果 CPU 的面积大，晶体管之间的距离变大，电信号传输的时间就会变长，运算速度自然就慢了

除了多塞一点人，还希望每个人的动作都快一点，这样同样的时间里就可以多干一点活儿了。这就相当于提升 CPU 主频，但是动作快，每个人就要出汗散热。要是太热了，对工厂里面的人来说会中暑生病，对 CPU 来说就会崩溃出错

为了要提升性能，我们需要不断地增加晶体管数量。同样的面积下，要多放一点晶体管，就要把晶体管造得小一点。这个就是平时所说的提升“制程”。从 28nm 到 7nm，相当于晶体管本身变成了原来的 1/4 大小。这个就相当于在工厂里，同样的活儿，要找瘦小一点的工人，这样一个工厂里面就可以多一些人。我们还要提升主频，让开关的频率变快，也就是要找手脚更快的工人

在 CPU 里面，能够放下的晶体管数量和晶体管的“开关”频率也都是有限的。一个 CPU 的功率，可以用这样一个公式来表示：功耗 ~= 1/2 ×负载电容×电压的平方×开关频率×晶体管数量

5.1 阿姆达尔定律（Amdahl’s Law）

这个定律说的就是，对于一个程序进行优化之后，处理器并行运算之后效率提升的情况。具体可以用这样一个公式来表示：优化后的执行时间 = 受优化影响的执行时间 / 加速倍数 + 不受影响的执行时间

需要进行的计算，本身可以分解成几个可以并行的任务。好比乘法和加法计算，几个人可以同时进行，不会影响最后的结果
需要能够分解好问题，并确保几个人的结果能够汇总到一起
在“汇总”这个阶段，是没有办法并行进行的，还是得顺序执行，一步一步来

5.2 原则性的性能提升方法

加速大概率事件。最典型的就是，过去几年流行的深度学习，整个计算过程中，99% 都是向量和矩阵计算，于是，工程师们通过用 GPU 替代 CPU，大幅度提升了深度学习的模型训练过程。本来一个 CPU 需要跑几小时甚至几天的程序，GPU 只需要几分钟就好了。Google 更是不满足于 GPU 的性能，进一步地推出了 TPU
通过流水线提高性能。现代的工厂里的生产线叫“流水线”。可以把装配 iPhone 这样的任务拆分成一个个细分的任务，让每个人都只需要处理一道工序，最大化整个工厂的生产效率。类似的，CPU 其实就是一个“运算工厂”。把 CPU 指令执行的过程进行拆分，细化运行，也是现代 CPU 在主频没有办法提升那么多的情况下，性能仍然可以得到提升的重要原因之一
通过预测提高性能。通过预先猜测下一步该干什么，而不是等上一步运行的结果，提前进行运算，也是让程序跑得更快一点的办法

附录1: 系统芯片

我们手机里只有 SD 卡（Secure Digital Memory Card）这样类似硬盘功能的存储卡插槽，并没有内存插槽、CPU 插槽这些东西。没错，因为手机尺寸的原因，手机制造商们选择把 CPU、内存、网络通信，乃至摄像头芯片，都封装到一个芯片，然后再嵌入到手机主板上。这种方式叫SoC，也就是 System on a Chip（系统芯片）。

收起

展开全文

计算机组成原理

crout分解计算例题_矩阵与数值计算（2）——矩阵三角分解LU、PALU、Cholesky三角分解、QR分解...

千次阅读 2020-11-20 18:56:38

前言矩阵分解是设计算法的主要技巧，通过分解可以将复杂问题转化为几个简单问题求解，通常完成这一转化任务的主要技巧就是矩阵分解。例如，我们知道上三角矩阵和下三角矩阵是容易求解的，或者对角矩阵是最理想的求解...


 
 
  
 
 前言
 矩阵分解是设计算法的主要技巧，通过分解可以将复杂问题转化为几个简单问题求解，通常完成这一转化任务的主要技巧就是矩阵分解。例如，我们知道上三角矩阵和下三角矩阵是容易求解的，或者对角矩阵是最理想的求解形式，我们通过矩阵的分解去将原本的复杂问题，转化为若干个易于求解的矩阵来运算。
 一、高斯消去法与LU分解
 大学本科期间学校讲授的线性代数课程，关于Ax=b这类矩阵求解方式采用的是高斯消去法的方式（与高中阶段的多元一次方程求解方式一样）。而为我们矩阵分解打头阵的分解形式就是LU分解，那么这两种分解有什么区别呢？首先我们从这两种方法的计算复杂度角度逐渐切入问题的核心。
 我们这里默认你掌握线性代数的基本知识，那么高斯消去法的计算过程我们可以通过下面这个图片来进行概括。
 
 
  
 
 
  高斯消去法
 
 如果有这样一个问题
 
 
  
 
 我们通过高斯消元法，最后会得到一个这样的等价问题，
 
 
  
 
 这个高斯消去的过程如果写成矩阵相乘的过程，那么就如下所示，
 
 
  
 
 通过上图我们就得到了LU分解的基本形式，通过三个L矩阵对A进行行变换我们得到一个上三角矩阵，通过这个上三角矩阵U和三个行变换矩阵的乘积L，就得到了LU分解的定义。
 
 
  
 
 
  LU分解
 
 定义
 对于n阶方阵A，如果存在n阶单位下三角矩阵L和n阶上三角形矩阵U，使得A=LU，则称其为矩阵A的LU分解，也称为Doolittle分解。
 对于Gauss消去法和LU分解法的乘法计算计算量都是在 
 
   量级，这个就是分解过程的乘法计算量，推导过程可以模拟一下高斯消去法的整体过程，就可以得到如下的等式，
 
 
 
  
 
 
  高斯消去法乘法计算量
 
 详细推导过程不要求掌握，但是可以通过阅读教材或者参考资料的详细推导来了解这个过程。需要记住的是，分解过程始终是 
 
   量级，求解过程是 
 
 
 
   量级。
 
 
 那么一个Ax=b的问题，我们就可以转化为LU分解计算，主要分为三步
 A=LU 乘法量级 
   
    
   
Ly=b 乘法量级 
   
    
   
Ux=y 乘法量级 
   
    
   
 接下来我们通过一道题目来实战一下大家对其理解的如何：
 
 
  
 
 
  问题
 
 欢迎大家在评论区发表你的看法。
 以上我们基本明确了矩阵的LU分解过程。那么任意一个矩阵A的LU分解是否一定存在且唯一的呢？下面我们来分析LU分解的存在唯一性。
 由高斯消去法的步骤我们知道，如果想要不断的消去，则要求A在消去过程中的主对角线元素也就是主元 
 
   ，但是我们现在只能通过高斯法一步步来判断是否可继续执行高斯消去法。有没有更加便捷的方式帮助我们判断矩阵A是否可以进行LU分解呢？
 
 答案是可以。
 
 
  
 
 
 
  
 
 
  存在唯一性定理证明过程
 
 这样我们就把存在性和唯一性的问题转化为矩阵A的k阶主子式是否等于0的问题。如果A的主子式都不为零，那么矩阵A可以进行LU分解，且该分解唯一。
 二、Crout分解和LDU分解
 LDU分解其实很简单，只需要将LU分解简单变化即可。我们知道U是一个上三角矩阵，我们将其对角元元素提取出来形成一个对角矩阵D，则剩下的新的U和原来的L，其三者就组成了LDU分解。
 
 
  
 
 
  LDU分解
 
 如果把LD的乘积作为一个矩阵，我们就得到了Crout分解。
 
 
  
 
 
  Crout分解
 
 例题：通过LU分解求解矩阵的逆。
 
 
  
 
 
  求解矩阵的逆
 
 三、带主元的LU分解
 我们知道LU分解，要求主元不为0，假设我们遇到了主元为0的情况，LU分解就没有办法进行下去了。还会涉及误差的问题。LU分解有这样两个问题：
 有些有解的问题不能通过LU分解来求解
如果某些主元过小，会引入较大的误差。
 为了解决这两个问题，想到了选主元策略。每次进行消去操作的时候，我们要挑选一下主元，然后在进行操作。详细来说：
 ①第k列主元及主元以下元素中挑选绝对值最大的数。
 ②通过初等变换，使得该数位于主对角线上。
 我们取上述相同问题，前两步为例
 
 
  
 
 
  高斯列主元消去法
 
 初等行变换矩阵我们称之为P。这个带选主元的消去法，可以概括成下面的式子。
 
 
  
 
 进而我们得到矩阵列主元LU分解的定义。
 定义：对于任意n阶矩阵A，均存在置换矩阵P、单位下三角矩阵L和上三角矩阵U，使得PA=LU（P、L可以不同，分解不唯一）
 这里要说明几点：
 分解不唯一是因为选列主元的时候有可能两个或两个以上元素的绝对值相等，导致P的选取不唯一。
LU分解不一定存在，但是列主元LU分解一定存在。
LU分解必唯一，但列主元LU分解不一定唯一。
 四、正定矩阵的Cholesky分解
 正定矩阵的所有主子式都大于零，所以满足LU分解的条件，LU分解存在且唯一。假设 
 
   ，那么我们有 
 
 
   ，因为LU分解唯一，所以我们有 
 
 
   。
 
 接着有
 
 
  
 
 上面这个分解 
 
   就是Cholesky分解。这个分解可以套用公式进行计算。
 
 
 
  
 
 
  Cholesky分解
 
 上面的公式就是Cholesky分解的过程，直接套用公式可以得出分解矩阵，计算的数序以列序为主。
 实际考察中，一般掌握三阶矩阵的计算即可，不必记忆公式的详细细节。
 求解方程组时，可以将原问题转化为下面三个等式求解。
 
 
  
 
 五、三对角矩阵的三角分解
 三对角矩阵是一类特殊的矩阵，这种特殊矩阵的解法也不同于LU分解，这里提供其独特的解法。
 
 
  
 
 
  三对角矩阵LU分解
 
 分解成形如上图的两个矩阵LU，我们可以通过计算很容易得到l，u，d的值。
 计算次序为 
 
   。
 
 计算公式为：
 
 
  
 
 上述这种方法被称为追赶法。我们想要使用这种方法求解方程组还需要满足以下条件。
 
 
  
 
 
  对角占优
 
 LU分解是解决中小规模、稠密矩阵的最好方法。
 五、条件数与方程组的性态
 病态和良态
 如果线性方程组Ax=b中，A或b的元素的微小变化就会引起方程组的巨大变化，则称方程组为病态方程组，矩阵A称为病态矩阵。
 我们非常不希望这样的矩阵存在，那么如何去衡量这种病态程度呢？从相对误差入手进行分析。
 假设 
 
   ，那我们来看看A，b与x相对误差之间的关系。
 
 
 
  
 
 基于上面的推导，我们得到了条件数的定义，
 
 
  
 
 
  条件数
 
 条件数就可以看作是矩阵A作用下，将b的轻微扰动放大的倍数。因此通过条件数我们可以了解到矩阵A的病态程度。
 特别的，二条件数是矩阵A的A^HA的最大特征值与最小特征值的比值开根号。
 
 
  
 
 推导过程简单，这里略过。
 条件数的性质：
 非负性
非齐次 cond(aA) = cond(A)
满足相容性：cond(AB)≤cond(A)cond(B)
 
 
  
 
 接近奇异的矩阵一般是病态矩阵。
 系数矩阵和有段项均扰动
 即 
 
   ，同样我们分析x的相对误差有如下推导。
 
 
 
  
 
 解的余量与相对误差之间的关系
 我们称 
 
   为解的误差， 
 
 
   为解的余量。
 
 我们可以推导他们之间的关系：
 
 
  
 
 
 
   ，类似地我们还可以推出
 
 
 
  
 
 于是，有下列结论，
 
 
  
 
 条件数的几何意义，条件数用来刻画矩阵距离奇异的距离。
 
 
  
 
 
  条件数几何意义
 
 六、矩阵的QR分解
 矩阵的QR分解被评为20世纪十大算法，是所有与矩阵相关算法的底层算法。
 QR分解解决的问题是普通分解会导致分解后的条件数增大，我们根据条件数的相容性知道，分解后的条件数要大于等于原矩阵的条件数，为了解决这个问题，我们就用到条件数的第六条性质，关于酉矩阵的性质，于是我们想到通过酉矩阵或许会解决这个问题。
 QR分解和LU分解最大的区别就是使用了正交变换来实现矩阵分解。
 我们定义QR分解如下，
 
 
  
 
 
  QR分解
 
 为了实现QR分解，引入Householder矩阵，Householder矩阵作用到x向量上会将x向量变换到另一个正交的坐标系中，但是变换后的向量y的范数不变，此时x与y关于一个超平面对称，也称为镜面反射。
 
 
  
 
 经过推导我们得到Householder矩阵的求解公式
 
 
  
 
 
  Householder矩阵
 
 Householder矩阵的性质
 
 
  
 
 
  Householder矩阵的性质
 
 其中第四条性质，是因为求解出来的Householder矩阵的特征值应该为
 
   ，与单位矩阵做减法，得到的特征值为 
 
 
   。
 
 总结
 上述内容为矩阵三角分解相关的内容，这部分还是需要在题目中不断得到强化和锤炼。接下来将介绍特殊矩阵的特征系统，里面会介绍什么是Schur标准型，为Jordan分解和奇异值分解铺平道路。

收起

展开全文

图像分割综述
万次阅读 多人点赞 2019-07-09 22:03:48
这也就是说，在边缘点信息获取到之后还需要后续的处理或者其他相关算法相结合才能完成分割任务。在以后的研究当中，用于提取初始边缘点的自适应阈值选取、用于图像的层次分割的更大区域的选取以及如何确认重要边缘...
收起
图像分割
测试开发笔记
万次阅读 多人点赞 2019-11-14 17:11:58
测试开发笔记第一章测试基础 7 什么是软件测试： 7 ★软件测试的目的、意义：（怎么做好软件测试） 7 3.软件生命周期： 7 第二章测试过程 8 1.测试模型 8 H模型： 8 V模型 9 2.内部测试 10 ...
收起
测试开发
人工智能时代，所需要了解人工智能的基本常识
万次阅读 多人点赞 2018-12-10 22:49:44
计算机视觉技术运用由图像处理操作及其他技术所组成的序列来将图像分析任务分解为便于管理的小块任务。比如，一些技术能够从图像中检测到物体的边缘及纹理。分类技术可被用作确定识别到的特征是否能够代表系统已知的...
收起
人工智能
深度学习入门
万次阅读 多人点赞 2017-11-05 21:23:46
在这种方法论中，有一种“追本溯源”的蕴意包含其内，即一个系统（或理论）无论多复杂，都可以分解、分解、再分解，直到能够还原到逻辑原点。在意象上，还原主义就是“1+1=2”，也就是说，一个复杂的系统，...
收起
深度学习
任务拆分独立计算--ForkJoin
千次阅读 2018-03-17 13:21:59
任务拆分独立计算笼统的来讲就是一个大任务被分成若干个小任务，并行计算...2.他们的基本思想都是把问题分解为一个个彼此独立的或可分解的子问题分别进行计算，再合并结果。 MapReduce与ForkJoin的不同点：1.Map...
收起
ForkJoin
支持向量机
千次阅读 多人点赞 2016-07-18 23:04:15
支持向量机支持向量机点到平面的距离平面的一般式方程向量的模向量的内积点到平面的距离最优间隔分类器与支持向量函数间隔和几何间隔如何确定这个超平面最大间隔划分超平面 ...核函数有效性
收起
支持向量机
目标分解总结
千次阅读 2017-01-20 11:57:50
现在要做的就是这种,目标逐级分解,形成一个任务树. 分成任务表和任务成员表表结构任务表task Id Int 主键(自增) Sp_id Int 服务商id Shop_id Int...
收起
数据结构
推荐系统中的矩阵分解总结
万次阅读 多人点赞 2018-08-26 12:07:47
最近学习矩阵分解，但是学了好多种类，都乱了，看了这篇文章，系统性的总结了矩阵分解，感觉很棒，故分享如下: 前言推荐系统中最为主流与经典的技术之一是协同过滤技术（Collaborative Filtering），它是基于这样...
收起
推荐系统
偏差-方差分解（转）
2019-01-15 22:20:00
这里所说的偏差-方差分解就是一种解释模型泛化性能的一种工具。它是对模型的期望泛化错误率进行拆解。样本可能出现噪声，使得收集到的数据样本中的有的类别与实际真实类别不相符。对测试样本 x，另 yd为 x 在数据...
收起
利用音频分解技术处理音乐信号
2021-01-05 22:08:19
本文为德国埃尔兰根纽伦堡大学的博士论文，共184页。音乐信号很复杂。当音乐家们一起演奏时，他们的乐器声音叠加在一起形成一个单一的复杂声音混合体。...我们的核心思想之一是通过将一个给定的音乐信号分解..
收起
从线性回归看偏差-方差分解（Bias-Variance Decomposition）
千次阅读 2019-03-25 23:18:55
打开微信扫一扫，关注微信公众号【数据与算法联盟】转载请注明出处：... 概述对于数字序列1，3，5，7，？，正常情况下大家脑海里蹦出的是9，但是217314也是其一个解 9对应的数学公式为 f(...
收起
机器学习
非负矩阵分解与K-means聚类
千次阅读 2019-01-08 16:12:53
1. 对称非负矩阵分解(Symmetric NMF)与Kernel K-means聚类 1.1 Kernel K-means聚类假设数据的形式为一个m×n的矩阵X，n表示样本的个数，m表示一个样本的特征维度：聚成K个类，其中每个类的中心表示为： K-...
收起
聚类
极限学习机（ELM）从原理到程序实现（附完整代码）
万次阅读 多人点赞 2019-06-07 15:05:08
为了得到在训练样本集上具有良好效果的 β\betaβ，需要保证其训练误差最小，我们可以用 Hβ\mathrm{H} \boldsymbol{\beta}Hβ（Hβ是网络的输出，如公式（2.4））与样本标签 TTT求最小化平方差作为评价训练误差...
收起
极限学习机 ELM 机器学习神经网络 MATLAB
【机器学习－西瓜书】二、偏差-方差分解；泛化误差
千次阅读 2017-08-23 14:15:53
2.5偏差与方差关键词：偏差-方差分解；泛化误差。偏差-方差分解是解释算法泛化性能的一种重要工具。偏差-方差分解试图对学习算法的期望泛化错误率进行拆解。...噪声则表达了在当前任务上任何学习算法所
收起
机器学习
多任务学习-Multitask Learning概述
千次阅读 2020-05-07 08:38:55
单任务学习：一次只学习一个任务（task），大部分的机器学习任务都属于单任务学习。多任务学习：把多个相关（related）的任务放在一起学习，同时学习多个任务。多任务学习（multitask learning）产生的原因？ ...
收起
【机器学习】偏差-方差分解Bias-variance Decomposition
千次阅读 2018-08-28 11:52:16
偏差-方差分解(Bias-Variance Decomposition) 偏差-方差分解(Bias-Variance Decomposition)是统计学派看待模型复杂度的观点。Bias-variance分解是机器学习中一种重要的分析技术。给定学习目标和训练集规模，它可以...
收起
基于QR分解与Jacobi方法的SVD分解
千次阅读 2018-04-24 22:04:39
基于QR分解方法的SVD分解：矩阵的 SVD 分解并不唯一。主要的并行算法子程序都是基于经典求解矩阵奇异值的串行方法而实现的。基于 QR 迭代求解矩阵奇异值的方法，是求解双对角矩阵所有奇异值最快速的算法，求解出的...
收起
Jacobi方法
哥德巴赫猜想偶数公式的计算机验证
2020-03-12 04:45:01
哥德巴赫猜想偶数公式的计算机验证，庄严，庄宏飞，本文选用各种不同性质的偶数，对哥德巴赫猜想证明的最后结论，哥德巴赫猜想偶数公式进行了大范围验证对比，理论计算结果与客观实
收起
偏置方差分解Bias-variance Decomposition
万次阅读 2016-02-05 17:48:11
http://blog.csdn.net/pipisorry/article/details/50638749偏置-方差分解(Bias-Variance Decomposition)...Bias-variance 分解是机器学习中一种重要的分析技术。给定学习目标和训练集规模，它可以把一种学习算法的期
收起
机器学习
做事的常识，成功的公式
千次阅读 2016-08-15 07:06:22
目标拆分，形成工作分解清单。做法其实很简单：首先，把目标写出来。接下来，在目标下面写上完成这个目标需要做的事。如果事情还可以细分，就再多写一层，直到分到最小单位为止。一旦复杂的任务细分成...
收起
技术时间管理
深度学习（三十一）基于深度矩阵分解的属性表征学习
千次阅读 2016-03-13 12:07:24
本文提出一种无监督的学习方法，用于深度半非负矩阵分解，因为半监督非负矩阵分解和k均值聚类很相似，。本文的创新点：1、借助于深度学习的思想，提出贪婪的半非负矩阵分解方法，其思想与栈式自编码网络一样的训练...
收起
矩阵分解之: 特征值分解(EVD)、奇异值分解(SVD)、SVD++
千次阅读 2020-01-15 22:17:38
1.矩阵分解 1.1 矩阵分解的产生原因 1.2矩阵分解作用 1.3矩阵分解的方法 1.4推荐学习的经典矩阵分解算法 2. 特征值分解(EVD) 3. 奇异值分解(SVD) 4.SVD++ 5.SVD/SVD++在协同过滤中的应用 1. 矩阵分解...
收起
子带分解
2020-12-30 23:20:49
在语音信号处理中，通常使用STFT对信号进行分频带处理，，STFT公式表示如下 Y(m,w)=∑n=−∞+∞x(t)w(t−mD)e−jwt Y(m,w)=\sum_{n=-\infty }^{+\infty }x(t)w(t-mD)e^{-jwt} Y(m,w)=n=−∞∑+∞x(t)w(t−mD)e−...
收起
子带滤波 STFT
推荐系统入门（三）：矩阵分解MF&因子分解机FM（附代码）
千次阅读 2020-10-24 14:58:12
推荐系统入门（三）：矩阵分解MF&因子分解机FM（附代码）目录推荐系统入门（三）：矩阵分解MF&因子分解机FM（附代码）一、... FM公式的理解3. FM模型的应用4. 代码实践4.1 调包实现4.1.1 电影评分数据集实战4.
收起
1024程序员节机器学习推荐系统 pytorch 数据挖掘
多元线性回归中的公式推导
万次阅读 2018-04-03 11:34:38
至此，权值向量被样本集中的数据估计出来了，完成了学习任务，当然此处仍有有待解决的问题：方阵 X T X X T X \boldsymbol X^T\boldsymbol X 只有在满秩时才可逆，而这一条件并非所有学习任务均能满足，可以引进...
收起
解析BERT
千次阅读 2019-07-26 14:38:45
像BERT这样的预训练语言模型在许多自然语言处理任务中发挥着重要作用，例如问答，命名实体识别，自然语言推理，文本分类等等 BERT是一种基于微调的多层双向变压器编码器。此时，介绍Transformer架构非常重要。什么...
收起
BERT

机器学习实践案例算法总结
算法	算法描述/原理概述	适用的数据集类型	Python代码实现的主要步骤	优缺点说明
贝叶斯分类器	根据贝叶斯公式：P(cat\|item) = P(item\|cat)P(cat)/P(item), 其中，P(item\|cat) = P(feature\|cat)P(feature\|cat)P(feature\|cat)…	适应于所有能转换成一组特征列表的数据集。	1、定义特征提取函数getfeature 2、利用样本对分类器进行训练，得到记录了特征和某个特定分类相关联的数字概率P(feature\|(cat) 3、分类预测(朴素贝叶斯分类器)	优点： 1、训练和分类计算的速度快 2、支持增量式的训练 3、特征的概率值被保存，所以分类学习的解释相对简单缺点： 1、无法处理特征组合会产生分类结果影响的情况
决策树分类器	从根部开始构造决策树，在每一步中都会选择一个属性，利用该属性以最佳的可能方式对数据进行拆分。对于构造完成的决策树，从树的根部节点开始，对每一个节点的判断条件进行检查，走相应的yes or no 分支直至叶节点，即代表新数据的预测分类	适应于数值型或者名词性的有分类结果的数据集	1、创建决策树。熵、基尼不纯度衡量集合的混乱、不纯程度。信息增益来衡量一次拆分的好坏。 2、决策树剪枝 3、决策树显示--树状图/文本打印 4、决策树分类	优点： 1、易于对模型的解释和理解。重要的判断因素都在靠近根部的位置。 2、能处理变量之间的相互影响。缺点： 1、不擅长对数值结果的预测。 2、不支持增量式的训练。
神经网络
支持向量机SVM
K最近邻算法KNN	对一个待预测的新数据项，将其与已经知道结果值的数据项进行比较，从中找出最为接近的若干项，并根据距离远近求其加权平均值以得到最终的预测结果。	可以做数值预测的数据集	1、对变量进行缩放处理和交叉验证 2、给出一个距离度量算法/相似度度量算法 3、加权KNN算法预测	优点： 1、简单易懂 2、合理的数据缩放量不但可以改善预测效果，还能知道预测过程中各个变量的重要程度。3、新的数据可以随时被添加进来，是一种online的技术。缺点： 1、计算低效。每一个待预测项必须和所有其他数据进行比较。2、寻找合理的缩放因子的过程很乏味、计算和评估的计算工作量很大。
分级聚类	它是构造一颗由所有数据项构成的树的过程。工作方式：寻找两个距离最接近的数据项，将它们合二为一，新聚类的"位置"等于原两个数据项位置的均值。重复此过程，直到每个数据项都被包含在了一个大的聚类中为止。	任何一个具有一个或多个数值属性的数据集	1、给出一个相关系数度量方法 2、分级聚类 3、绘制分级聚类树状图	优点： 1、层级结构可以显示为树状图的形状，易于解读 2、面对一个全新的数据集，并不清楚想要多少群组时可通过分级聚类观察出哪些群组最接近
K-Means聚类	它是将数据拆分到不同群组的方法。工作方式：随机产生K个中心点的位置，将每个数据项都分配到距离最近的中心点。将中心位置移到分配给原中心点的所有项的平均位置处。重复上述聚类步骤。直到中心位置不再变化或达到某阈值。	任何一个具有一个或多个数值属性的数据集	1、给出想要的群组数量 2、给出一个相关系数度量方法 3、K-means聚类 4、打印分类群组结果	优点： 1、聚类得到的群组易于打印和识别
模拟退火算法	以一个随机推测的题解开始，以此为基准随机选择一个方向，找到另一个近似解，判断其成本值。如果新题解的成本值小，则替换原题解。如果成本值更大，则用概率觉得是否取代原题解。迭代至温度几乎为0时，返回题解。	给定定义域和成本函数的优化问题	1、确定变量定义域domain 2、定义成本函数costf
遗传算法	以一组种群题解开始，筛选出其中成本值最低的精英题解，利用变异、交叉的修改方法将精英题解扩充到原种群大小，称新得到的这个种群为下一代。迭代至一定代数或成本值达到某阈值或种群不再改变，返回成本值最低的作为最优解。	给定定义域和成本函数的优化问题	1、确定变量定义域domain 2、定义成本函数costf
非负矩阵因式分解NMF

Python机器学习实践

『矩阵论笔记』详细介绍矩阵的三角分解(LR分解)+平方根分解(Cholesky分解)！

文章目录

一. 三角分解(LR分解)

1.1. 方阵的两个重要分解

1.2. 上(下)三角阵的性质

1.3. 三角分解的概念

1.4. 三角分解的充要条件：定理1

二. 三角分解(LR分解)的求解

2.1. 三角分解的方法之高斯消元法

2.2. 带行交换的LR分解：定理2

2.3. 三角分解的方法之待定系数法

三. 平方根分解(Cholesky分解)

3.1. LDR分解的定义(预备知识)

3.2. 平方根分解(Cholesky分解)

3.3. 平方根分解的求解之高斯消元法

3.4. 平方根分解的求解之待定系数法

四. Cholesky分解用在计算马氏距离

4.1. 马氏距离

4.2. matlab实现计算马氏距离

参考文献

计算机组成原理-基本组成

计算机组成原理-基本组成

1 计算机组成原理知识地图

2 计算机的基本硬件组成

2.1 CPU: 中央处理器（Central Processing Unit）

2.2 内存: 内存（Memory）

2.3 主板: 主板（Motherboard）

2.4 I/O设备

2.5 特殊的设备

3 冯·诺依曼体系结构

3.1 First Draft 计算机组成部分

3.2 图灵与冯·诺依曼体系结构

4 计算机性能

4.1 响应时间

4.2 吞吐率

4.3 CPU 主频

5 功耗

5.1 阿姆达尔定律（Amdahl’s Law）

5.2 原则性的性能提升方法

附录1: 系统芯片

crout分解计算例题_矩阵与数值计算（2）——矩阵三角分解LU、PALU、Cholesky三角分解、QR分解...

前言

一、高斯消去法与LU分解

二、Crout分解和LDU分解

三、带主元的LU分解

四、正定矩阵的Cholesky分解

五、三对角矩阵的三角分解

五、条件数与方程组的性态

六、矩阵的QR分解

总结

图像分割综述

测试开发笔记

人工智能时代，所需要了解人工智能的基本常识

深度学习入门

任务拆分独立计算--ForkJoin

支持向量机

目标分解总结

推荐系统中的矩阵分解总结

偏差-方差分解（转）

利用音频分解技术处理音乐信号

从线性回归看偏差-方差分解（Bias-Variance Decomposition）

非负矩阵分解与K-means聚类

极限学习机（ELM）从原理到程序实现（附完整代码）

【机器学习－西瓜书】二、偏差-方差分解；泛化误差

多任务学习-Multitask Learning概述

【机器学习】偏差-方差分解Bias-variance Decomposition

基于QR分解与Jacobi方法的SVD分解

哥德巴赫猜想偶数公式的计算机验证

偏置方差分解Bias-variance Decomposition

做事的常识，成功的公式

深度学习（三十一）基于深度矩阵分解的属性表征学习

矩阵分解之: 特征值分解(EVD)、奇异值分解(SVD)、SVD++

子带分解

推荐系统入门（三）：矩阵分解MF&因子分解机FM（附代码）

多元线性回归中的公式推导

解析BERT

任务分解公式