第2章 线性代数与矩阵论

线性代数是多元函数微积分的基础，在机器学习和深度学习中扮演着重要角色，在图论、随机过程中被广泛应用。

2.1 向量及其运算

2.1.1 基本概念

向量（Vector）是具有大小和方向的量，是由多个数构成的一维数组，每个数称为向量的分量，分量的个数称为向量的维数。标量有大小无方向。

2.1.2 基本运算

• 转置（Transpose）：行列位置互换，$x^T$
• 加法：对应分量相加，满足交换律和结合律，平行四边形法则
• 数乘：标量与每个分量相乘，满足分配律
• 內积（Inner product）：对应分量乘积之和，$x\cdot y=x^Ty=\sum_{i=1}^n{x_iy_i}$
  $$
  \begin{align}
  x^Ty=y^Tx&,\qquad(Cx)^Ty=Cx^Ty\
  (x+y)^Tz=x^Tz+y^Tz&,\qquad z^T(x+y)=z^Tx+z^Ty
  \end{align}
  $$
• 正交（Orthogonal）：內积为0，正交是几何中垂直概念在高维空间的推广
• Hadamard积：对应分量相乘，结果为相同维数的向量，$x\odot y$。它可以简化问题的表述，在反向传播和各种梯度下降法中被使用。

2.1.3 向量的范数

向量的范数（Norm）是向量模长的推广，向量的L-p范数是一个标量，定义为
$$
|x|p=\left(\sum{i=1}^n|x_i|^p\right)^{1/p}
$$
常用的L1范数是绝对值之和，L2范数（Euclidean Norm）是向量的模长，两者被用于构造正则化项。

• 对于非0向量，通过数乘向量模的倒数可以将向量单位化（标准化）使其长度为1
• 当$p=\infin$时，称为$L-\infin$范数，$|x|_\infin=\max{x_i}$，是L-p范数的极限
• 柯西-施瓦茨Cauchy-Schwarz不等式：$x^Ty\leq|x|\cdot|y|$，L2范数
• 向量夹角计算公式：$\displaystyle{\cos\theta=\frac{x^Ty}{|x|\cdot|y|}}$
• 对于长度确定的两个向量，夹角为0时它们的內积最大，夹角为$\pi$时它们的內积最小。这一结论在梯度下降和最速下降法中使用。
• L2范数满足三角不等式：$|x+y|\leq|x|+|y|$
• 距离函数：满足非负性，对称性，三角不等式

2.1.4 解析几何

• 超平面（hyperplane）方程：$w^Tx+b=0$，$w$法向量
• 点到超平面的距离：$\displaystyle{d=\frac{|w^Tx+b|}{|w|_2}}$

2.1.5 线性相关性

• 线性组合（Linear Combination）：$x=C_1x_1+\cdots+C_nx_n$
• 如果存在不全为0的系数是的线性组合为零向量，则这组向量线性相关，否则线性无关（线性独立，Linear Independence）。线性相关意味着这组向量有冗余、最大线性无关的向量子集称为极大线性无关组

2.1.6 向量空间

• 向量空间（Vector space，线性空间）对集合内的向量加法和数乘运算封闭
• 向量空间的极大线性无关组称为空间的基，基所包含的向量个数称为空间的维数
• 基前面的系数称为这组基下的坐标，如果基向量相互正交称为正交基，长度为1的正交基称为标准正交基 格拉姆-施密特Gram-Schmidt正交化：通过向量投影构造垂直向量

2.1.8 应用–支持向量机

支持向量机（不考虑核函数）是线性分类器的特例，是最大化分类间隔的线性分类器。其目标是寻找一个分类超平面，它不仅能正确地分类每一个样本，并且要使得每一类样本中距离超平面最近的样本到超平面的距离尽可能远，这样有更好的泛化性能。

