二次型

二次型是一种特殊的二次函数，只含有二次项，它在线性代数与多元函数微积分中被广泛使用

在机器学习中二次型经常作为目标函数出现

基本概念

二次型(Quadric Form) 是由纯二次项构成的函数，即二次齐次多项式，如下面的函数

二次型可以写成矩阵形式

其中$\boldsymbol{A}$是$n$阶对称矩阵，$\boldsymbol{x}$是一个列向量，上面的二次型展开之后为

这里要求，需要注意的是，一般的二次函数不一定是二次型，它可能有一次项和常数项

上式的二次型对应的矩阵为

平方项的系数是矩阵的主对角线元素，交叉乘积项的系数由与均分，实对称矩阵与二次型一一对应

正定二次型与正定矩阵

在某些数学证明或计算中，会将二次函数配方成完全平方的形式以得到想要的结果，如下面的例子

平方项是非负的，$(2,-5,7)$是该函数的极小值，由此引入二次型和矩阵正定的概念，如果一个二次型对于任意非$\boldsymbol{0}$向量$\boldsymbol{x}$都有

则称该二次型为正定(Positive Definite)二次型，矩阵$\boldsymbol{A}$为正定矩阵，如果对于任意非$\boldsymbol{0}$向量$\boldsymbol{x}$都有

则该二次型为半正定(Positive Semi-definite)二次型，矩阵$\boldsymbol{A}$为半正定矩阵，如果对于任意非0向量$\boldsymbol{x}$都在

则该二次型为负定(Negative Definite)二次型，矩阵$A$为负定矩阵，类似地可以定义半负定的概念

如果既不正定也不负定，则称为不定

下面的二次型为正定二次型

其对应的矩阵为正定矩阵

下面的二次型为半正定二次型

其对应的矩阵为半正定矩阵

如果令，二次型的值为0

下面的二次型是负定二次型

其对应的矩阵为负定矩阵

正定二次型被用于多元函数极值的判定法则

正定矩阵的所有主对角线元素$a_{i i}>0，i=1，\cdots，n$

根据正定的定义，由于对于任意非0向量$\boldsymbol{x}$都有$\boldsymbol{x}^{\mathrm{T}} \boldsymbol{A} \boldsymbol{x}>0$，因此可以构造一个第$i$个分量为1，其他分量均为0的向量$\boldsymbol{x}$

则有

因此结论成立

证明一个对称矩阵$\boldsymbol{A}$正定可以按照定义进行，除此之外，还可以采用下面的方法

  1. 矩阵的个特征值均大于0
  2. 存在可逆矩阵$\boldsymbol{P}$使得$\boldsymbol{A}=\boldsymbol{P}^{\mathrm{T}} \boldsymbol{P}$
  3. 如果$\boldsymbol{A}$是正定矩阵，则$\boldsymbol{A}^{\mathrm{T}}$也是正定矩阵
  4. 矩阵$\boldsymbol{A}$的所有顺序主子式均为正

第一条判定规则可以通过正交变换将二次型化为标准型证明，化为标准型(对应于对角矩阵)之后为正定二次型

下面证明第2条判定规则，对于任意曲$\boldsymbol{\theta}$向量$\boldsymbol{x}$在

因为$P$可逆，对于任意非$\boldsymbol{0}$向量$\boldsymbol{x}$有$\boldsymbol{P x} \neq \mathbf{0}$

下面证明第3条判定规则，如果$A$是正定矩阵，对于任意非0向量$x$都有$x^{\mathrm{T}} A \boldsymbol{x}>0$，对于任意非$\boldsymbol{0}$向量$\boldsymbol{x}$有

对于$n$阶矩阵$A$

其前$k, 1 \leqslant k \leqslant n$行前$k$列元素形成的行列式

称为顺序主子式，这是矩阵左上角的子方阵形成的行列式，对于下面的4阶矩阵

其1阶顺序主子式为

2阶顺序主子式为

3阶顺序主子式为

4阶顺序主子式为

矩阵$A$不是正定的，因为其二阶顺序主子式为负

