矩阵计算与矩阵分解

矩阵范数和矩阵求导术以后完成

在线性代数和矩阵论都已经学过，这里只写一些常用的

基本计算

$(AB)^T=B^TA^T$

$(AB)^{-1}=B^{-1}A^{-1}$

$A^{-1}A=AA^{-1}=I$

$(A^T)^{-1}=(A^{-1})^T$

$(ABC)^T=C^TB^TA^T$
对称矩阵$A$。协方差矩阵、核矩阵、Hessian矩阵都是对称矩阵

有$A_{ij}=A_{ji}$

$A=A^T$，$A^{-1}$也是对称矩阵

一般情况下，矩阵的特征值是复数。但是对于对称矩阵，特征值$\lambda_i$为实数。
正交矩阵$A$：$AA^T=A^TA=I$

即矩阵中的各个组成向量/维度相互正交
高斯消元（略）
矩阵的逆

如何求逆（略）

对于可逆矩阵$A$，有$AA^{-1}=A^{-1}A=I$

正交矩阵的逆等于其转置矩阵：$A^{-1}=A^T$
特征向量方程：$Ax=\lambda x,\quad x$为特征向量；使得该式成立的$\lambda$称为矩阵$A$的特征值，为常数

该表达式的特征方程为$|\lambda I-A|=0$

通过特征方程可解得特征向量和特征值
矩阵对角化

定义：若满足$S^{-1}AS=Λ,\quadΛ$为一个对角矩阵，则此式子称为矩阵$A$的对角化。

$Λ$称为$A$的特征值矩阵，其对角线上的元素为$A$的所有特征值；

$S$称为$A$的特征向量矩阵，其每一列都由$A$的特征向量构成。（证略）

（矩阵对角化不唯一）

另一种表示：通过左右乘可表示为$A=S\Lambda S^{-1}$

正交对角化：只要满足①$S$为正交矩阵且②$S^{-1}AS=Λ$，那么$S^{-1}AS=Λ$就叫$A$的正交对角化。此时$S^{-1}=S^T$，见性质-5。（矩阵对角化的方式不止此一种，比如下面的SVD也是正交对角化一种方法）

于是$S^{-1}AS=S^TAS=Λ$，或表示为$A=S\Lambda S^{-1}=S\Lambda S^T$。

[矩阵的特征值分解]求解正交对角化：

①一般就先用特征方程求得特征值$\lambda_1,\lambda_2,\cdots,\lambda_n$和对应特征向量$x_1,x_2,\cdots,x_n$，由特征值作为对角线元素得到$\Lambda$，即$\Lambda=diag(\lambda_1,\lambda_2,\cdots,\lambda_n)$。此时求得的特征向量还未正交标准化。

②于是再对特征向量进行施密特正交化和单位化得到正交且标准的特征向量。$S$即由特征向量组成（特征向量的每一列即为$S$矩阵的每一列/每个向量），$S$中个每特征向量都正交。

③$A=S\Lambda S^{-1}$，此即一种正交对角化，也叫$A$的特征值分解

可对角化条件：求得特征值和特征向量，$A$的每个特征值对应的齐次线性方程组的基础解系所含向量个数等于特征值的重数（注意每个重根虽然特征值相同，但是不同的特征值）；矩阵不一定能对角化，但对称矩阵一定能对角化。

实对称矩阵A的属于不同特征值的特征向量一定是正交的。（所以对于实对称矩阵的不同特征值对应的特征向量就不用再求施密特正交化了，只需要单位化）
行列式

行列式仅适用于方阵

$|AB|=|A||B|$

$|A^{-1}|=\frac{1}{|A|}$

克莱姆法则解线性方程组（略）

$|A_{M×M}|=\prod_{i=1}^M \lambda_i=A$的对角化矩阵$\Lambda$的对角线元素之积
秩等价空间维度等价独立变量等价无关变量等价正特征值数量
正定矩阵和半正定矩阵

半正定矩阵：$A∈\mathbb R^{n×n},x∈\mathbb R^n$，对任意$x$，$x^TAx≥0$恒成立

正定矩阵：$A∈\mathbb R^{n×n},x∈\mathbb R^n$，对任意$x$，$x^TAx＞0$恒成立
一些等式

$(P^{-1}+B^TR^{-1}B)^{-1}B^TR^{-1}=PB^T(BPB^T+R)^{-1}$

$(I+AB)^{-1}A=A(I+BA)^{-1}$

Woodybury恒等式：$(A+BD^{-1}C)^{-1}=A^{-1}-A^{-1}B(D+CA^{-1}B)^{-1}CA^{-1}$