• 基于类别标签的约束：$\displaystyle{y_i(w^Tx_i+b)>0}$
• 超平面方程去冗余：$\displaystyle{\min_{x_i}{|w^Tx_i+b|=1}}$
• 多分类样本到超平面的距离：$\displaystyle{d(w,b)=\frac{N}{|w|}}$
• 两分类支持向量机求解优化问题可以写成：$\min{\frac{1}{2}w^Tw},\qquad y_i(w^Tx_i+b)\geq1$

2.2 矩阵及其运算

实矩阵、复矩阵、方阵、主对角线、对角矩阵（diag，$\Lambda$）、单位矩阵（$I$）、零矩阵、分块矩阵、格拉姆矩阵（Gram，其中的每个元素$G_{ij}$等于向量$x_i$和$x_j$的內积，是一个对称矩阵）

2.2.2 基本运算

• $(A+B)^T=A^T+B^T$
• 使用矩阵可以简化线性方程组的表述：$系数矩阵\times x=常数矩阵$，增广矩阵
• 矩阵乘法与转置满足穿脱原则：$(AB)^T=B^TA^T$

2.2.3 逆矩阵

逆矩阵对应于标量的倒数运算，对于$n$阶矩阵$A$，如果存在另一个$n$阶矩阵$B$，使得它们的乘积为单位矩阵，即$AB=I$

• 可逆矩阵也称为非奇异矩阵，不可逆矩阵也称为奇异矩阵。
• 如果矩阵可逆，则其逆矩阵唯一。
• 矩阵可逆的充分必要条件是满秩。
• $(AB)^{-1}=B^{-1}A^{-1}\qquad(A^{-1})^{-1}=A\qquad(A^T)^{-1}=(A^{-1})^T\qquad(\lambda A)^{-1}=\lambda^{-1}A^{-1}$
• 可通过初等行变换求矩阵的逆，即将$(A\ I)$转变成$(I\ A^{-1})$
• 如果一个方阵满足$AA^T=A^TA=I$则称为正交矩阵（orthogonal matrix）

矩阵的秩
对于$m\times n$矩阵$A$，秩为矩阵线性无关的行向量或列向量的最大数量。
$$
r(A)\leq\min(m,n)\qquad r(A)=r(A^T)\qquad r(A+B)\leq r(A)+r(B)\qquad r(AB)\leq\min(r(A),r(B))
$$

正交矩阵
正交矩阵的行向量均为单位向量且相互正交，构成标准正交基。正交矩阵的乘积、逆矩阵、转置，仍然是为正交矩阵。

2.2.4 矩阵的范数

矩阵$W$的范数定义为：$\displaystyle{|W|p=\max{x\neq0}\frac{|Wx|p}{|x|p}}$，该范数通过向量的$L-p$范数定义，称为诱导范数（induced Norm），几何意义是矩阵所代表的线性变换对向量进行变换后，向量长度的最大拉伸倍数。
谱范数（spectral norm）：$p=2,\qquad\displaystyle{|W|=\max{x\neq0}\frac{|Wx|}{|x|}}$
F范数（Frobenius norm）：$\displaystyle{|W|F=\sqrt{\sum{i=1}^m\sum{j=1}^n}w_{ij}^2}$，等价于向量的$L2$范数，将矩阵按行或列展开之后形成向量，然后计算$L2$范数。根据柯西不等式，对于任意$x$，$|Wx|\leq|W|_F\cdot|x|$。如果$x$为非零向量则F范数是谱范数的上界。

2.2.6 线性变换

矩阵与向量的乘法可以解释为线性变换（Linear transformation），它将一个向量变成另外一个向量。旋转变换是线性变换，其变换矩阵为正交矩阵；缩放变换是线性变换，其变换矩阵为对角矩阵。

2.3 行列式

行列式（Determinant，det）是对矩阵的一种运算，它作用于方阵，将其映射成一个标量。

2.3.1 行列式的定义与性质