对于任意的$m \times n$矩阵$\boldsymbol{A}$，$\boldsymbol{A}^{\mathrm{T}} \boldsymbol{A}$是对称半正定矩阵，下面给出证明，显然该矩阵是对称的

对于任意非$\boldsymbol{0}$向量$\boldsymbol{x}$，有

类似地可以证明$\boldsymbol{A A ^ { \mathrm { T } }}$也是对称半正定矩阵

在机器学习中，这种矩阵经常出现，如向量组的格拉姆矩阵，包括线性回归、支持向量机以及logistic回归等线性模型

它们目标函数的黑塞矩阵为这种类型的矩阵，因此是凸函数，可以保证求得全局极小值点

类似地，实对称矩阵负定可以通过下面的方法进行判定

  1. 矩阵的个特征值均小于0
  2. 存在可逆矩阵$\boldsymbol{P}$使得$\boldsymbol{A}=-\boldsymbol{P}^{\mathrm{T}} \boldsymbol{P}$
  3. 矩阵$A$的所有奇数阶顺序主子式均为负，偶数阶顺序主子式均为正

标准型

标准型指对于任意的，二次型中项的系数均为0，二次型由纯平方项构成，可写成如下形式

下面是一个标准型

标准型对应的矩阵为对角矩阵，上面的标准型对应的矩阵为

在标准型中，正平方项的数量称为正惯性指数，负平方项的数量称为负惯性指数

上面的标准型的正惯性指数为2，负惯性指数为1

由于二次型的矩阵为对称矩阵，因此一定可以对角化

通过正交变换可以将二次型化为标准型，与实对称矩阵的正交变换对角化相同

对于二次型$x^{\mathrm{T}} A \boldsymbol{x}$，通过正交变换将$A$化为对角矩阵

从而有

这里$\boldsymbol{P}$是正交矩阵，如果令$\boldsymbol{y}=\boldsymbol{P}^{\mathrm{T}} \boldsymbol{x}$或者$\boldsymbol{x}=\boldsymbol{P} \boldsymbol{y}$，则$\boldsymbol{y}^{\mathrm{T}} \boldsymbol{A} \boldsymbol{y}$是标准型

这对应于通过将$\boldsymbol{x}$换元为$y$，使得换元之后的二次型为标准型

如果矩阵的个特征值均大于0，则矩阵正定

对于任意非0向量$x$，由于$P$是正交矩阵，$y=P^{\mathrm{T}} x \neq 0$，因此$A$正定

下面举例说明，对于下面的二次型

其对应的系数矩阵为

特征多项式为

解得特征值为$0,5,6$

当$\lambda=5$时，有

方程$(A-\lambda I) x=0$的解为

当$\lambda=6$时，有

方程$(A-\lambda I) x=0$的解为

当$\lambda=0$时，有

方程$(A-\lambda I) x=0$的解为

由于二次型的系数矩阵是实对称矩阵，其不同特征值对应的特征向量相互正交，因此只需要将这些特征向量单位化即可

令

通过正交变换$x=\boldsymbol{P y}$可将二次型化为如下的标准型

矩阵分解

矩阵分解是矩阵分析的重要内容，这种技术将一个矩阵分解为若干矩阵的乘积，通常为2个或3个矩阵的乘积

在求解线性方程组，计算逆矩阵、行列式以及特征值，多重积分换元等问题上，矩阵分解有广泛的应用

楚列斯基分解

对于$n$阶对称半正定矩阵$\boldsymbol{A}$，楚列斯基(Cholesky)分解将其分解为$n$阶下三角矩阵$L$以及其转置$L^{\mathrm{T}}$的乘积

如果$A$是实对称正定矩阵，则上式的分解唯一

下面是对称矩阵楚列斯基分解的一个 例子

楚列斯基分解可用于求解线性方程组，对于如下的线性方程组

如果$A$是对称正定矩阵，它可以分解为$L L^{\mathrm{T}}$，则有

如果令

则可先求解线性方程组

得到$y$。然后求解

得到$x$，这两个方程组的系数矩阵分别为下三角和上三角矩阵，均可高效地求解

在实际应用中，如果系数矩阵$A$不变而常数向量$b$会改变，则预先将$A$进行楚列斯基分解，每次对于不同的$b$均可高效地求解