都可以用左乘/右乘逆矩阵的逆推得
正交基变换

$X$为原矩阵下的向量（坐标），$X=(\mathbb x_1,\mathbb x_2,\cdots,\mathbb x_n)$，有$n$个原基下的$\mathbb x$向量

$A$为正交基矩阵 $A=(a_1,a_2,\cdots,a_m)$，其中的每个向量就是一个新的基，新基是相互正交的

$\mathbb x_i和a_j$都是$m$维列向量，$\mathbb x_i$代表原基下的一个向量/坐标，那么
$Y=A^TX$
即为基变换，新基下的向量为$Y=(\mathbb y_1,\mathbb y_2,\cdots,\mathbb y_n)$

$\mathbb y_i$也是$m$维列向量，代表经过基矩阵$A$变换后新基下的坐标

也可以半展开写成：（这里转置易错，见13）
$(\mathbb y_1,\mathbb y_2,\cdots,\mathbb y_n)=(a_1,a_2,\cdots,a_m)^T(\mathbb x_1,\mathbb x_2,\cdots,\mathbb x_n)$ $=\begin{bmatrix} a_1^T\\ a_2^T\\ \vdots\\ a_m^T\\\end{bmatrix} \begin{bmatrix}\mathbb x_1,\mathbb x_2,\cdots,\mathbb x_n\end{bmatrix} =\begin{bmatrix} a_1^T\mathbb x_1&a_1^T\mathbb x_2&\cdots&a_1^T\mathbb x_n\\ a_2^T\mathbb x_1&a_2^T\mathbb x_2&\cdots&a_2^T\mathbb x_n\\ \vdots&\vdots&\ddots&\vdots\\ a_m^T\mathbb x_1&a_m^T\mathbb x_2&\cdots&a_m^T\mathbb x_n\\ \end{bmatrix}$
在该基变换中，每一个旧基下的向量$\mathbb x_i$都左乘了基矩阵$A$ ，也就是：
$\mathbb y=A^T\mathbb x$
如果只有一个向量$x$做基变换，那便是：
$\mathbb y=(a_1,a_2,\cdots,a_m)^T\mathbb x=\begin{bmatrix} a_1^T\\ a_2^T\\ \vdots\\ a_m^T\\\end{bmatrix}\mathbb x= \begin{bmatrix} a_1^T\mathbb x\\ a_2^T\mathbb x\\ \vdots\\ a_m^T\mathbb x\\ \end{bmatrix} =(a_1^T\mathbb x,a_2^T\mathbb x,\cdots,a_m^T\mathbb x)^T$
展开列向量$\mathbb y$中的每一个维度表示：即$y_i=a_i^T\mathbb x=a_1x_1+a_2x_2+\cdots+a_mx_m$

这样变换的原理：

可以看出变换得到的新基下的变量的每个维度都由基矩阵的一个列向量也就是一个基与原基下的变量内积得到，新向量的一个维度为基矩阵的一个基与原基变量的内积，就是上面这个式子

而内积的几何意义是：向量$A与B$的内积实质上就是$A$到$B$的投影长度乘以$B$的模，如果$B$为单位向量，那么$A与B$的内积就是$A$到$B$上的投影，也就是向量$\mathbb x$在新基组$(a_1,a_2,\cdots,a_m)$下的投影，也就得到了新基下的坐标/向量表示：$\mathbb y$。原基下的向量$\mathbb x$被投影到了每一个新基($a_i$)上，组成了新基下的向量表示（坐标）：$\mathbb y$。

用图表示关系就是

各个颜色的变换就是内积，就是一次原基下的向量表示到某一个新基的投影过程

举例，对于一般的二维笛卡尔直角坐标系中，其基为$a_1=(0,1)^T,a_2=(1,0)^T$，其正交基矩阵就是

$A=\begin{bmatrix}a_1,a_2\end{bmatrix}=\begin{bmatrix} 0&1\\1&0 \\ \end{bmatrix}$，对于本来就在笛卡尔坐标系下的向量$\mathbb x$,自然$\mathbb x=A^T\mathbb x$，新基和原基没变，那向量表示（坐标）自然也没变

基变换的本质：投影
注意转置简写矩阵的时候易错

（设定$a$为向量）

$(a_1,a_2,\cdots,a_m)^T=\begin{bmatrix} a_1^T\\ a_2^T\\ \vdots\\ a_m^T\\\end{bmatrix}$

外面那层转置只是转置了外层的列，每列内部还没有进行转置，所以要这样！
内积的几何意义