$n$阶方阵$A$的行列式记为$|A|$或$det(A)$，称为$n$阶行列式，计算公式为：
$$|A|=
\begin{vmatrix}
a_{11}&a_{12}&\cdots&a_{1n}\
a_{21}&a_{22}&\cdots&a_{2n}\
\vdots&\vdots&\ddots&\vdots\
a_{n1}&a_{n2}&\cdots&a_{nn}\
\end{vmatrix}
=\sum_{j_1j_2\cdots j_n\in S_n}{(-1)^{\tau(j_1j_2\cdots j_n)}\prod_{i=1}^n{a_{i,j_i}}}$$
其中$S_n$是$n$个正整数所有排列构成的集合，显然有$n!$种；$\tau(\cdot)$为排列的逆序数，排列中所有逆序的数量成为排列的逆序数。

行列式可以表示平行四边形与平行六面体的有向面积和体积，也是线性变换的伸缩因子。如果将方阵看做线性变换，则其行列式的绝对值表示该变换导致的体积元变化系数。

拉普拉斯展开（Laplace Expansion）：一个行列式可以按照行或列进行递归展开。
$$|A|=a_{i1}A_{i1}+a_{i2}A_{i2}+\cdots+a_{in}A_{in}=a_{1j}A_{1j}+a_{2j}A_{2j}+\cdots+a_{nj}A_{nj}$$
其中$A_{ij}$是去掉矩阵$A$的第$i$行和第$j$列之后的$n-1$阶矩阵的行列式，并且带有符号$(-1)^{i+j}$。称$A_{ij}$为$a_{ij}$的代数余子式，不带符号的子行列式称为余子式。

• 存在一行或一列全为0的行列式值为0，对角矩阵的行列式值为对角线元素的乘积，单位矩阵的行列式值为1，上三角或下三角矩阵的行列式值为主对角线元素的乘积。
• 行列式具有多线性，可以按照某行或某列的线性组合拆分成两个行列式之和；如果把某一行元素都乘以$k$，则行列式变为之前的$k$倍；矩阵与标量乘法的行列式为$|\alpha A|=\alpha^n|A|$。
• 如果行列式的两行或列相等，那么行列式值为0。
• 如果$|A|\neq0$，则有$A\frac{1}{|A|}A^*=I$，因此$A^{-1}=\frac{1}{|A|}A^{}$；这也证明了矩阵$A$可逆的充分必要条件是$|A|\neq0$，$A^$为伴随矩阵。
• 如果矩阵$A$和$B$是尺寸相同的矩阵，则矩阵乘积的行列式等于行列式的乘积。

线性方程组

2.4.1 高斯消元法

Gaussian Elimination Method 通过将一个方程减掉另一个方程的倍数消除未知数，得到阶梯型方程组（利用初等变换将系数矩阵变成上三角矩阵）

2.4.2 齐次方程组

Homogeneous Linear Equations：齐次线性方程组是常数项为0的线性方程组，$Ax=0$ 齐次方程一定有解 （$x=0$）

• 如果$r(A)=n$，方程组只有0解
• 如果$r(A)<n$，方程组有非0解
• 如果$A$是方阵，$r(A)<n$等同于$A$不可逆
• 如果$x_1,\cdots,x_l$都是方程组的解，他们的任意组合$\sum_{i=1}^l{k_ix_i}$也是方程组的解：$\displaystyle{A\left(\sum_{i=1}^l{k_ix_i}\right)=\sum_{i=1}^lk_iAx_i=\sum_{i=1}^lk_i0=0}$；如果这组解线性无关且方程组的任意一个解都可以由他们线性表示，则称他们为方程组的一个基础解系
• 如果$r(A)<n$，则存在基础解系，且基础解系中包含$n-r(A)$个解

求解方法
对系数矩阵进行初等变换，在得到自由未知数时，将其设为特殊值形成基础解系，然后得到方程组的通解。例如：
$
\begin{cases}
x_1+2x_2+2x_3+x_4=0\
2x_1+x_2-2x_3-2x_4=0\
x_1-x_2-4x_3-3x_4=0
\end{cases}
$ $\rightarrow$ $
\begin{array}{cccc}
x_1&x_2&x_3&x_4\
\hline
1&0&-2&-5/3\
0&1&2&4/3\
0&0&0&0\
\end{array}$
令$x_3=1,x_4=0$，得基础解系的第一个解：$x_1=(2,-2,1,0)^T$
令$x_3=0,x_4=1$，得基础解系的第二个解：$x_2=(5/3,-4/3,0,1)^T$
方程组的通解为：$x=k_1x_1+k_2x_2$，其中$k_1,k_2$为任意常数