在求解最优化问题的拟牛顿法中，需要求解如下的方程组

其中为第次迭代时的黑塞(Hessian)矩阵的近似矩阵，为牛顿方向，为第次迭代时的梯度值

此方程可以使用楚列斯基分解求解

楚列斯基分解还可以用于检查矩阵的正定性

对一个矩阵进行楚列斯基分解，如果分解失败，则说明矩阵不是半正定矩阵；否则为半正定矩阵

下面以3阶矩阵为例推导楚列斯基分解的计算公式，如果

则有

首先可以得到主对角的第一个元素

根据$l_{11}$可以得到第2行的所有元素

进一步得到第3行的元素

所有元素逐行算出，首先计算出第1行的元素，然后计算第2行的元素，接下来计算，依此类推

这里与有关，这些值已经被算出

对于$n$阶矩阵，楚列斯基分解的计算公式为

Python中linalg的cholesky函数实现了对称正定矩阵的楚列斯基分解

函数的输入是被分解矩阵$\boldsymbol{A}$，输出为下三角矩阵$\boldsymbol{L}$

1
2
3
4
5
import numpy as np

A = np.array([[6,3,4,8],[3,6,5,1],[4,5,10,7],[8,1,7,25]])
L = np.1inalg.cholesky(A)
print(L)

程序输出结果为

1
2
3
4
[[2.44948974  0.0         0.0         0.0 ],
 [1.22474487  2.12132034  0.0         0.0],
 [1.63299316  1.41421356  2.30940108  0.0],
 [3.26598632  -1.41421356 1.58771324  3.13249102]]

可以验证矩阵$\boldsymbol{L}$与其转置的乘积即为矩阵$\boldsymbol{A}$

QR 分解

QR分解(正交三角分解)将矩阵分解为正交矩阵与上三角矩阵的乘积，这种分解被广泛地应用于求解某些问题，如矩阵的特征值

事实上，$\mathrm{QR}$分解是格拉姆-施密特正交化的另外一种表现形式

首先考虑方阵的情况，对于任意的$n$阶方阵$\boldsymbol{A}$，$\mathrm{QR}$分解将其分解为一个$n$阶正交矩阵$\boldsymbol{Q}$与一个$n$阶上三角矩阵$\boldsymbol{R}$的乘积

如果矩阵$\boldsymbol{A}$可逆且要求矩阵$\boldsymbol{R}$的主对角元为正，则上式的分解唯一

如果$\boldsymbol{A}$有$m(m \leqslant n$) 个线性无关的列，则$\boldsymbol{Q}$的前$m$个列构成$\boldsymbol{A}$的列空间的标准正交基

下面来看$\mathrm{QR}$分解的实际例子，对于如下矩阵

其$\mathrm{QR}$分解的结果为

下面考虑非方阵的情况，对于$m \times n, m>n$的矩阵$\boldsymbol{A}$，QR 分解将其分解为一个$m$阶正交矩阵与如下形式的$m \times n$矩阵$\boldsymbol{R}$的乘积

其中$\boldsymbol{R}_{n}$是$n$阶上三角矩阵，$\boldsymbol{0}$是一个$(m-n) \times n$的零矩阵。 如果$m<n$, 则分解的结果为

其中$\boldsymbol{Q}$是一个$m$阶正交矩阵，是阶上三角矩阵，是一个的矩阵

$\mathrm{QR}$分解有 3 种实现方式

分别是格拉姆-施密特正交化、豪斯霍尔德变换以及吉文斯(Givens)旋转

下面介绍格拉姆-施密特正交化以及豪斯霍尔德变换

考虑$A$为$n$阶方阵的情况，使用格拉姆-施密特正交化技术对矩阵$A$的列进行正交化，将矩阵$\boldsymbol{A}$按列分块

假设这些列向量线性无关，首先将它的列正交化

然后进行单位化

$A$的各个列向量在标准正交基下的坐标为其在各个基向量上的投影，由于在进行格拉姆-施密特正交化时只与有关

因此在方向的投影均为0，有

写成矩阵形式为

令，以及