向量$A与B$的内积实质上就是$A$到$B$的投影长度乘以$B$的模，如果$B$为单位向量，那么$A与B$的内积就是$A$到$B$上的投影

奇异值分解

定义

singular value decomposition ，SVD

将一个非零的$m×n$实矩阵$A,A∈\mathbb R^{m×n}$，表示为三个实矩阵乘积形式的运算：

$A=U\Sigma V^T$

其中$U$为$m$阶正交矩阵，$V$为$n$阶正交矩阵，$\Sigma$是由降序排列的非负的对角线元素组成的$m×n$矩形的对角矩阵

$A=U_{m×m}\Sigma_{m×n}V^T_{n×n}$ $①UU^T=I,②VV^T=I,③\Sigma=diag(\sigma_1,\sigma_2,\cdots,\sigma_p),④\sigma_1≥\sigma_2≥\cdots≥\sigma_p≥0,⑤p=\min(m,n)$

$\sigma_i$称为矩阵$A$的奇异值，$U$的列向量称为左奇异向量，$V$的列向量称为右奇异向量

紧奇异值分解：分解得到的对角矩阵$\Sigma$的秩与原式矩阵$A$的秩相等，即$rank(A)=rank(\Sigma)$

截断奇异值分解：分解得到的对角矩阵$\Sigma$的秩小于原式矩阵$A$的秩，即$rank(A)>rank(\Sigma)$

（可以看出截断奇异值分解损失了信息）

性质

若$A$为实矩阵，则奇异值分解存在（证明用构造法，为$A$依次构造$U和V$，略）
几何意义：任意一个向量$x∈\mathbb R^n$，经过基于$A=U\Sigma V^T$的线性变换，等价于向量$x∈\mathbb R^n$经过坐标系的旋转或反射变换$V^T$，坐标轴的缩放变换$\Sigma$，以及坐标轴的旋转或反射变换$U$，得到向量$Ax∈\mathbb R^m$
设矩阵$A$的奇异值分解为$A=U\Sigma V^T$，则

$A^TA=(U\Sigma V^T)^T(U\Sigma V^T)=V(\Sigma^T\Sigma)V^T$

$AA^T=(U\Sigma V^T)(U\Sigma V^T)^T=U(\Sigma\Sigma^T)U^T$

（推导）直接乘即可推导

由于$U,V$是正交矩阵，则右边的式子$V(\Sigma^T\Sigma)V^T$就是$A^TA$的正交对角分解，$AA^T$同理（因为根据计算-7，对于正交矩阵$V$满足$V^T=V^{-1}$，于是$A^TA=V(\Sigma^T\Sigma)V^{-1}$，根据定义这就是正交对角分解）

于是，矩阵$AA^T和A^TA$的[正交对角分解存在]且可以由[$A$的奇异值分解]的三个矩阵表示。由这个性质可以推出奇异值分解的计算方法。
奇异值，左奇异向量，右奇异向量之间的关系

[A]通过定义式$A=U\Sigma V^T$可得右乘$V$得$AV=V\Sigma$，则：

$Av_j=\sigma_ju_j,\quad j=1,2,\cdots,n$，[于是当$\sigma≠0,u_j=\frac{Av_j}{\sigma_j},\quad j=1,2,\cdots,n$]

[B]由$A^T=(U\Sigma V^T)^T=V\Sigma^T U^T,\therefore A^TU=V\Sigma^T$，则：

①$A^Tu_j=\sigma_jv_j,\quad j=1,2,\cdots,n$

②$A^Tu_j=0,\quad j=n+1,n+2,\cdots,m$，[于是当$\sigma=0,A^Tu_j=0,\quad j=n+1,n+2,\cdots,m$]
奇异值唯一，$U,V$不唯一
$rank(A)=rank(\Sigma)=[正]奇异值的个数$

奇异值分解的计算

由性质3，我们发现了$A^TA$的奇异值可以由$A$的奇异值分解得到的三个矩阵$U,\Sigma,V$表示，即:

$A^TA=V(\Sigma^T\Sigma)V^T$

于是存在对应关系：$V$的列向量是$A^TA$的特征向量；$\Sigma$的奇异$A^TA$的特征值的平方根。于是我们想到借助求解$A^TA$的特征向量和特征值求得$\Sigma,V$(性质3)，再借助$A=U\Sigma V^T$的关系求得$U$（性质4）。

步骤：

首先求$A^TA$的特征值和特征向量

