Linear Algebra in a Nutshell

Matrix

厄米特矩阵

埃尔米特矩阵等于自己的 共轭转置

• 厄米特矩阵 \(A^H = A\)
  • 实对称矩阵 \(A^T = A\)
• 反厄米特矩阵 \(A^H = -A\)
  • 实反对称矩阵 \(A^T = -A\)

正规矩阵

\[ A^H A = A A^H \]

• 酉矩阵 \(A^H A = A A^H = I\)
  • 正交矩阵 \(A^T A = AA^T = I\)
    • 特殊正交矩阵：\(\det(A) = +1\)，是一个旋转矩阵
      • Givens矩阵：\(G(i,j,\theta)\)
    • 瑕旋转矩阵：\(\det(A) = -1\)，瑕旋转是旋转加上镜射
      • Householder矩阵：\(H = I - 2 uu^T\)

正定与半正定矩阵

在线性代数里，正定矩阵(positive definite matrix)有时简称为 正定阵。

对任意的非零向量 \(\boldsymbol{x}\) 恒有 二次型

\[ f = \boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x} > 0 \]

则称 \(f\) 为 正定二次型，对应的矩阵为 正定矩阵；若 \(f \ge 0\)，则 对应的矩阵为 半正定矩阵。

直观理解

令 \(Y=MX\)，则 \(X^T Y > 0\)，所以

\[ cos(\theta) = \frac{X^T Y}{\|X\|\|Y\|} > 0 \]

因此，从另一个角度，正定矩阵代表一个向量经过它的变化后的向量与其本身的夹角 小于90度

判别对称矩阵A的正定性

• 求出A的所有特征值
  • 若A的特征值均为正数，则A是正定的；若A的特征值均为负数，则A为负定的。
• 计算A的各阶顺序主子式
  • 若A的各阶顺序主子式均大于零，则A是正定的；若A的各阶顺序主子式中，奇数阶主子式为负，偶数阶为正，则A为负定的。

伴随矩阵

余子式

在n阶行列式D中划去任意选定的k行、k列后，余下的元素按原来顺序组成的n-k阶行列式M，称为 行列式D的k阶子式A的余子式。

A关于第i行第j列的余子式（记作 \(M_{ij}\)）是去掉A的第i行第j列之后得到的(n− 1)×(n− 1)矩阵的行列式。

代数余子式

如果k阶子式A在行列式D中的行和列的标号分别为i1，i2，…，ik和j1，j2，…，jk。则在A的余子式M前面添加符号 \((-1)^{\left(i_{1}+i_{2}+, \ldots,+i_{k}\right)+\left(j_{1}+j_{2}+, \ldots,+j_{k}\right)}\)，所得到的n-k阶行列式，称为 行列式D的k阶子式A的代数余子式。

A的 (代数)余子矩阵 是一个n×n的矩阵C，使得其第i行第j列的元素是A关于第i行第j列的代数余子式：

\[ \mathbf{C}_{i j}=(-1)^{i+j} M_{i j} \]

伴随矩阵（adjoint matrix）

A的 代数余子矩阵 的 转置矩阵，也就是说， A的伴随矩阵是一个n×n的矩阵（记作adj(A)），使得其第i 行第j 列的元素是A关于第j 行第i 列的代数余子式

\[ \mathbf{A}^* = \operatorname{adj}(\mathbf{A})=\mathbf{C}^{T} \]

自伴随矩阵

\[ \mathbf{A}^* = \mathbf{A} \]

在数学里，作用于一个有限维的内积空间，一个自伴算子(self-adjoint operator)等于自己的伴随算子；等价地说，表达自伴算子的矩阵是埃尔米特矩阵。埃尔米特矩阵等于自己的共轭转置。

可逆矩阵（非奇异矩阵）

\[ \mathbf{A}^{-1} = \frac{1}{|\mathbf{A}|} \mathbf{A}^* \]

• 矩阵乘以可逆矩阵 秩不变，因为可逆矩阵可以表示为初等矩阵的乘积，而初等变换不改变矩阵的秩（左乘-行变换，右乘-列变换）

其他