2.4.3 非齐次方程组

Non-homogeneous Linear Equations：常数项不全为0，$Ax=b$，（利用初等变换将增广矩阵$B$变成上三角矩阵）

• 如果$r(A)=r(B)$，那么方程组的解存在
• 如果$r(A)<r(B)$，那么方程组的解不存在
• 方程组有解的前提下，如果$r(A)=n$，那么方程组有唯一解；如果$r(A)<n$，那么方程组有无穷解
• 如果$x_1,\cdots,x_l$是非齐次方程组对应齐次方程组的基础解系，$x^*$是非齐次方程组的一个解，则$\sum_{i=1}^l{k_ix_i+x^*}$是非齐次方程组的解

求解方法
非齐次方程组的解为对应齐次方程组的通解加上非齐次方程组的一个特解（形如$x=x^*+k_1x_1+k_2x_2$），特解可以任意选取，通常令自由未知数的值全为0。

自由未知数：矩阵中元素全为0的行对应位置的未知数

2.5 特征值与特征向量 Eigenvalue Eigenvector

2.5.1 特征值与特征向量

对于$n$阶矩阵$A$，其特征向量是经过这个矩阵的线性变换之后仍然处于同一条直线上的向量（$Ax=\lambda x$），$\lambda$为特征值（是特征向量在矩阵的线性变换下的缩放比例），$x$为该特征值对应的特征向量，$A-\lambda I$为特征矩阵，$|A-\lambda I|=0$为特征方程，特征方程对应的行列式展开之后是$\lambda$的$n$次多项式，称为矩阵的特征多项式。

• 对角矩阵、上/下三角矩阵的特征值为主对角线元素
• 根据多项式分解定理，特征方程可以写成$\displaystyle{(\lambda-\lambda_1)^{n_1}(\lambda-\lambda_2)^{n_2}\cdots(\lambda-\lambda_{N_\lambda})^{n_{N_\lambda}}=0}$，其中$n_i$称为特征值$\lambda_i$的代数重数 Algebraic Multiplicity
• 所有$N_\lambda$个不同的特征值构成的集合称为矩阵的谱 Spectrum，其中特征值绝对值的最大值称为谱半径 Spectral Radius
• 求解方程组$(A-\lambda_i I)x=0$得其特征向量，有$1\le m_i\le n_i$个线性无关解，称$m_i$为$\lambda_i$的几何重数 Geometric Multiplicity
• 这些线性无关的解构成的空间称为矩阵$A$关于特征值$\lambda_i$的特征子空间，记为$V_{\lambda_i}$，维数为$m_i=n-r(A-\lambda_i I)$，属于不同特征值的特征向量线性无关，矩阵所有线性无关的特征向量的数量为$N_x=\sum_{i=1}^{N_\lambda}m_i$

阿贝尔-鲁菲尼（Abel-Ruffini）定理指出，4次以上的代数方程没有公式解。因此高阶矩阵的特征值只能求近似解，比起直接求解更好的办法是迭代法。

特征值与矩阵主对角线元素以及行列式的关系

• 矩阵的迹 Trace 定义为其主对角线元素之和：$tr(A)=\sum_{i=1}^n a_{ij}$
• 关于迹的公式：$tr(A+B)=tr(A)+tr(B)\qquad tr(kA)=k\cdot tr(A)\qquad tr(AB)=tr(BA)$

根据韦达定理，$n$次方程：$x^n+c_{n-1}x^{n-1}+\cdots+c_1x+c_0=0$ 所有根之和为：$x_1+x_2+\cdots+x_n=-c_{n-1}$ 所有根的乘积为：$x_1x_2\cdots x_n=(-1)^nc_0$