$W=A^TA$，解特征方程$|\lambda I-W|=0$
求$n$阶正交矩阵$V$

上面特征方程解后单位正交化后的特征向量构成$V$

由于$W=A^TA$为实对称矩阵，其不同特征值对应的特征向量正交，对这样的特征向量不用再求施密特正交化了，只需要单位化
求$m×n$阶对角矩阵$\Sigma$

$\sigma_i=\sqrt{\lambda_i},\quad i=1,2,\cdots,n$

求得对角矩阵后要加上零行向量以便于与$U,V$相乘计算
求$m$阶正交矩阵$U$

根据性质4总结：①当$\sigma≠0,u_j=\frac{Av_j}{\sigma_j},\quad j=1,2,\cdots,n$，得到$U_1$（对于正奇异值，直接用[A]求）

②当$\sigma=0,A^Tu_j=0,\quad j=n+1,n+2,\cdots,m$，转变为求$A^T$零空间的一组标准正交基：$A^Tx=0$，求得的一组标准正交基$x$即是$u$，得到$U_2$（对于零奇异值，不能用①求了，于是用[B]方法求）

$U=[U_1\quad U_2]$
得到奇异值分解$A=U\Sigma V^T$

在实际运用中不直接求$W=A^TA$，而是通过求$A^TA$的特征值进行

SVD与矩阵近似（证略）

佛罗贝尼乌斯范数（F范数）：$A∈\mathbb R^{m×n},A=[A_{ij}]_{m×n}$，则定义矩阵$A$的佛罗贝尼乌斯范数为：
$||A||_F=(\sum_{i=1}^m\sum_{j=1}^n(a_{ij}^2))^{\frac{1}{2}}$
引理：$A$的奇异值分解为$A=U\Sigma V^T,\quad \Sigma=diag(\sigma_1,\sigma_2,\cdots,\sigma_n)$，则：
$||A||_F=(\sigma_1^2+\sigma_2^2+\cdots+\sigma_n^2)^{\frac{1}{2}}$
F范数实际上就是衡量这个矩阵和对应的零矩阵的距离，就像二维平面上的一个点，和原点的距离就是它的f范数，那么下面的$A-X$其实就是衡量$A$到$X$的距离，也就是近似程度

定理1：设矩阵$A∈\mathbb R^{m×n}$，矩阵的秩$rank(A)=r$，并设$\mathbb M$为$\mathbb R^{m×n}$中所有秩不超过$k$的矩阵的集合，$0＜k＜r$，则存在一个秩为$k$的矩阵$X∈\mathbb M$使得
$||A-X||_F=\min_{S∈\mathbb M}||A-S||_F$
称矩阵$X$为矩阵$A$的佛罗贝尼乌斯范数意义下的最优近似。这里秩不超过$k$的矩阵也就是要用一个低秩矩阵去近似高秩原矩阵。证明了存在，那什么样的矩阵才是最优解呢？答案：SVD。见下。

定理2：设矩阵$A∈\mathbb R^{m×n}$，矩阵的秩$rank(A)=r$，有奇异值分解$A=U\Sigma V^T$，并设$\mathbb M$为$\mathbb R^{m×n}$中所有秩不超过$k$的矩阵的集合，$0＜k＜r$，若秩为$k$的矩阵$X∈\mathbb M$满足
$||A-X||_F=\min_{S∈\mathbb M}||A-S||_F$ $则||A-X||_F=(\sigma_{k+1}^2+\sigma_{k+2}^2+\cdots+\sigma_{n}^2)^{\frac{1}{2}}$
特别地，若$A’=U\Sigma’V^T$，其中
$\begin{bmatrix} {\sigma_1}&{}&{}&{}\\ {}&{\sigma_2}&{}&{}\\ {}&{}&{\ddots}&{}\\ {}&{}&{}&{0}&{}&{}\\ {}&{}&{}&{}&{\ddots}&{}\\ {}&{}&{}&{}&{}&{0}\\ \end{bmatrix} = \begin{bmatrix} {\Sigma_k}&{0}\\ {0}&{0} \end{bmatrix}$ $则||A-A'||_F=(\sigma_{k+1}^2+\sigma_{k+2}^2+\cdots+\sigma_{n}^2)^{\frac{1}{2}}=\min_{S∈\mathbb M}||A-S||_F$
定理2表明了在秩不超过$k$的$m×n$矩阵的集合中，存在矩阵$A$的佛罗贝尼乌斯范数意义下的最优近似矩阵$X$。

