矩阵分解

• 矩阵加法分解：将矩阵分解为三角阵、对角阵之和

  • 常用于迭代求解线性方程组

• 矩阵乘法分解：将矩阵分解为三角镇、对角阵、正交阵之积

• 以下分解均在实数域上，扩展至复数域需同样将相应因子矩阵 扩充至复数域上定义

矩阵加法分解

Jacobi分解

Jacobi分解：将矩阵分解为对角阵、非对角阵

matrix_decomposition_jacobi

Gauss-Seidel分解

Gauss-Seidel分解：将矩阵分解为上、下三角矩阵

matrix_decomposition_gauss_seidel

Successive Over Relaxation

SOR：逐次超松弛迭代法，分解为对角、上三角、上三角矩阵，同时 增加权重$w$调整分解后比例

matrix_decomposition_sor

• 利用内在等式应用的平衡性、不动点收敛理论可以快速迭代
  • $x$拆分到等式左右两侧，可以视为$y=x$和另外函数交点
  • 根据不动点收敛理论可以进行迭代求解

LU系列分解

LU Decomposition

LU分解：将方阵分解为lower triangualr matrix、 upper triangluar matrix

$$\begin{align*} A & = L U \\ \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,m} \end{bmatrix} & = \begin{bmatrix} l_{1,1} & 0 & \cdots & 0 \\ l_{2,1} & l_{2,2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{m,1} & l_{m,2} & \cdots & l_{m,m} \end{bmatrix} \begin{bmatrix} u_{1,1} & u_{1,2} & \cdots & u_{1,m} \\ 0 & u_{2,2} & \cdots & u_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{m,m} \end{bmatrix} \end{align*}$$

• $L$：下三角矩阵
• $U$：上三角矩阵

• 特别的可以要求某个矩阵对角线元素为1
• 几何意义：由单位阵出发，经过竖直、水平切变

特点

• LU分解实际上不需要额外存储空间，矩阵L、U可以合并存储

• LU分解可以快速求解线性方程组，可以视为高斯消元法的矩阵 形式

  • 得到矩阵LU分解后，对任意向量b，可使用已有LU分解 求解

    • L为消元过程中的行系数和对角线全为1的下三角矩阵 （负系数在矩阵中为正值）
    • U为消元结果上三角矩阵

  • 则解方程组$Ax=b$等价于$LUx=b$

    • 先求解$Ly=b$
    • 再求解$Ux=x$

LDU Decomposition

LDU分解：将矩阵分解为下三角、上三角、对角矩阵

$$\begin{align*} A & = L D U \\ \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,m} \end{bmatrix} & = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ l_{2,1} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{m,1} & l_{m,2} & \cdots & 1 \end{bmatrix} \begin{bmatrix} u_{1,1} & 0 & \cdots & 0\\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{m,m} \end{bmatrix} \begin{bmatrix} 1 & u_{1,2}/u_{1,1} & \cdots & u_{1,m}/u_{1,1} \\ 0 & 1 & \cdots & u_{2,m}/u_{2,2} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix} \end{align*}$$

• LU分解可以方便的得到LDU分解：提取对角阵、然后对应矩阵 元素等比缩放

PLU[Q] Decomposition

• PLU分解：将方阵分解为置换矩阵、下三角、上三角矩阵
• PLUQ分解：将方阵分解为置换矩阵、下三角、上三角、置换矩阵

• 考虑$P^{-1}A=LU$，交换$A$行即可作普通LU分解，PLUQ分解 类似
• PLU分解数值稳定性好、实用工具

LL/Cholesky Decomposition

LL分解：将对称阵分解为下三角、转置