• 对角阵：任意正规矩阵 都可以经过 正交变换 变成 对角矩阵

• 上（下）三角阵

矩阵变换

初等变换

• 初等变换只是不影响矩阵的秩，其他的特性都改变了。

• 对于计算矩阵的行列式，不能进行初等变换，但是可以做行列的进加减，不能乘以系数。

正交变换

Givens rotation（吉文斯旋转）

在数值线性代数中，吉文斯旋转（Givens rotation）是在两个坐标轴所展开的平面中的旋转。

吉文斯旋转 矩阵：

\[ G(i, j, \theta)=\left[\begin{array}{ccccccc} 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & & \vdots & & \vdots \\ 0 & \cdots & c & \cdots & s & \cdots & 0 \\ \vdots & & \vdots & \ddots & \vdots & & \vdots \\ 0 & \cdots & -s & \cdots & c & \cdots & 0 \\ \vdots & & \vdots & & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & \cdots & 0 & \cdots & 1 \end{array}\right] \]

\[ G \triangleq\left[\begin{array}{cc} \cos \phi & \sin \phi \\ -\sin \phi & \cos \phi \end{array}\right] \]

当一个吉文斯旋转矩阵 \(G(i, j, \theta)\) 从左侧乘另一个矩阵 \(A\) 的时候，\(GA\) 只作用于 \(A\) 的第 \(i\) 和 \(j\) 行。

\[ \left[\begin{array}{cc} c & -s \\ s & c \end{array}\right]\left[\begin{array}{l} a \\ b \end{array}\right]=\left[\begin{array}{l} r \\ 0 \end{array}\right] \]

明确计算出 \(\theta\) 是没有必要的。我们转而直接获取 c, s 和 r。一个明显的解是

\[ \begin{aligned} &r \leftarrow \sqrt{a^{2}+b^{2}}\\ &c \leftarrow a / r\\ &s \leftarrow-b / r \end{aligned} \]

• Givens 旋转在数值线性代数中主要的用途是在向量或矩阵中介入零。例如，这种效果可用于计算矩阵的 QR分解。

\[ G_{j_{k}} \ldots G_{j_{2}} G_{j_{1}} R_{a}=\left[\begin{array}{c} R^{\prime} \\ 0 \end{array}\right] \]

• 超过 Householder变换 的一个好处是它们可以轻易的并行化，另一个好处是对于非常稀疏的矩阵计算量更小。

Eigen::Matrix<double, 5, 5> mat = Eigen::Matrix<double, 5, 5>::Random();
Eigen::JacobiRotation<double> temp_GR;
for (int n = 0; n < mat.cols(); ++n) {
  for (int m = (int)mat.rows() - 1; m > n; m--) {
    // Givens matrix G
    temp_GR.makeGivens(mat(m - 1, n), mat(m, n));
    (mat.block(m - 1, n, 2, mat.cols() - n)).applyOnTheLeft(0, 1, temp_GR.adjoint());
  }
}

Jacobi rotation

Householder 变换

豪斯霍尔德变换（Householder transformation）或译“豪斯霍德转换”，又称初等反射（Elementary reflection），这一变换将一个向量变换为由一个超平面反射的镜像，是一种线性变换。其变换矩阵被称作豪斯霍尔德矩阵，在一般内积空间中的类比被称作豪斯霍尔德算子。超平面的法向量被称作豪斯霍尔德向量。

豪斯霍尔德变换可以将向量的某些元素置零，同时保持该向量的范数不变。例如，将非零列向量 \(\mathbf{x}=\left[x_{1}, \dots, x_{n}\right]^{T}\) 变换为单位基向量 \(\mathbf{e}=[1,0, \ldots, 0]^{T}\) 的豪斯霍尔德矩阵为

\[ \mathbf{H}=\mathbf{I}-\frac{2}{\langle\mathbf{v}, \mathbf{v}\rangle} \mathbf{v} \mathbf{v}^{H} \]

其中豪斯霍尔德向量 \(\mathbf{v}\) 满足：

\[ \mathbf{v}=\mathbf{x}+\operatorname{sgn}\left(\mathbf{x}_{1}\right)\|\mathbf{x}\|_{2} \mathbf{e}_{1} \]

