【Math for ML】矩阵分解(Matrix Decompositions) (上)

2018/12/20 21:42
阅读数 23

I. 行列式(Determinants)和迹(Trace)

1. 行列式(Determinants)

为避免和绝对值符号混淆,本文一般使用$det(A)$来表示矩阵$A$的行列式。另外这里的$A∈R^{n×n}$默认是方阵,因为只有方阵才能计算行列式。

行列式如何计算的就不在这里赘述了,下面简要给出行列式的各种性质和定理。

定理1:当且仅当一个方阵的行列式不为0,则该方阵可逆。 定理2:方阵$A$的行列式可沿着某一行或某一列的元素展开,形式如下:

  • 沿着第$i$行展开:$$det(A)=\sum_{k=1}^n(-1)^{k+i}a_{ik}det(A_{i,k})$$
  • 沿着第$i$列展开:$$det(A)=\sum_{k=1}^n(-1)^{k+i}a_{ki}det(A_{k,i})$$ 定理3:当且仅当一个方阵为满秩时,该方阵行列式不为0,即可逆。

2. 迹(Trace)

矩阵的迹是矩阵对角元素之和,即 $$tr(A)=\sum_{i=1}^na_{ii}$$

有如下性质:

  • $tr(A+B)=tr(A)+tr(B)$
  • $tr(αA)=\alpha tr(A),\alpha∈R$
  • $tr(I_n)=n$
  • $tr(ABC)=tr(BCA)=tr(=CAB)$
  • $tr(AB)=tr(BA), A∈R^{n×m},B∈R^{m×n}$

II. 特征值(Eigenvalue)&特征向量(Eigenvector)

1. 特征值与特征向量定义:

对于一个给定的矩阵 $A∈R^{n×n}$,它的特征向量$v$ 经过这个线性变换之后,得到的新向量仍然与原来的 $v$保持在同一条直线上,但其长度或方向也许会改变。即 $$Av=\lambda v$$ 则$\lambda ∈R$是矩阵$A$的特征值,$v$是对应的特征向量

设$λ=λ_i$是矩阵$A$的一个特征值,则有方程$(A-λ_iv)x=0$,可求得非零解$x=p_i$即为$λ_i$对应的特征向量。(若$λ_i$为实数,则$p_i$可取实向量;$λ_i$为复数,则$p_i$可取复向量)

  • 推论 设n阶矩阵$A=(a_{ij})$的特征值为$λ_1,...,λ_n$,不难证明:

    • 1)$λ_1+..+λ_n=a_{11}+...+a_{nn}$
    • 2)$λ_1λ_2...λ_n=|A|$

    由2)可知$A$是可逆矩阵的充要条件是它的n个特征值全不为0.

  • 定理

设$λ_1,...,λ_n$是方阵$A$的n个特征值,$p_1,...,p_n$依次是对应的特征向量,如果$λ_1,...,λ_n$各不相等,则$p_1,...,p_n$线性无关。

2. 特征空间(Eigenspace)和特征谱(Eigenspectrum) 定义

由特征值$\lambda$及其对应的特征向量$v$所span的空间称为特征空间 ,用$E_{\lambda}$表示。矩阵$A$的特征值集合称为特征谱。

下面给出两个定理,后面内容很多都是基于它们推导出来的。

  • (Hogben(2006)): 一个n阶方阵$A$如果有n个不同的特征值,那么对应的n个特征向量互相线性独立。
  • (Meyer(2000)): 任何n阶对称矩阵都有n个独立且正交的特征向量

3. 图解特征向量和特征值

下面使用二维图像的变换来帮助我们直观理解特征值和特征向量的意义。一共给出了两个示例,最左边表示原数据,中间表示不同特征值对应的特征向量方向(<span style="color:red;">红色</span>表示$λ_1$对应的特征向量,<span style="color:blue;">蓝色</span>表示$λ_2$对应的特征向量),最右边表示经过矩阵变换后得到的新的矩阵,该矩阵反应了特征向量和特征值是如何影响变换的。

  • 第一个例子

$$ A_1=\left[ \begin{matrix} 0.5 & 0 \ 0 & 2 \ \end{matrix} \right] $$

简单计算后可求出特征值和与之对应的特征向量分别为:

  • $λ_1=0.5:p_1=[1,0]^T$
  • $λ_2=2,,,,,:p_2=[0,1]^T$
  • $tr(A)=\sum_{i=1}^n \lambda_i$

可以看到最后得到的新的矩阵$A_1x$沿着特征矩阵的方向伸缩,伸缩比例恰巧等于对应特征值大小。

image.png

$$ A_4=\left[ \begin{matrix} 1 & -1 \ -1 & 1 \ \end{matrix} \right] $$

简单计算后可求出特征值和与之对应的特征向量分别为:

  • $λ_1=0:p_1=[1,1]^T$
  • $λ_2=2,,,,,:p_2=[-1,1]^T$

可以看到最后得到的新的矩阵$A_1x$沿着特征矩阵的方向伸缩,伸缩比例恰巧等于对应特征值大小。

image.png

关于特征值,特征矩阵等概念更直观,更透彻的理解可以参看文末【理解矩阵】系列文章,这系列文章用非常浅显易懂的语言解释了什么是矩阵,行列式和向量。

III. 平方根法(Cholesky decomposition)