$$\begin{align*} A & = L L^T \\ \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,m} \end{bmatrix} & = \begin{bmatrix} l_{1,1} & 0 & \cdots & 0 \\ l_{2,1} & l_{2,2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{m,1} & l_{m,2} & \cdots & l_{m,m} \end{bmatrix} \begin{bmatrix} l_{1,1} & l_{2,1} & \cdots & l_{m,1} \\ 0 & l_{2,2} & \cdots & l_{m,2} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & l_{m,m} \end{bmatrix} \end{align*}$$

• Cholesky分解常用于分解$A^TA$

  • 常用于相关分析，分解相关系数阵、协方差阵

• 相较于一般LU分解，Cholesky分解速度更快、数值稳定性更好

• 类似的有LDL分解，同时提取对角线元素即可

Singular Value Decomposition

SVD奇异值分解：将矩阵分解为正交矩阵、对角矩阵、正交矩阵

$$M_{m*n} = U_{m*r} \Sigma_{r*r} V_{n*r}^T$$

• 特征值分解在任意矩阵上推广：相应的特征值、特征向量 被称为奇异值、奇异向量
• 几何意义：由单位阵出发，经旋转、缩放、再旋转

特点

• $\Sigma$对角线元素为$M^T M$、$M M^T$的奇异值

  • 可视为在输入输出间进行标量的放缩控制
  • 同$U$、$V$的列向量相对应

• $U$的列向量称为左奇异向量

  • $M M^T$的特征向量
  • 与$M$正交的“输入”或“分析”基向量

• $V$的列向量成为右奇异向量

  • $M^T M$的特征向量
  • 与$M$正交的“输出”基向量

低阶近似

• 对$m * n$阶原始矩阵$M$

  • 设其秩为$K \leq min(m, n)$，奇异值为 $d_1 \geq d_2 \geq \cdots \geq d_K > 0$
  • 不失一般性可以设其均值为0

• 根据Eckart and Young的结果

  $$\forall r \leq K, \sum_{k=1}^r d_k u_k v_k^T = \arg\min_{\bar M \in M(r)} \| M - \bar M \|_F^2$$

  • $u_k, v_k$：$U, V$的第$k$列向量
  • $|M|_F$：矩阵的Frobenius范数

QR Decomposition

QR分解：将矩阵分解为正交矩阵、上三角矩阵

$$\begin{align*} A = Q R \end{align*}$$

• 几何意义：由单位阵出发，经旋转、切变

特点

• 正交矩阵逆为其转置，同样可以方便求解线性方程组

向量

• 线性组合
• 向量空间
• 空间的基：向量空间的一组基是张成该空间的一个线性无关向量集
• 线性相关

vector_rules_for_addition_and_scaling

向量点积

• 向量点积性质

  • 向量的数乘等比例影响点积，则可为每个向量找到共线单位向量满足 $u \cdot u=1$

    

    vector_dot_scaling

  • 点积等同于向量 $b$ 左乘矩阵 $a^T$，即把向量 $b$ 压缩（线性变换）至向量 $a$ 方向上

    

    vector_dot_as_matrix_production

• 点积 $a \cdot b$ 与投影关系（假设向量 $a$ 为单位向量）

  • 投影，即将向量 $b$ 线性变换 至 $a$ 方向上的标量

    • 则投影可以用 $1 * n$ 矩阵表示
    • 投影代表的矩阵则可通过利用基向量的变换结果求解

    

    vector_projection_as_transformer

  • 向量 $a$ 本身作为单位向量

    • 坐标轴上单位向量与 $a$ 的内积即为 $a$ 该方向分量，也即 $a$ 在该轴上投影
    • 由对称性显然，坐标轴在 $a$ 方向投影等于 $a$ 在轴方向投影
    • 则投影到向量 $a$ 代表的线性变换矩阵即为 $a^T$

    

    vector_dot_projection_duality

  • 扩展到一般情况

    • 考虑标量乘法对点积影响，坐标轴上向量与任意向量 $a$ 内积等价于投影
    • 投影是线性变换，则对空间一组基的变换可以推导到空间中任意向量 $b$

• 高维空间到标量的线性变换与空间中一个向量对应，即应用线性变换等价于同该向量点积

  vector_dot_as_matrix_production

点积用途

• 向量证明基本都是都转换到点积上
  • 正定：行列式恒>0
  • 下降方向：内积<0
  • 方向（趋于）垂直：内积趋于0

求和、积分、点积、卷积

• 卷积：累计中各点的值变为需累计的值，即二次累计

向量叉积

vector_cross_formula

• 向量叉积意义

  • 向量叉积即寻找向量（到标量的线性变换），满足与其点积结果为张成的体积

    

    vector_cross_as_volume

  • 考虑点积性质，则向量叉积的方向与向量构成超平面垂直、模为超平面大小

    

    vector_cross_direction

一些规定

• 正交方向：向量空间 $R^n$ 中 $k, k \leq n$ 个向量 $q^{(1)}, \cdots, q^{(k)}$ 两两正交，则称其为 $k$ 个正交方向，若满足所有向量非 0，则称为 $k$ 个非 0 正交方向

• 向量左右

  • 左侧：向量逆时针旋转 $[0, \pi]$ 内
  • 右侧：反左侧

矩阵

• 矩阵（乘法）：对向量的变换

  • 对 $m * n$ 矩阵，即将 $n$ 维空间映射至 $m$ 维空间

• 矩阵相关概念

  • （矩阵）秩：空间维数
  • （矩阵）零空间/核：变换（左乘矩阵）后落在原点的向量的集合

  

  matrix_null_space

• 线性变换：保持空间中坐标轴仍为直线且原点保持不变的变换
• 此处若无特殊说明，向量均以列向量作为基础

特殊矩阵

• 其中正交矩阵、三角阵、对角阵也被成为因子矩阵

• Orthogonal Matrix 正交矩阵：和其转置乘积为单位阵的方阵

  • 左乘正交矩阵几何意义：等价于旋转

    

    orthogonal_matrix_geo

  • 酉矩阵/幺正矩阵：$n$ 个列向量是 $U$ 空间标准正交基的 $n$ 阶复方阵，是正交矩阵往复数域上的推广

• Diagonal Matrix 对角阵：仅对角线非0的矩阵

  • 左乘对角阵矩阵几何意义：等价于对坐标轴缩放

    

    diagonal_matrix_geo

• Triangular Matrix 上/下三角矩阵：左下/右上角全为0的方阵

  • 三角阵是高斯消元法的中间产物，方便进行化简、逐层迭代求解线性方程组

  • 左乘上三角阵几何意义：等价于进行右上切变（水平斜拉）

    

    upper_triangular_matrix_geo

  • 左乘下三角阵几何意义：等价于进行左下切变（竖直斜拉）

    

    lower_triangular_matrix_geo

• Transposation Matrix 置换矩阵：系数只由 0、1 组成，每行、列恰好有一个 1 的方阵

矩阵常用公式

Sherman-Morrison 公式

• 设A是n阶可逆矩阵，$u, v$均为n为向量，若 $1 + v^T A^{-1} u \neq 0$，则扰动后矩阵$A + u v^T$可逆 $$(A + u v^T)^{-1} = A^{-1} - \frac {A^{-1} u v^T A^{-1}} {1 + v^T A^{-1} u}$$

矩阵乘法

• 矩阵乘法

  • 向量左乘矩阵：即是对向量进行变换

    

    matrix_as_transformer

  • 矩阵乘积：复合变换

    

    matrix_production

• 矩阵乘法应按照从右往左阅读，右侧矩阵为输入、左侧矩阵为变换（向量默认为列向量时）

Affline Transformation

仿射变换：对向量空间进行线性变换、平移得到另一个向量空间

affline_transformation

$$\begin{align*} y &= Ax + b \\ y &= (A|b^T) \begin {bmatrix} x \\ 1 \end {bmatrix} \end{align*}$$

• $y \in R^n, x \in R^n$
• $A \in R^{n * n}$：可视为产生旋转、放缩
• $b \in R^n$：可视为产生平移

• 仿射变换可以理解为：放缩、旋转、平移

• 从仿射变换的角度，对向量空间进行仿射变换

  • $n+1$ 对变换前、变换后向量坐标即可以求解仿射变换的全部参数
  • 变换后的向量之间仍然保留某种相关性，所以 $n+1$ 对向量坐标可以完全确定仿射变换

• 从仿射变换几何含义，将向量空间中向量统一变换

  • $n+1$ 个不共线 $n$ 维向量即唯一确定n维空间
  • 若所有向量变换均遵循同一“线性”变换规则，即进行相同放缩、旋转、平移，则这样的变换可以使用仿射变换表示

• 说明

  • $n$ 变换前、变换后向量坐标可以求解 $A$（不考虑 $b$），但第 $n+1$ 对向量坐标未必满足 $A$ 变换
  • 若 $n+2$ 对向量坐标不满足 $(A|b)$ 的解，则表示不是进行仿射变换

Perspective Transformation

透视变换：将向量空间映射到更高维度，再降维到另一向量空间

perspective_transformation

$$\begin{align*} y &= P \begin {bmatrix} x \\ 1 \end {bmatrix} \\ y &= \begin {bmatrix} A & b \\ c & p_{n+1,n+1} \end {bmatrix} \begin {bmatrix} x \\ 1 \end {bmatrix} \end{align*}$$

• $P \in R^{(n+1) (n+1)}, A \in R^{n n}$
• $x \in R^n, y \in R^{n+1}$：这里默认$x$第$n+1$维为1
• $c$：可视为产生透视，若其为0向量，则退化为仿射变换
• $p_{n+1,n+1}$：可视为决定透视放缩，所以若是已确定新向量空间的“位置”，此参数无效，即 $n+2$ 对向量坐标即可求解变换

• 透视变换虽然是向量空间变换至另一向量空间，但仍然存在一个透视“灭点”，作为所有透视线的交点

  • 对平面成像而言，“灭点”是成像平面、视角决定

• 变换后 $y$ 维数增加，一般会再次投影、缩放回原维度空间，如原向量空间 $(R^n,1)$

• 仿射变换可以视为是新的向量空间和原始空间“平行”的透视变换特例

变换矩阵求解

$$\begin{align*} \begin {bmatrix} P & b \\ c & p_{n+1,n+1} \end {bmatrix} \begin {bmatrix} x \\ 1 \end {bmatrix} &= \gamma \begin {bmatrix} x^{'} \\ 1 \end {bmatrix} \\ \Rightarrow Px + b &= \gamma x^{'} \\ c^Tx + p_{n+1,n+1} &= \gamma \\ \Rightarrow Px + b &= (c^Tx + p_{n+1,n+1}) x^{'} \end{align*}$$

• 考虑变换后再次缩放回更低维 $(R^n,1)$ 向量空间
• $\gamma$：变换后向量缩放比例

• 可解性
  • 共 $n+2$ 对变换前、后向量坐标，即 $n*(n+2)$ 组方程
  • 对每对向量，其中 $n$ 组方程如上可以看出是齐次方程组，不包含常数项
  • 则对 $P \in R^{(n+1) * (n+1)}$ 中除 $p_{n+1,n+1}$ 其他项均可被其比例表示（不含常数项）

• 当然 $p_{n+1,n+1}$ 可以置 1 参加运算，不影响结果

Determinant

• 矩阵行列式几何意义：线性变换对空间的拉伸比例

  • 行列式绝对值：拉伸的比例的绝对大小
    • 行列式为 0 时则表示空间降维
    • 则显然应有 $det(M_1 * M_2) = det(M_1) det(M_2)$
  • 行列式正负号：拉伸的方向

  

  matrix_determinant_as_stretch

• 矩阵行列式的用途

  • 行列式为 0 意味着矩阵表示降维变换，则对应线性方程组仅在方程组右侧在矩阵张成空间内，即扩展矩阵秩不增时有解

特别的

• $2 * 2$ 矩阵 $\begin{vmatrix} a & b \ c & d \end{vmatrix} = ad - bc$

  • $a, d$ 分别表示 $(1,0)$、$(0,1)$ 正向放缩比例
  • 而 $b, c$ 则相应的为逆向放缩比例

  

  matrix_2_2_determinant_calculation

• 二维三点：行列式绝对值为三点构成三角形面积两倍

  $$\begin{vmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \\ \end{vmatrix} = x_1y_2 + x_3y_1 + x_2y_3 - x_3y_2 - x_2y_1 - x_1y_3$$

  • $q_3$ 位于 $\overrightarrow{q_1q_2}$ 左侧：行列式大于0
  • $q_3q_1q_2$ 共线：行列式值为 0

• 三维三点：行列式为三个向量张成的平行六面体体积

Eigen Value、Eigen Vector

• 矩阵（变换）特征向量、特征值几何意义

  • 特征向量：在线性变换后仍然在自身生成空间中，即保持方向不变，仅是模变化的向量
  • 特征值：对应特征向量模变化的比例

• 特殊变换中的特征向量、特征值情况

  • 旋转变换：特征值为 $\pm i$，没有特征向量，即特征值为复数表示某种旋转
  • 剪切变换（$\begin{vmatrix} A^{‘} & 0 \ 0 & 1 \end{vmatrix}$$：必然有特征值为 1，且对应特征向量在坐标轴上
  • 伸缩变换（$\lambda E$）：所有向量都是特征向量

• 矩阵对角化

  • 矩阵对角化：即寻找一组基，使得线性变换对该组基向量仅引起伸缩变换
  • 定理：当且仅当 $n$ 阶矩阵 $A$ 有 $n$ 个线性无关的特征向量时，其可以对角化
    • 即变换后有 $n$ 个线性无关向量在自身生成空间中
    • 也即矩阵对应变换为线性变换

线性方程组

Gaussian Elimination

高斯消元法：初等变换n个线性方程组为等价方程组，新方程组系数矩阵为上三角矩阵

• 三角系数矩阵可以方便的递推求解
• 初等变换可将系数矩阵变换为上三角矩阵，而不影响方程解

参考资料

• https://www.bilibili.com/video/av6731067/
• https://charlesliuyx.github.io/2017/10/06/%E3%80%90%E7%9B%B4%E8%A7%82%E8%AF%A6%E8%A7%A3%E3%80%91%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0%E7%9A%84%E6%9C%AC%E8%B4%A8/

矩阵求导/矩阵微分

Layout Conventions

矩阵求导：在矩阵空间的多元微积分

• numerator layout：分子布局，微分分子的维数决定微分结果 的高维度结构（行优先，如：微分矩阵行数等于分子维数）
• denominator layout：分母布局，微分分母的维数为微分结果 的高维度结构（行优先）

• 两种布局方式相差转置
• 与微分分子、分母为行、或列向量无关 （即当微分分子、分母为向量时，行、列向量结果相同，只与 维度有关）
• 此布局模式仅讨论简单单因子微分时布局模式，复合多因子 应使用维度分析考虑 （即若严格按照计算规则，结果应该满足布局）

matrix_derivative_results

• 数分中Jaccobi行列式采用分子布局，以下默认为分子布局

维度分析

维度分析：对求导结果的维度进行分析，得到矩阵微分结果

• 维度一般化：将向量、矩阵维度置不同值，便于考虑转置
• 拆分有关因子：利用求导乘法公式（一般标量求导）拆分 因子，分别考虑各因子微分结果
• 变换微分因子、剩余因子（可能有左右两组），以满足矩阵运算 维度要求
  • 微分因子：按布局模式考虑维度、不转置
  • 剩余因子：为满足最终结果符合维度布局，考虑转置
  • 若维度一般化也无法唯一确定剩余因子形式，再考虑行、列 內积对应关系

• 考虑到矩阵乘法定义（左乘矩阵行数为乘法结果行数），则在 分子布局（分子行优先），简单微分中若微分因子为右乘矩阵、 剩余因子为左乘矩阵，则类似标量系数在前求微分，否则 结果需转置

例

• 考虑$\frac {\partial x^T A x} {\partial x}$，其中 $A \in R^{n*n}, x \in R^n$

• 维度一般化：$\frac {\partial u^T A v} {\partial x}$， 其中$A \in R^{a * b}, x \in R^n$

• 拆分有关因子，变换微分、剩余因子

  $$\begin{align*} \frac {\partial (u^T A) v} {\partial x} & = u^T A \frac {\partial v} {\partial x} \\ \frac {\partial u^T (A v)} {\partial x} & = v^T A^T \frac {\partial u} {\partial x} \end{align*}$$

• 则有

  $$\frac {\partial x^T A x} {\partial x} = x^T (A^T + A)$$

关于标量导数

标量对标量

标量$y$对标量$x$求导：$\frac {\partial y} {\partial x}$

matrix_derivative_scalar_by_scalar_vector_involved

matrix_derivative_scalar_by_scalar_matrix_involved

向量对标量

向量$Y$关于标量$x$求导（$Y$为行、列向量均如此）

matrix_derivative_vector_by_scalar

$$\frac {\partial Y} {\partial x} = \begin{bmatrix} \frac {\partial y_1} {\partial x} \\ \frac {\partial y_2} {\partial x} \\ \vdots \\ \frac {\partial y_n} {\partial x} \end{bmatrix}$$

矩阵对标量

矩阵$Y$关于标量$x$求导

matrix_derivative_matrix_by_scalar

$$\frac {\partial Y} {\partial x} = \begin{bmatrix} \frac {\partial y_{11}} {\partial x} & \frac {\partial y_{12}} {\partial x} & \cdots & \frac {\partial y_{1n}} {\partial x} \\ \frac {\partial y_{21}} {\partial x} & \frac {\partial y_{22}} {\partial x} & \cdots & \frac {\partial y_{2n}} {\partial x} \\ \vdots & \vdots & \ddots & \vdots \\ \frac {\partial y_{n1}} {\partial x} & \frac {\partial y_{n2}} {\partial x} & \cdots & \frac {\partial y_{nn}} {\partial x} \\ \end{bmatrix}$$

关于向量导数

标量对向量

标量$y$关于向量$X$求导

matrix_derivative_scalar_by_vector

matrix_derivative_scalar_by_vector

$$\frac {\partial y} {\partial X} = [\frac {\partial y} {\partial x_1}, \frac {\partial y} {\partial x_1}, \cdots, \frac {\partial y} {\partial x_n}]$$

向量对向量

向量$Y$关于向量$X$求导

matrix_derivative_vector_by_vector

$$\frac {\partial Y} {\partial X} = \begin{bmatrix} \frac {\partial y_1} {\partial x_1} & \frac {\partial y_1} {\partial x_2} & \cdots & \frac {\partial y_1} {\partial x_n} \\ \frac {\partial y_2} {\partial x_1} & \frac {\partial y_2} {\partial x_2} & \cdots & \frac {\partial y_2} {\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac {\partial y_m} {\partial x_1} & \frac {\partial y_m} {\partial x_2} & \cdots & \frac {\partial y_m} {\partial x_n} \end{bmatrix}$$

• $Y$、$X$为行、列向量均如此

关于矩阵导数

标量对矩阵求导

matrix_derivative_scalar_by_matrix_1

matrix_derivative_scalar_by_matrix_2

matrix_derivative_scalar_by_matrix_3

matrix_derivative_scalar_by_matrix_4

微分

微分形式

matrix_differential

导数、微分转换

matrix_derivative_differential_conversion

Reproducing Kernel Hilbert Space

• Hilbert space：假设 $K(x,z)$ 是定义在 $\mathcal{X X}$ 上的对称函数，并且对任意 $x_1, x_2, \cdots, x_m \in \mathcal{X}$，$K(x,z)$ 关于其的 Gram* 矩阵半正定，则可以根据函数 $K(x,z)$ 构成一个希尔伯特空间

构造步骤

定义映射构成向量空间

• 定义映射

  $$\phi: x \rightarrow K(·, x)$$

• 根据此映射，对任意 $x_i \in \mathcal{X}, \alpha_i \in R, i = 1,2,\cdots,m$ 定义线性组合

  $$f(·) = \sum_{i=1}^m \alpha_i K(·, x_i)$$

• 由以上线性组合为元素的集合 $S$ 对加法、数乘运算是封闭的，所以 $S$ 构成一个向量空间

定义内积构成内积空间

• 在 $S$ 上定义运算 $*$：对任意 $f,g \in S$

  $$\begin{align*} f(·) = \sum_{i=1}^m \alpha_i K(·, x_i) \\ g(·) = \sum_{j=1}^n \beta_j K(·, z_j) \end{align*}$$

  定义运算 $*$

  $$f * g = \sum_{i=1}^m \sum_{j=1}^n \alpha_i \beta_j K(x_i, z_j)$$

• 为证明运算 $*$ 是空间 $S$ 的内积

  • 需要证明：
    • $(cf) g = c(f g), c \in R$
    • $(f + g) h = f h + g * h, h \in S$
    • $f g = g f$
    • $f f \geq 0, f f = 0 \Leftrightarrow f = 0$
  • 其中前3条由 $S$ 元素定义、$K(x,z)$ 对称性容易得到
  • 由 $*$ 运算规则可得 $$f * f = \sum_{i,j=1}^m \alpha_i \alpha_j K(x_i, x_j)$$ 由 Gram 矩阵非负可知上式右端非负，即 $f * f \geq 0$

• 为证明 $f * f \Leftrightarrow f = 0$

  • 首先证明

    $$|f * g|^2 \leq (f * f)(g * g)$$

    • 设$f, g \in S$，则有$f + \lambda g \in S$，则有

      $$\begin{align*} (f + \lambda g) * (f + \lambda g) & \geq 0 \\ f*f + 2\lambda (f * g) + \lambda^2 (g*g) & \geq 0 \end{align*}$$

    • 则上述关于$\lambda$的判别式非负，即

      $$(f*g)^2 - (f*f)(g*g) \leq 0$$

  • $\forall x \in \mathcal{x}$，有

    $$K(·, x) * f = \sum_{i=1}^m \alpha_i K(x, x_i) = f(x)$$

    则有

    $$|f(x)|^2 = |K(·, x) * f|^2$$

  • 又

    $$|K(·, x) * f|^2 \leq (K(·, x) * K(·, x))(f * f) = K(x, x)(f*f)$$

    则有

    $$|f(x)|^2 \leq K(x, x) (f * f)$$

    即$f * f = 0$时，对任意$x$都有$|f(x)| = 0$

• 因为 $*$ 为向量空间 $S$ 的内积，可以继续用 $·$ 表示

  $$f·g = \sum_{i=1}^m \sum_{j=1}^n \alpha_i \alpha_j K(x_i,z_J)$$

完备化构成Hilbert空间

• 根据内积定义可以得到范数

  $$\|f\| = \sqrt {f · f}$$

  所以 $S$ 是一个赋范向量空间，根据泛函分析理论，对于不完备的赋范空间 $S$ ，一定可以使之完备化得到希尔伯特空间 $\mathcal{H}$

• 此希尔伯特空间 $\mathcal{H}$ ，称为 reproducing kernel Hilber Space ，因为核 $K$ 具有再生性

  $$\begin{align*} K(·, x) · f & = f(x) \\ K(·, x) · K(·, Z) & = K(x, z) \end{align*}$$

Positive Definite Kernel Function

• 设 $K: \mathcal{X X} \leftarrow R$是对称函数，则$K(x,z)$为正定核函数的充要条件是$\forall x_i \in \mathcal{X}, i=1,2,…,m$，$K(x,z)$ 对应的 Gram 矩阵 $K = [K(xi, x_j)]{mm} $ 是半正定矩阵

• 必要性

• 由于 $K(x,z)$ 是 $\mathcal{X X}$上的正定核，所以存在从$\mathcal{X}$ 到 Hilbert* 空间 $\mathcal{H}$ 的映射，使得

  $$K(x,z) = \phi(x) \phi(z)$$

• 则对任意 $x_1, x_2, \cdots, x_m$，构造 $K(x,z)$ 关于其的 Gram 矩阵

  $$[K_{ij}]_{m*m} = [K(x_i, x_i)]_{m*m}$$

• 对任意 $c_1, c_2, \cdots, c_m \in R$，有

  $$\begin{align*} \sum_{i,j=1}^m c_i c_j K(x_i, x_j) & = \sum_{i,j=1}^m c_i c_j (\phi(x_i) \phi(x_j)) \\ & = (\sum_i c_i \phi(x_i))(\sum_j c_j \phi(x_j)) \\ & = \| \sum_i c_i \phi(x_i) \|^2 \geq 0 \end{align*}$$

  所以 $K(x,z)$ 关于 $x_1, x_2, \cdots, x_m$ 的 Gram 矩阵半正定

• 充分性

• 对给定的 $K(x,z)$，可以构造从 $\mathcal{x}$ 到某个希尔伯特空间的映射

  $$\phi: x \leftarrow K(·, x)$$

• 且有

  $$K(x,z) = \phi(x) · \phi(z)$$

  所以 $K(x,z)$ 是 $\mathcal{X * X}$ 上的核函数