Matrix Decomposition

EVD (Eigen Decomposition)

\[ A = VDV^{-1} \]

• \(A\) 是 方阵；\(D\) 是 对角阵，其 特征值从大到小排列；\(V\) 的列向量为 特征向量
• 若 \(A\) 为 对称阵，则 \(V\) 为 正交矩阵，其列向量为 \(A\) 的 单位正交特征向量

SVD (Singular Value Decomposition)

• 谈谈矩阵的 SVD 分解

\[ A = UDV^T \]

• \(A\) 为 \(m \times n\) 的矩阵；\(D\) 是 非负对角阵，其 奇异值从大到小排列；\(U\)、\(V\) 均为 正交矩阵

SVD分解十分强大且适用，因为任意一个矩阵都可以实现SVD分解，而特征值分解只能应用于方阵。

奇异值与特征值

\[ AV = UD \Rightarrow Av_i = \sigma_{i} u_i \Rightarrow \sigma_{i} = \frac{Av_i}{u_i} \]

\[ A^T A = (V D^T U^T) (U D V^T) = V D^2 V^T \]

\[ A A^T = (U D V^T) (V D^T U^T) = U D^2 U^T \]

• \(A^T A\) 的 特征向量 组成的是SVD中的 \(V\) 矩阵
• \(A A^T\) 的 特征向量 组成的是SVD中的 \(U\) 矩阵
• \(A^T A\) 或 \(A A^T\) 的 特征值 \(\lambda_i\) 与 \(A\) 的 奇异值 \(\sigma_i\) 满足 \(\sigma_i = \sqrt{\lambda_i}\)

PCA

奇异值减少得特别快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上，可以用 最大的 \(k\) 个的奇异值和对应的左右奇异向量 来近似描述矩阵

\[ A_{m \times n} = U_{m \times m} D_{m \times n} V_{n \times n}^T \approx U_{m \times k} D_{k \times k} V_{k \times n}^T \]

LU Decomposition

\[ A = LU \]

• \(A\) 是 方阵；\(L\) 是 下三角矩阵；\(U\) 是 上三角矩阵

PLU 分解

\[ A = PLU \]

事实上，PLU 分解有很高的数值稳定性，因此实用上是很好用的工具。

LDU 分解

\[ A = LDU \]

Cholesky Decomposition

• Cholesky decomposition

\[ A = LDL^T \]

• \(A\) 是 方阵，正定矩阵；\(L\) 是 下三角矩阵

classic:

\[ A = LL^T \\[2ex] A^{-1} = (L^T)^{-1} L^{-1} = (L^{-1})^T L^{-1} \]

LDLT

• LDLT for Checking Positive Semidefinite Matrix's Singularity

QR Decomposition

• QR decomposition

\[ A = QR \]

• \(A\) 为 \(m \times n\) 的矩阵；\(Q\) 为 酉矩阵；\(R\) 是 上三角矩阵

Four Fundamental Subspaces

• 零空间 与 行空间 正交
• 左零空间 与 列空间 正交

column space (the range or image) \(C(A)\)

In linear algebra, the column space (also called the range or image) of a matrix A is the span (set of all possible linear combinations) of its column vectors. The column space of a matrix is the image or range of the corresponding matrix transformation.

row space \(C(A^T)\)

nullspace \(N(A)\)

\[ A x = 0 \]

The nullity of a matrix is the dimension of the null space.

The rank and nullity of a matrix A with n columns are related by the equation:

\[ \operatorname{rank}(A) + \operatorname{nullity}(A) = n \]

left nullspace \(N(A^T)\)

\[ A^T x = 0 \longrightarrow x^T A = 0 \]

左零空间 求解

已知 \[ A \in \mathbb{R}^{m \times n}, \quad \operatorname{rank}(A) = r = n, \quad m > n \]

SVD