• 矩阵所有特征值的和为矩阵的迹：$\sum_{i=1}^n\lambda_{i}=tr(A)$
• 所有特征值的积为矩阵的行列式：$\prod_{i=1}^n\lambda_{i}=|A|$

特征值的重要性质

• 如果矩阵$A$可逆且$\lambda$为它的特征值，则$\lambda^{-1}$是$A^{-1}$的特征值
• 如果$\lambda$是$A$的特征值，则$\lambda^n$是$A^n$的特征值
• 如果$\lambda$是$A$的特征值，则$k\lambda$是$kA$的特征值
• 如果$\lambda$是$A$的特征值，则$f(\lambda)$是$f(A)$的特征值

特征向量的重要性质

• 如果一组向量是矩阵$A$关于同一个特征值$\lambda$的特征向量，则他们的非零组合仍是矩阵$A$关于$\lambda$的特征向量
• 实对称矩阵的特征值均为实数，属于不同特征值的特征向量相互正交

共轭矩阵

• $A=$ $\begin{pmatrix}
  1-i&1\
  1&1+i
  \end{pmatrix}$ $\rightrightarrows$ $\overline{A}=$ $\begin{pmatrix}
  1+i&1\
  1&1-i
  \end{pmatrix}$
• $\overline{A+B}=\overline{A}+\overline{B}\qquad\overline{kA}=k\overline{A}\qquad\overline{AB}=\overline{A}\ \overline{B}\qquad\overline{(AB)^T}=\overline{A}^T\ \overline{B}^T$

2.5.2 相似变换

如果有两个矩阵$A$、$B$以及一个可逆矩阵$P$满足 $P^{-1}AP=B$ 则称矩阵$A,B$相似，记为$A\sim B$，$P$为相似变换矩阵。
相似具有自反性（$A\sim{A}$）、对称性（$A\sim{B}\rightarrow B\sim{A}$）、传递性（$A\sim{B}, B\sim{C} \rightarrow A\sim{C}$）；相似矩阵有相同的特征值，意味着相似变换保持矩阵的特征值不变。
矩阵的相似对角化：$P^{-1}AP=\varLambda$ 可以以矩阵$A$的特征向量为列构造一个矩阵$P$，通过它将矩阵对角化，得到以$A$的特征值为主对角线的对角矩阵$\varLambda$。这种做法的成立条件是$P$可逆，即矩阵$A$有$n$个线性无关的特征向量。

2.5.3 正交变换 （一种特殊的相似变换）

实对称矩阵一定可以对角化，我们可以构造一个正交的相似变换将其对角化。实对称矩阵属于不同特征值的特征向量是相互正交的，如果用格拉姆-施密特正交化将同一个特征值的所有向量正交化，然后将所有特征向量单位化，可以得到一组标准正交基。以它们构造相似变换矩阵。则矩阵是正交矩阵（满足$P^{-1}=P^T$）。（$P^{T}AP=\varLambda$）正交变换具有一个优良的性质，它可以保持矩阵的对称性。

P的构造过程：求解矩阵A的所有特征向量，接着对其单位化，然后由这些向量组成矩阵P的列向量。

Householder变换：一种特殊的正交变换
Householder矩阵：$P=I-2\omega\omega^T=I-\frac{uu^T}{H},H=\frac{|u|^T}{2},u=x\mp|x|e_1$，其中$\omega$是n维非0列向量且有$|\omega|=1$，$u$为任意非0向量，$x$为n维列向量，$e_1=(1,0,\cdots,0)^T$，显然$P$是对称矩阵且是正交矩阵。
$$Px=(I-\frac{uu^T}{H})x=x-\frac{u}{H}(x\mp|x|e_1)x=x-\frac{2u(|x|^2\mp|x|x_1)}{2|x|^2\mp2|x|x_1}=x-u=\pm|x|e_1$$