$Q$的列是用$A$的列构造的标准正交基，$R$的第$i$列为$\boldsymbol{A}$的第$i$列在前$i$个基向量方向的投影，此即$Q R$分解结果

例子

下面举例说明，对于如下的矩阵

首先对它的列向量进行正交化，得到如下矩阵

然后将该矩阵的列单位化，可以得到

由此可以得到上三角矩阵

用豪斯霍尔德变换进行$Q R$分解的思路与之前讲述的类似，首先用矩阵$A$的第1列构造第1个豪斯霍尔德矩阵$\boldsymbol{P}_{1}$

左乘该矩阵将$\boldsymbol{A}$的第1列后面$n-1$个元素全部零化

接下来构造第2个豪斯霍尔德矩阵$P_{2}$，为如下形式

其中

使用的第2列的后面个元素构造，将左乘，可以将其第2列后面个元素零化

构造第3个豪斯霍尔德矩阵$\boldsymbol{P}_{3}$，为如下形式

其中

用的第3列的后面个元素构造，将左乘，可以将其第3列后面个元素零化

依此类推，经过$n-1$次豪斯霍尔德变换，可以将$\boldsymbol{A}$化为上三角矩阵

令

由于$P_{0}, i=1, \cdots, n-1$都是正交矩阵，因此$Q$也是一个正交矩阵，这就是$\mathrm{QR}$分解的结果

$\mathrm{QR}$分解可以由Python中linalg的qr函数实现，函数的输入为被分解矩阵$A$，输出为正交矩阵$Q$和上三角矩阵$R$

下面用例子进行说明，首先考虑方阵，对于如下的方阵

其$\mathrm{QR}$分解的代码如下

1
2
3
4
5
6
import numpy as np

A = np.array([[1,2,3],[4,5,6],[7,8,9]])
Q, R = np.linalg.qr(A)
print(Q)
print(R)

程序运行结果如下

1
2
3
4
5
6
7
[[-0.12309149  0.90453403    0.40824829],
 [-0.49236596  0.30151134    -0.81649658],
 [-0.86164044  -0.301511340  0.40824829]]

[[-8.12403840e+00  -9.60113630e+00  -1.10782342e+01],
 [0.00000000e+00   9.04534034e-01   1.80906807e+00],
 [0.00000000e+00   0.00000000e+00   -8.88178420e-16]]

可以验证这两个矩阵的乘积就是原始矩阵$\boldsymbol{A}$，接下来考虑不是方阵的情况，对于如下的矩阵

其$\mathrm{QR}$分解的代码如下

1
2
3
4
5
6
import numpy as np

A = np.array([[1,2,3],[4,5,6]])
Q, R = np.linalg.qr(A)
print(Q)
print(R)

程序运行结果如下

1
2
3
4
5
[[-0.24253563-0.9701425]
 [-0.97014250 .24253563]]

[[-4.12310563-5.33578375-6.54846188]
 [0,-0.72760688-1.45521375]]

特征值分解

定义

特征值分解(Eigen Decomposition)也称为谱分解(Spectral Decomposition)，是矩阵相似对角化的另一种表述

对于$n$阶矩阵$\boldsymbol{A}$，如果它有$n$个线性无关的特征向量，则可将其分解为如下3个矩阵的乘积

其中$\Lambda$为对角矩阵，矩阵$\Lambda$的对角线元素为矩阵$A$的特征值

$Q$为$n$阶矩阵，它的列为$A$的特征向量，与对角矩阵中特征值的排列顺序一致

一个$n$阶矩阵可以进行特征值分解的充分必要条件是它有$n$个线性无关的特征向量，通常情况下，这些特征向量$x_{i}$都是单位化的

用于计算逆矩阵

特征值分解可以用于计算逆矩阵，如果矩阵$\boldsymbol{A}$可以进行特征值分解，且其所有特征值都非0，则

其逆矩阵为

对角矩阵的逆矩阵容易计算，是主对角线所有元素的倒数

特征值分解还可用于计算矩阵的多项式或者幂，对于如下多项式

如果矩阵$\boldsymbol{A}$可以进行特征值分解，且

则有

对角矩阵的幂仍然是对角矩阵，是主对角线元素分别求幂，因此有