\[ \begin{aligned} A_{m \times n} &= U_{m \times m} \cdot {\Sigma}_{m \times n} \cdot V_{n \times n}^T \\ &= \left[\begin{array}{ccc|ccc} u_{1} & \cdots & u_{r} & u_{r+1} & \cdots & u_{m} \end{array}\right] \left[\begin{array}{ccc|c} \sigma_{1} & & & \\ & \ddots & & 0 \\ & & \sigma_{r} & \\ \hline & 0 & & 0 \end{array}\right] \left[\begin{array}{c} v_{1}^{T} \\ \vdots \\ v_{r}^{T} \\ \hline v_{r+1}^{T} \\ \vdots \\ v_{n}^{T} \end{array}\right] \\ &= \begin{bmatrix} {U_1}_{m \times r} & {U_2}_{m \times (m-r)} \end{bmatrix} \cdot \begin{bmatrix} {\Sigma}_r & 0 \\ 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} {V_1}_{n \times r}^T \\[3pt] {V_2}_{n \times (n-r)}^T \end{bmatrix} \\ &= U_1 \cdot \Sigma_r \cdot V_1^T \\ &= \sum_{i=1}^r \sigma_i u_i v_i^T \end{aligned} \]

nullspace

\[ A \cdot V_2 = 0 \longrightarrow N(A) = V_2 \in \mathbb{R}^{n \times (n-r)} \]

left nullspace

\[ U_2^T \cdot A = 0 \longrightarrow N(A^T) = U_2 \in \mathbb{R}^{(m-r) \times m} \]

column space or the range (????)

\[ C(A) = U_1^T \in \mathbb{R}^{r \times m} \]

QR

\[ \begin{aligned} A_{m \times n} &= Q_{m \times m} \cdot R_{m \times n} \\ &= \begin{bmatrix} {Q_1}_{m \times r} & {Q_2}_{m \times (m-r)} \end{bmatrix} \begin{bmatrix} R_1 \\ 0 \end{bmatrix} \end{aligned} \]

left nullspace

\[ Q_2^T \cdot A = 0 \longrightarrow N(A^T) = Q_2 \in \mathbb{R}^{(m-r) \times m} \]

线性方程组

非齐次线性方程组

\[ A_{m \times n} x = b_{m \times 1} \]

在非齐次方程组中，A到底有没有解析解，可以由增广矩阵来判断：

• r(A) > r(A | b) 不可能，因为增广矩阵的秩大于等于系数矩阵的秩
• r(A) < r(A | b) 方程组无解；
• r(A) = r(A | b) = n，方程组有唯一解；
• r(A) = r(A | b) < n，方程组无穷解；

非齐次线性方程组的最小二乘问题

\[ x^* = \arg \min_x{\|Ax - b\|}_2^2 \]

m个方程求解n个未知数，有三种情况：

• m=n
  • 且A为非奇异，则有唯一解 \(x=A^{-1}b\)
• m>n，超定问题（overdetermined）
  • \(x=A^{+}b\)
• m<n，欠定问题（underdetermined）

齐次线性方程组

\[ A_{m \times n} x = 0 \]

齐次线性方程 解空间维数=n-r(A)

• r(A) = n
  • A 是方阵，该方程组有唯一的零解
  • A 不是方阵(m>n)，解空间只含有零向量
• r(A) < n
  • 该齐次线性方程组有非零解，而且不唯一（自由度为n-r(A))

齐次线性方程组的最小二乘问题

\[ \min{\|Ax\|}_2^2 \quad s.t. \quad \|x\| = 1 \]

• 最小二乘解为 矩阵 \(A^TA\) 最小特征值所对应的特征向量
• \(\text{EVD}(A^{T}A)=[V,D]\)，找最小特征值对应的V中的特征向量
• \(\text{SVD}(A)=[U,S,V]\)，找S中最小奇异值对应的V的右奇异向量

Solver

直接法

• Choleskey
• QR

迭代法

CG (Conjugate Gradient, 共轭梯度法)

PCG (Preconditioned Conjugate Gradient)

梯度下降法 vs 共轭梯度法

with Eigen

• Eigen 3.2稀疏矩阵入门

• Catalogue of dense decompositions

• Benchmark of dense decompositions

• Solving linear least squares systems
  • SVD decomposition (the most accurate but the slowest)
  • QR decomposition
  • normal equations (the fastest but least accurate)

• Solving Sparse Linear Systems