• 根据上式特性，我们可以构造以Housholder矩阵为基础的正交变换，将矩阵转化为类似对角矩阵的形式，零化主对角线之外的元素（左乘$P$零化第一列，右乘$P$零化第一行）。
• 如果是对称矩阵，通过$n-2$次豪斯霍德尔变换可以将$A$化为对称三角矩阵 Tridiagonal Matrix，这种矩阵除主对角线及其上下对角线的元素外，其他元素均为0。
• 如果是一般的实数矩阵，由于不对称右乘无法完全零化，通过$n-2$次豪斯霍德尔变换可以将$A$化为上海森堡矩阵 upper-Hessenberg form，这种矩阵除主对角线及其以上和主对角线下面的一条对角线的元素外，其他元素均为0。

2.5.4 QR算法

QR分解：对于一个矩阵$A$，QR分解将其转化为一个正交矩阵$Q$与一个上三角矩阵$R$的乘积。
QR算法：一种迭代算法，从矩阵$A_0=A$开始，每次构造一个相似变换，将$A_{k-1}$变换成$A_k$，最后$A_k$收敛到一个上三角矩阵，主对角线元素即为其特征值。
QR迭代:$A_k=Q_kR_k\rightarrow A_{k+1}=R_kQ_k$，对于实对称矩阵$A$，QR迭代产生的所有正交矩阵$Q_k$的乘积的所有列列为$A$的特征向量。
加快收敛速度：
1、带位移的QR算法，迭代公式为$A_k-s_kI=Q_kR_k\rightarrow A_{k+1}=R_kQ_k+s_kI$
2、Householder变换将$A$化成三角矩阵

2.5.5 广义特征值

Generalized Eigenvalue 是特征值的推广，定义于两个矩阵之上，对于方阵$A$和$B$，如果存在一个数$\lambda$及非0向量$x$，满足$Ax=\lambda Bx$，则称$\lambda$为广义特征值，$x$为广义特征向量；如果矩阵$B$可逆，则$B^{-1}Ax=\lambda x$，广义特征值在机器学习中被广泛应用，包括流形学习、谱聚类算法、以及线性判别分析等。

2.5.6 瑞利商 Rayleigh Quotient

• $\displaystyle{R(A,x)=\frac{x^TAx}{x^Tx}}$：定义为方阵$A$和非0向量$x$的瑞利商，对于任意的非0实数$k$，有$R(A,kx)=R(A,x)$，即对向量缩放之后其瑞利商不变，瑞利商存在冗余。
• $x^Tx=1$：增加约束确保解的唯一性，消除冗余。
• $\lambda_{min}\le R(A,x)\le\lambda_{max}$：瑞利商的所有极值在矩阵的特征值与特征向量处取得（拉格朗日乘数法证明），在最大特征值处，瑞利商有最大值，最小特征值处有最小值。（其典型应用是主成分分析）
• $\displaystyle{R(A,B,x)=\frac{x^TAx}{x^TBx}}$：广义瑞利商的性质和瑞利商基本一致，存在冗余，将向量$x$缩放后瑞利商不变；可以增加约束消除冗余$x^TBx=1$。
• $\displaystyle{\frac{x^TAx}{x^TBx}=\frac{((C^T)^{-1}y)^TA((C^T)^{-1}y)}{((C^T)^{-1}y)^TCC^T((C^T)^{-1}y)}=\frac{y^TC^{-1}A(C^T)^{-1}y}{y^Ty}}$：如果令$B=CC^T$（对矩阵$B$的楚列斯基Cholesky分解），$x=(C^T)^{-1}y$，则可以将广义瑞利商转化为瑞利商。（线性判别分析的优化目标函数就是广义瑞利商）

2.5.7 谱范数与特征值的关系

矩阵$W$的谱范数等于的$W^TW$最大特征值的平方根，即$W$最大的奇异值

（$|W|_2=\max{[\sigma_1, \cdots, \sigma_n]}$）；

谱范数的平方为瑞利商的最大值（$\displaystyle{|W|2^2=\max{x\ne0}=\frac{x^TW^TWx}{x^Tx}}$）。

2.5.8 条件数