借助于特征值分解，可以高效地计算出$f(A)$，特别地，有

如果$A$是实对称矩阵，可对其特征向量进行正交化，特征值分解为

其中$Q$为正交矩阵，它的列是$A$的正交化特征向量，$A$同样为$A$的所有特征值构成的对角矩阵

特征值分解可以借助于$\mathrm{QR}$箕法实现，机器学习中常用的矩阵如协方差矩阵等都是实对称矩阵，因此都可以进行特征值分解

特征值分解可以由Python中linalg的eig函数实现，函数的输入为被分解矩阵$A$，输出为所有特征值，以及这些特征值对应的单位化特征向量

1
2
3
4
5
6
import numpy as np

A = np.array([[1,2,3],[4,5,6],[7,8,9]])
V, U = np.linalg.eig(A)
print(U)
print(V)

程序结果如下

1
2
3
4
5
[[-0.23197069-0.785830240 .40824829]
 [-0.52532209-0.08675134-0.81649658]
 [-0.81867350 .612327560 .40824829]]

[1.61168440e+01   -1.11684397e+00  -1.30367773e-15]

这里的V所有特征值形成的向量，U的列是单位化的特征向量

奇异值分解

特征值分解只适用于方阵，且要求方阵有$n$个线性无关的特征向量

奇异值分解(Singular Value Decomposition, SVD)是对它的推广，对于任意的矩阵均可用特征值与特征向量进行分解

其思路是对$A A^{\mathrm{T}}$和$\boldsymbol{A}^{\mathrm{T}} \boldsymbol{A}$进行特征值分解，对于任意矩阵$\boldsymbol{A}$，这两个矩阵都是对称半正定矩阵，一定能进行特征值分解

并且这两个矩阵的特征值都是非负的，后面将会证明它们有相同的非0特征值

假设$A \in \mathbb{R}^{m \times n}$，其中$m \geqslant n$，则有

其中$\boldsymbol{U}$为$m$阶正交矩阵，其列称为矩阵$\boldsymbol{A}$的左奇异向量，也是$\boldsymbol{A} \boldsymbol{A}^{\mathrm{T}}$的特征向量，$\boldsymbol{\Sigma}$为如下形式的$m \times n$矩阵

其尺寸与$\boldsymbol{A}$相同，在这里$\boldsymbol{\Sigma}_{n}$是$n$阶对角矩阵且主对角线元素按照其值大小降序排列

$\sigma_{i}$称为$\boldsymbol{A}$的奇异值，是$\boldsymbol{A} \boldsymbol{A}^{\mathrm{T}}$特征值的非负平方根，也是$\boldsymbol{A}^{\mathrm{T}} \boldsymbol{A}$特征值的非负平方根

$\boldsymbol{V}$为$n$阶正交矩阵，其行称为矩阵$\boldsymbol{A}$的右奇异向量，也是$\boldsymbol{A}^{\mathrm{T}} \boldsymbol{A}$的特征向量

式1两边左乘$\boldsymbol{U}$，右乘$\boldsymbol{V}^{\mathrm{T}}$，由于$\boldsymbol{U}$、$\boldsymbol{V}$都是正交矩阵，因此有

上式称为矩阵的奇异值分解，对于$m \leqslant n$的情况，有类似的结果，此时

下面证明$\boldsymbol{A} A^{\mathrm{T}}$与$\boldsymbol{A}^{\mathrm{T}} \boldsymbol{A}$有相同的非0特征值，假设$\lambda \neq 0$是$A A^{\mathrm{T}}$的特征值,$\boldsymbol{x}$是对应的特征向量，则有

上式两边同时左乘$\boldsymbol{A}^{\mathrm{T}}$可以得到

即

下面证明$\boldsymbol{A}^{\mathrm{T}} \boldsymbol{x} \neq \mathbf{0}$，式 (2.65) 两边同时左乘$\boldsymbol{x}^{\mathrm{T}}$, 由于$\lambda \neq 0, \boldsymbol{x} \neq \mathbf{0}$

因此$A^{\mathrm{T}} x \neq 0$，$\lambda$是$A^{\mathrm{T}} A$的特征值，$\boldsymbol{A}^{\mathrm{T}} \boldsymbol{x}$是对应的特征向量

