Matrix Decomposition

矩阵分解

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

    • 常用于迭代求解线性方程组
  • 矩阵乘法分解:将矩阵分解为三角镇、对角阵、正交阵之积

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

矩阵加法分解

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 matrixupper triangluar matrix

  • $L$:下三角矩阵
  • $U$:上三角矩阵
  • 特别的可以要求某个矩阵对角线元素为1
  • 几何意义:由单位阵出发,经过竖直、水平切变

特点

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

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

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

      • L为消元过程中的行系数和对角线全为1的下三角矩阵 (负系数在矩阵中为正值)
      • U为消元结果上三角矩阵
    • 则解方程组$Ax=b$等价于$LUx=b$

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

LDU Decomposition

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

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

PLU[Q] Decomposition

  • PLU分解:将方阵分解为置换矩阵、下三角、上三角矩阵
  • PLUQ分解:将方阵分解为置换矩阵、下三角、上三角、置换矩阵
  • 考虑$P^{-1}A=LU$,交换$A$行即可作普通LU分解,PLUQ分解 类似
  • PLU分解数值稳定性好、实用工具

LL/Cholesky Decomposition

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

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

    • 常用于相关分析,分解相关系数阵、协方差阵
  • 相较于一般LU分解,Cholesky分解速度更快、数值稳定性更好

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

Singular Value Decomposition

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

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

特点

  • $\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的结果

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

QR Decomposition

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

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

特点

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

Vector

向量

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

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$可逆

矩阵乘法

  • 矩阵乘法

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

      matrix_as_transformer

    • 矩阵乘积:复合变换

      matrix_production

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

Affline Transformation

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

affline_transformation

  • $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

  • $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)$

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

变换矩阵求解

  • 考虑变换后再次缩放回更低维 $(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

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

    • $q_3$ 位于 $\overrightarrow{q_1q_2}$ 左侧:行列式大于0
    • $q_3q_1q_2$ 共线:行列式值为 0
  • 三维三点:行列式为三个向量张成的平行六面体体积

Eigen ValueEigen Vector

  • 矩阵(变换)特征向量、特征值几何意义

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

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

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

线性方程组

Gaussian Elimination

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

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

参考资料

Matrix Derivative/Matrix Differential

矩阵求导/矩阵微分

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$

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

  • 则有

关于标量导数

标量对标量

标量$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

矩阵对标量

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

matrix_derivative_matrix_by_scalar

关于向量导数

标量对向量

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

matrix_derivative_scalar_by_vector matrix_derivative_scalar_by_vector

向量对向量

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

matrix_derivative_vector_by_vector

  • $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

Hilbert空间

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)$ 构成一个希尔伯特空间

构造步骤

定义映射构成向量空间

  • 定义映射

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

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

定义内积构成内积空间

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

    定义运算 $ * $

  • 为证明运算 $ * $ 是空间 $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)$ 对称性容易得到
    • 由 $ * $ 运算规则可得Gram 矩阵非负可知上式右端非负,即 $f * f \geq 0$
  • 为证明 $f * f \Leftrightarrow f = 0$

    • 首先证明

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

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

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

      则有

    • 则有

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

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

完备化构成Hilbert空间

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

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

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

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}$ 的映射,使得

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

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

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

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

  • 且有

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