如果矩阵$W$可逆，条件数定义为它的范数与它的逆矩阵范数的乘积（可以是任意范数），$cond(W)=|W|\cdot|W^{-1}|$。条件数总是大于等于1的，它决定了矩阵的稳定性，条件数越大则矩阵越接近不可逆矩阵，矩阵越ill-posed。如果使用谱范数，则条件数等于矩阵的最大奇异值与最小奇异值的比值。

2.5.9 应用——谱归一化与谱正则化

谱正则化 Spectral Regularization：正则化是机器学习中减轻过拟合的技术，它迫使模型的参数值很小，是模型变得更简单（一般地，简单的模型有更好的泛化性能，奥卡姆剃刀？）。谱正则化用谱范数构造正则项。
谱归一化 Spectral Normalization：通过谱范数对线性映射的矩阵进行谱归一化来确保映射有较小的利普希茨常数，从而保证机器学习模型对输入数据的扰动不敏感。

示例 神经网络$f(x)=Wx+b$ 如果映射满足Lipschitz条件（将其推广到多元函数，绝对值改为向量的范数），则有$|Wx_1+b-Wx_2+b|=|Wx_1-Wx_2|\le K|x_1-x_2|$，假设权重矩阵的谱范数为$\sigma(W)$，归一化后$W_{SN}=W/\sigma(W)$，然后用谱范数做正则项有目标函数：
$$\frac{1}{N}\sum_{i=1}^N{L(x_i,y_i)}+\frac{\lambda}{2}\sum_{i=1}^l{\sigma(W_i)^2}$$
其中$L(x_i,y_i)$为单样本损失函数，为神经网络层数，为对应层权重矩阵；谱正则项由神经网络所有层权重矩阵的谱范数平方和构成，可以防止权重矩阵出现大的谱范数，从而保证神经网络的映射有较小的Lipschitz常数。

2.6 二次型

二次型是一种特殊的二次函数，只含有二次项。

2.6.1 基本概念

• Quadric Form 二次型是由纯二次项构成的函数，即二次齐次多项式，可以写成矩阵形式：$x^TAx$，其中$A$是$n$阶对称矩阵，$x$是一个列向量。
• 二次型对应的矩阵：平方项$ax^2$的系数是矩阵的主对角线元素，交叉乘积项$ax_ix_j$的系数由$a_{ij}$与$a_{ji}$均分。实对称矩阵与二次型一一对应

示例 二次型 $2x^2-3xy+y^2+z^2$ 对应的矩阵为 $\begin{pmatrix}
2&-1.5&0\
-1.5&1&0\
0&0&1\
\end{pmatrix}$

2.6.2 正定二次型与正定矩阵

如果一个二次型对于任意非0向量$x$都有$x^TAx>0$，则称该二次型为正定（Positive Definite）二次型，矩阵$A$为正定矩阵；如果对于任意非0向量$x$都有$x^TAx\ge0$，则称该二次型为半正定（Positive Semi-definite）二次型，矩阵$A$为半正定矩阵；对于任意非0向量$x$都有$x^TAx<0$，则称该二次型为负定（Negative Definite）二次型，矩阵$A$为负定矩阵，类似地可以定义半负定；如果不正定也不负定就称为不定。正定二次型被用于多元函数极值的判定法则 正定矩阵所有主对角线元素大于0

证明对称矩阵$A$正定可以按照定义进行，也可以：

1. 矩阵$A$的$n$个特征值$\lambda_1,\cdots,\lambda_n$均大于0：通过正交变换将二次型华为标准型证明。
2. 存在可逆矩阵$P$使得$A=P^TP$：因为可逆，任意非0向量$x$有$Px\neq0$，$x^TAx=x^TP^TPx=(Px)^T(Px)>0$
3. 如果$A$是正定矩阵，则$A^T$也是正定矩阵：$(x^TA^Tx)^T=x^TAx>0$
4. 矩阵$A$的所有顺序主子式均为正：顺序主子式是矩阵左上角的子方阵形成的行列式