同样，如果$\lambda \neq 0$是$A^{\mathrm{T}} A$的特征值,$\boldsymbol{x}$是对应的特征向量，则有

上式两边同时左乘$\boldsymbol{A}$可以得到

即

下面证明$A x \neq 0$，上上上式两边同时左乘$x^{\mathrm{T}}$，由于$\lambda \neq 0, x \neq 0$

因此$A x \neq 0$，$\lambda$是$A A^{\mathrm{T}}$的特征值，$A \boldsymbol{x}$是对应的特征向量

需要注意的是，$\boldsymbol{A A ^ { \mathrm { T } }}$的0特征值不一定是$A^{\mathrm{T}} \boldsymbol{A}$的0特征值，下面举例说明，对于如下的矩阵

有

$A A^{\mathrm{T}}$的特征值为

可知特征值为，0是的特征值但不是的特征值

下面来看奇异值分解的一个例子。对于如下的矩阵

有

以及

这里的特征值为，的特征值为

因此$\boldsymbol{A}$的非0奇异值为、

计算$\boldsymbol{A} \boldsymbol{A}^{\mathrm{T}}$与$\boldsymbol{A}^{\mathrm{T}} \boldsymbol{A}$的特征向量并进行单位化，最后得到奇异值分解结果为

如果$m \geqslant n$

即

在这里

是$n$阶对角阵，上式就是$A^{\mathrm{T}} \boldsymbol{A}$的特征值分解

类似地有

即

在这里

是$m$阶对角阵，上上式就是$A A^{\mathrm{T}}$的特征值分解，对于$m \leqslant n$有相同的结论

如果$A$是对称矩阵，则$A^{\mathrm{T}} A=A A^{\mathrm{T}}=A \boldsymbol{A}$，因此$A^{\mathrm{T}} A$和$\boldsymbol{A} \boldsymbol{A}^{\mathrm{T}}$的特征值分解是相同的，这意味着$U$和$V$相同

假设$\lambda$是$A$的特征值，根据特征值的性质，$\lambda^{2}$是$A^{\mathrm{T}} \boldsymbol{A}$与$\boldsymbol{A A ^ { \mathrm { T } }}$的特征值，因此$A$的奇异值为其特征值的绝对值

Python中linalg的svd函数实现了奇异值分解，函数的输入值为被分解矩阵$A$，输出为正交矩阵$U$和$V^{\mathrm{T}}$，以及非0奇异值$\sigma_{i}$

1
2
3
4
5
6
7
8
from numpy import *

data = [[1,2,3],[4,5,6]]
u, sigma, vt = linalg.svd(data)

print(u)
print(sigma)
print(vt)

输出结果如下

1
2
3
4
5
6
7
[[-0.3863177   -0.92236578]
 [-0.92236578   0.3863177]
 [9.508032      0.77286964]] 
 
[[-0.42866713   -0.56630692   -0.7039467]
 [0.80596391    0.11238241    -0.58119908]
 [0.40824829   -0.81649658    0.40824829]]

这里的u是公式中的$U$，$\mathrm{vt}$是公式中的$V^{\mathrm{T}}$，sigma是所有非0奇异值，它们构成如下$2 \times 3$的矩阵$\boldsymbol{\Sigma}$

可以验证，这3个矩阵的乘积为原始矩阵

奇异值分解的几何意义

向量$\boldsymbol{x}$左乘任意矩阵$\boldsymbol{A}$所实现的线性变换可以分解为3次变换

首先是$\boldsymbol{x}$左乘正交矩阵$V^{\mathrm{T}}$所代表的旋转变换，接下来是$V^{\mathrm{T}} x$左乘矩阵$\boldsymbol{\Sigma}$所代表的拉伸变换

最后是$\Sigma V^{\mathrm{T}} x$左乘正交矩阵$U$所代表的旋转变换

奇异值分解揭示了矩阵的本质特征，对分析矩阵的性质有重要的价值

在对人工神经网络权重矩阵的理论分析中，奇异值和奇异向量经常被使用，在图像压缩与推荐系统中，奇异值分解也有应用