$A’=U\Sigma’V^T$是达到最优值的一个矩阵，也就是说=>【通过SVD求得的这个矩阵就是最优近似矩阵】<=这是这里的核心，也就说明了可以用SVD求得低秩矩阵去近似原矩阵。且奇异值分解是在平方损失（佛罗贝尼乌斯范数）意义下对矩阵的最优近似，即最优的数据压缩

利用外积展开式对矩阵$A$进行近似——截断奇异值分解

对于秩为$n$的原矩阵$A=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_nu_nv_n^T$

于是其近似矩阵可以取为秩为$k$的矩阵$A=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_ku_kv_k^T$

这里其实就是取奇异值矩阵从大到小排列的奇异值的前$k$个，在第$k$个奇异值处截断，剩下的奇异值行全部删掉，见下面的截断奇异值分解的详细描述。这就是截断奇异值分解，是一种最优化的有损压缩。

截断奇异值分解：

截断奇异值分解得到的矩阵秩为$k$，通常远小于原始矩阵的秩$r$，所以是由低秩矩阵实现了对原始矩阵的压缩（近似）。具体地说就是：奇异值矩阵中的奇异值是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说，我们也可以用最大的$k$个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：

$A_{m×n}=U_{m×m}Σ_{m×n}V^T_{n×n}≈U_{m×k}Σ_{k×k}V^T_{k×n}$。其中$k$要比$n$小很多，也就是一个大的矩阵$A$可以用三个小的矩阵$U_{m×k},Σ_{k×k},V^T_{k×n}$来表示，对应于上面的$A’=U\Sigma’V^T$。其秩低于原矩阵的秩。

这种近似是在佛罗贝尼乌斯范数意义下的最优近似，其在1中已经给出了

应用

紧奇异值分解是在佛罗贝尼乌斯范数意义下的无损压缩

截断奇异值分解是在佛罗贝尼乌斯范数意义下的有损压缩

由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪。

也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。

同时也可以用于NLP中的算法，比如潜在语义索引（LSI）。

奇异值分解与特征值分解的区别

特征值分解可以看作一个空间到自身的映射，奇异值分解可以看作一个空间到另一个空间的映射。

奇异值分解把线性变换清晰地分解为旋转、缩放、投影这三种基本线性变换，特征值分解是对旋转和缩放两种效应的归并。

由于奇异值关于不同的基（两组基），所以可以扩展到任意线性变换，而特征值则只能描述线性算子。

可以看知乎这一篇：矩阵的奇异值与特征值有什么相似之处与区别之处？ - 赵文和的回答 - 知乎 https://www.zhihu.com/question/19666954/answer/54788626

矩阵范数

非负性
$||\alpha A||=|\alpha|·||A||$
$||A+B||≤||A||+||B||$
$||A||_1=\max_j \sum_{i=1}^m|a_{ij}|$
$||A||_2=\sqrt{\lambda_i}\quad,\lambda_i为A^HA的最大特征值$
$||A||_{∞}=\max_i \sum_{j=1}^n |a_{ij}|$

对于向量$x,||x||_2=(\sum_{i=1}^nx_i^2)^{\frac{1}{2}}$

矩阵求导术

向量$\vec a$关于标量$x$的导数也是个向量，其分量为：$(\frac{\partial \vec a}{\partial x})_i=\frac{\partial a_i}{\partial x}$

同理，向量$x$关于矩阵$a$的导数为：$(\frac{\partial x}{\partial a})_i=\frac{\partial x}{\partial a_i}$

向量$a$关于向量$b$的导数为$(\frac{\partial a}{\partial b})_{ij}=\frac{\partial a_i}{\partial a_j}$，也就是分子的每个分量对分母的每个分量求导

实质上就是多元微分，其结果为向量/矩阵

$x$为向量，$a$为向量，$\frac{\partial x^Ta}{\partial x}=a$

证明：设$x=[x_1,x_2,\cdots,x_n],a=[a_1,a_2,\cdots,a_n],\therefore x^Ta=[x_1a_1,x_2a_2,\cdots,x_na_n]$

$\therefore \frac{\partial x^Ta}{\partial x}=\frac{\partial[x_1a_1,x_2a_2,\cdots,x_na_n]}{\partial [x_1,x_2,\cdots,x_n]}$，然后根据$(\frac{\partial a}{\partial b})_{ij}=\frac{\partial a_i}{\partial a_j}$：

$\frac{\partial x^Ta}{\partial x}=\frac{\partial x_ia_i}{\partial x_j}=[a_1,a_2,\cdots,a_n]=a$

后记

向量/矩阵在计算的时候一定要注意形态和下标！