对于任意的$m\times n$矩阵$A$，$A^TA$是对称半正定矩阵，$AA^T$也是对称半正定矩阵。

实对称负定：

1. 矩阵$A$的$n$个特征值$\lambda_1,\cdots,\lambda_n$均小于0
2. 存在可逆矩阵$P$使得$A=-P^TP$
3. 矩阵$A$的所有奇数顺序主子式均为负，偶数顺序主子式均为正

2.6.3 标准型

标准型指对于任意的$i\neq j$，二次型中项$a_{ij}x_ix_j$的系数均为0，二次型由纯平方项构成，形如 $x^TAx=d_1x_1^2+\cdots+d_nx_n^2$。标准型对应的矩阵为对角矩阵 在标准型中，正平方项的个数称为正惯性指数，负平方项的数量为负惯性指数。 二次型的矩阵为对称矩阵，因此一定可以对角化 对于二次型$x^TAx$，通过正交变换将$A$化为对角矩阵$A=P\Lambda P^T$，从而有$x^TAx=x^TP\Lambda P^Tx=(P^Tx)^T\Lambda(P^Tx)$，$P$是正交矩阵，如果令$y=P^Tx$，则$y^T\Lambda y$是标准型。

2.7 矩阵分解

2.7.1 楚列斯基分解Cholesky

对于$n$阶对称半正定矩阵$A$，Cholesky分解将其分解为$n$阶下三角矩阵$L$以及其转置的乘积：$A=LL^T$。如果$A$是实对称正定矩阵，则分解唯一。Cholesky分解还可以用于检查矩阵的正定性，如果一个矩阵不能进行Cholesky分解则说明矩阵不是半正定矩阵，否则为半正定矩阵。

2.7.2 QR分解

QR分解（正交三角分解）将矩阵$A$分解为正交矩阵$Q$与上三角矩阵$R$的乘积，QR分解是格拉姆-施密特正交化的另外一种表现形式。

1. 对于任意$n$阶方阵：$A=QR$
2. 对于非方阵，$m>n$：$A=QR=Q\begin{pmatrix}R_n \ 0_{(m-n)\times n}\end{pmatrix}$
3. 对于非方阵，$m<n$：$A=QR=Q\begin{pmatrix}R_m&B_{m\times(n-m)}\end{pmatrix}$，$B$是一个$m\times(n-m)$的矩阵
4. QR分解的三种实现方式：格拉姆-施密特正交化、豪斯霍尔德变换、吉文斯旋转

2.7.3 特征值分解

又称为谱分解，是矩阵相似对角化的另一种表现形式，对于$n$阶方阵$A$，如果它有$n$个线性无关的特征向量，则可将其分解为：$A=Q\varLambda Q^{-1}$。

1. 其中$\varLambda$为对角矩阵，对角线元素是$A$的特征值；$Q$的列为$A$的特征向量
2. 分解充分必要条件：它有$n$个线性无关的特征向量
3. 如果$A$可以进行特征值分解，且所有特征值都非0，则$A^{-1}=Q\varLambda^{-1}Q^{-1}$
4. 如果$A$可以进行特征值分解，则$f(A)=Qf(\varLambda)Q^{-1}$

2.7.4 奇异值分解SVD

SVD是特征值分解的推广（思路是对$AA^T$和$A^TA$进行特征值分解），对于任意矩阵均可用特征值与特征向量进行分解：$A=U\Sigma V^T$

1. $U$为$m$阶正交矩阵，其列为矩阵$A$的左奇异向量，也是$AA^T$的特征向量
2. $\Sigma$为$A$的奇异值，是$AA^T$特征值的非负平方根，也是$A^TA$特征值的非负平方根
3. $V$为$n$阶正交矩阵，其列为矩阵$A$的右奇异向量，也是$A^TA$的特征向量

几何意义
向量左乘任意矩阵所实现的线性变换可以分解成三次变换$Ax=U\Sigma V^Tx$：首先是$V^T$代表的旋转变换，接着是$\Sigma$代表的拉伸变换，最后是$U$代表的旋转变换。