一种矩阵运算方法,又叫Cholesky分解。所谓平方根法,就是利用对称正定矩阵的三角分解得到的求解对称正定方程组的一种有效方法。它是把一个对称正定的矩阵表示成一个下三角矩阵L和其转置的乘积的分解。它要求矩阵的所有特征值必须大于零,故分解的下三角矩阵的对角元也是大于零的。公式如下: $$ \begin{align} A&=LL^T \notag \ \Leftrightarrow \left[ \begin{matrix} a_{11} & \cdots &a_{1n} \ \vdots & \ddots &\vdots \ a_{n1} & … &a_{nn} \ \end{matrix} \right] &= \left[ \begin{matrix} l_{11} & \cdots &0 \ \vdots & \ddots &\vdots \ l_{n1} & … &l_{nn} \ \end{matrix} \right] \left[ \begin{matrix} l_{11} & \cdots &l_{n1} \ \vdots & \ddots &\vdots \ 0 & … &l_{nn} \ \end{matrix} \right] \notag \end{align} $$ 其中$L$又称为Cholesky因子。

这里不会详细介绍该方法的计算方法,简单说明一下该方法会带来哪些好处。

1.求逆矩阵

我们都知道求一个矩阵的逆矩阵是一个非常耗时的过程,而对于一个上(下)三角矩阵而言,求逆矩阵就简单很多。假设我们已经将矩阵$A$分解,那么有 $$A^{-1}=(LL^T)^{-1}=(L^{-1})^T(L^{-1})$$

2.求行列式

$$det(A)=det(L)^2=\prod_i{l_{ii}^2}$$

IV. 特征分解(Eigendecomposition)&对角化(Diagonalization)

1. 对角矩阵&相似矩阵

常见的对角矩阵形式如下: $$ \begin{align} D= \left[ \begin{matrix} c_1 & \cdots & 0 \ \vdots & \ddots & \vdots \ 0 & \cdots & c_n \notag \end{matrix} \right] \end{align} $$

注意:对角矩阵不一定是方阵,但是为了方便解释默认用对角方阵来说明。

很明显对角矩阵相对于其他形式的矩阵天然有很多计算上的优势,例如计算逆矩阵,行列式时都非常简单,所以如果能把一个矩阵对角化,那么很多问题就可以解决了。

在介绍矩阵对角化之前简单回复一下相似矩阵(similar matrix) 的概念,即

如果存在一个可逆矩阵$P$使得两个矩阵$A,D$满足$D=P^{-1}AP$,那么则称$A,D$相似。

2. 可对角化(Diagnolizable)

  • 定义 所以可对角化(Diagnolizable) 可定义如下:

如果一个矩阵$A$和一个对角矩阵相似,则称$A$可对角化。也就是说如果存在一个可逆矩阵$P$使得两个矩阵$A,D$满足$D=P^{-1}AP$,且$D$为对角矩阵,那么则称$A$可对角化。

  • 对角化条件 那么什么时候才能对角化呢?答案在下面的特征值分解/对角化定理中:

当且仅当方阵$A∈R^{n×n}$满秩(即有n个独立的特征向量)时,有 $$A=PDP^{-1}$$ 其中$P$是由$A$的特征矩阵组成的可逆矩阵,$D$是由$A$的特征值组成的对角矩阵。

  • 亏损矩阵 基于上面的介绍,很自然地给出亏损矩阵(defective matrix) 的定义:

n阶矩阵$A$若有n个线性无关的特征向量(n个特征值也要各不相同),称$A$为非亏损矩阵,即$A$有完备的线性无关的特征向量系。反之称$A$为亏损矩阵

  • 对称矩阵对角化

任何对称矩阵都可以对角化,即 $$ \begin{align} S&=PDP^{-1} \notag\ &=PDP^T \notag \end{align} $$ 其中$P$是由n个正交特征向量组成的矩阵(此时有$P^{-1}=P^T$,证明略),$D$是特征值组成的对角矩阵

下图直观地给出了对称矩阵对角化的过程:

上图可划分成四个部分,按顺时针顺序分别简称为LT(Left-Top),RT(Right-Top),LB(Left-Bottom),RB(Right-Bottom)。

LT的$p_1,p_2$表示矩阵$A∈R^{2×2}$的单位特征向量(长度为1)。

  • LT→RT:单位圆按照$A$特征向量的方向伸缩,伸缩比例等于$A$的特征值大小。因为$A$的对称矩阵,所以其特征向量是互相独立且正交的,由图可以清楚地看到$p_1⊥p_2$;
  • LT→LB: 因为$A$的对称矩阵,所以有$P^T=P^{-1}$,所以可以$P^T$理解成将坐标轴体系由$p_1,p_2$坐标体系逆向还原成传统的$e_1,e_2$坐标体系。所以矩阵的本质其实也可以理解成对坐标轴的变换,这个观点相信你在看了文末给出的【理解矩阵】系列文章后会有更深刻的理解。
  • LB→RB: 如果上面的介绍你理解了,那么这一过程也就很自然地能够理解了。没错,该步骤就表示在将坐标轴还原到传统意义上的坐标轴后对LB的单位圆按照特征值大小进行伸缩。
  • RB→LT: 对坐标轴进行变换。

参考


<footer style="color:white;;background-color:rgb(24,24,24);padding:10px;border-radius:10px;"><br> <h3 style="text-align:center;color:tomato;font-size:16px;" id="autoid-2-0-0"><br> <b>MARSGGBO</b><b style="color:white;"><span style="font-size:25px;">♥</span>原创</b><br> <br><br> <br><br> <b style="color:white;"><br> 2018-12-18<p></p> </b><p><b style="color:white;"></b><br> </p></h3><br> </footer>

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部