【多视图几何】TUM 课程第1章数学基础：线性代数

在 YouTube 上找到了慕尼黑工业大学（Technische Universitaet München）计算机视觉组 Daniel Cremers 教授的 Multiple View Geometry 课程。容易理解，收获颇多，写下笔记以巩固所学。

课程的 YouTube 地址为：https://www.youtube.com/playlist?list=PLTBdjV_4f-EJn6udZ34tht9EVIW7lbeo4 。视频评论区可以找到课程所使用课件与练习题的下载地址。第一个视频底部可以找到参考书名 An Invitation to 3-D Vision: From Images to Geometric Models 。

课程第1章介绍了线性代数的基础，MVG 课程前半部分以线性代数的形式对问题进行建模，将模型是否有解、有多少解转化为矩阵秩的问题。

1. 线性空间

1.1 线性空间定义

Vector Space 也叫 Linear Space，向量空间或线性空间。线性空间是一个集合加一个数域（一般为实数 $ mathbb{R} $），这个集合需要满足加法与乘法封闭。封闭指集合中的元素经过运算后得到的元素依旧在这个集合中。

这两个封闭的性质用映射表示为：

[+ : V imes V ightarrow V ]

[centerdot : mathbb{R} imes V ightarrow V ]

$ V $ 中元素经过运算，依旧在 $ V $ 中。

1.2 子空间

线性空间存在子空间（Subspace），子空间也是一个线性空间，满足加法与乘法的封闭。子空间与母空间之间的关系是子空间中集合 (W) 是母空间集合 (V) 的真子集，即 $ W subset V $，子空间的数域与母空间的数域完全相等。

由于 $ 0 in mathbb{R} $，所以线性空间一定包含0元（幺元）。

三维空间包含幺元，也就是原点 $ (0, 0, 0)^T $。三维空间的子空间是二维空间，二维空间（平面）也一定包含幺元，所以作为三维空间子空间的平面一定过原点。

1.3 线性无关与基底

一个向量的集合 (S = {v_1, dots, v_k} subset V) 张成的子空间指这些向量的线性组合：

[ extrm{span}(S) = { v in V | v = Sigma_{i = 1}^{k} alpha_i v_i} ]

集合 $ S $ 线性无关（linearly independent）指将这些向量线性组合成0元时所有向量的系数都为0，即：

[Sigma_{i = 1}^{k} alpha_i v_i = 0 Rightarrow alpha_i = 0 forall i ]

线性组合（Linear Combination）指将所有元素乘以一个实数，然后求和。

如果这些系数中存在不为 0 的数，那么这个集合就叫做线性相关。

线性空间 $ V $ 的基底（Basis）是一集合 (B = { v_1, dots, v_n })，这个集合线性无关，并且其中的元素能够张成整个线性空间。

基底 $ S $ 是线性无关向量的最大集合，即在基底 $ S $ 中再增加一个向量，集合会变成线性相关。所以线性空间 $ V $ 中的任意一个向量都可以使用基底线性表示。

基底的三个性质：
假设 $ B $ 与 $ B' $ 是线性空间 $ V $ 的两个基底，
i. $ B $ 与 $ B' $ 中向量的个数相同，向量的个数 $ n $ 称作线性空间 $ V $ 的维度（Dimension）。
ii. 线性空间 $ V $ 中的任意一个向量都可以表示为基底 (B = { v_1, dots, v_n }) 的线性组合：

[v = Sigma^n_{i=1} alpha_ib_i ]

iii. 基底 $ B' $ 中的向量都可以表示为基底 $ B $ 中向量的线性组合：

[b'_i = Sigma^n_{j=1}alpha_{ji}b_j ]

用矩阵的形式表示这个基底变换（Basis Transform），$ B' = BA $，其中 (B equiv (b_1, dots, b_n), B' equiv (b'_1, dots, b'_n)) 将基底行的形式排列，$ A equiv [alpha_{ij}] $ 是一个方阵。

1.4 内积与克罗内克积

在线性空间中可以定义内积（Inner Product）：

[<centerdot, centerdot> : V imes V ightarrow mathbb{R} ]

内积是一种二元运算，将两个向量映射到实数域内，并且运算满足三条性质：

线性（Linear）：$ <u, alpha v + eta w> = alpha <u, v> + eta <u, w> $
对称（Symmetric）：$ <u, v> = <v, u> $
正定（Positive Definite）：$ <v, v> ge 0 $，且 $ <v, v> = 0 Leftrightarrow v = 0 $

由内积可以定义范数（Norm）

[|centerdot| : V ightarrow mathbb{R}, |v| = sqrt{<v, v>} ]

与度量（Metric）

[d : V imes V ightarrow mathbb{R}, d(v, w) = |v - w| = sqrt{<v-w, v-w>} ]

度量可以用于描述长度或距离，定义了度量的线性空间称作是度量空间（Metric Space）。

规范内积（Canonical Inner Product）是内积的一种“实现方式”，也称作点积（(Dot Product)[https://en.wikipedia.org/wiki/Dot_product]），线性空间 $ V = mathbb{R}^n $ 中定义在规范基底 $ B = I_n $ 上的点积：

[<x, y> = x^T y = Sigma^n_{i=1} x_i y_i ]

对应的范数就称作 $ L_2 $ 范数（$ L_2 $-norm）或者欧几里德范数（Euclidean Norm）：

[|x|_2 = sqrt{x^Tx} = sqrt{x_1^2 + dots + x_n^2} ]

如果不把点积定义在规范基底 $ I_n $ 上，而定义在基底 $ B' $ 上（$ I_n = B'A^{-1} (，) A $ 是从标准基底 $ I_n $ 到 $ B' $ 的变换矩阵），在新坐标 $ (x', y') $ 下的点积与旧坐标 $ (x, y) $下的点积的关系：

[<x, y> = x^Ty = (Ax')^T(Ay') = x'^TA^TAy' equiv <x', y'>_{A^TA} ]

$ <x', y'>_{A^TA} $ 被称作从矩阵 $ A $ 诱导出的内积。

最后，两个向量 $ v, w $ 当且仅当 $ <v, w> = 0 $ 时，它们是正交（Orthogonal）的。

两个矩阵 $ A in mathbb{R}^{m imes n}, B in mathbb{R}^{k imes l} $ 的克罗内克积（Kronecker Product）

[ A otimes B = egin{bmatrix} a_{11}B dots a_{1n}B \ vdots quad ddots quad vdots \ a_{m1}B dots a_{mn}Bend{bmatrix} in mathbb{R}^{mk imes nl}]

形式上是将 $ A $ 中的每一个元素替换成该元素与 $ B $ 的数乘。

有了克罗内克积就可以定义矩阵的 stack，矩阵 $ A = [a_1, a_2 dots a_n] in mathbb{R}^{m imes n} $ 是将 $ A $ 的所有列向量组合成一个列向量：

[A^s equiv egin{bmatrix} a_1 \ vdots \ a_n end{bmatrix} in mathbb{R}^{mn} ]

在 Matlab 中可以表示为

A_stack = kron(ones(size(A, 2), 1), A);

克罗内克积有一个非常常用的转换：

[u^TAv = (v otimes u)^T A^s ]

如果 (u^TAv = 0) ，使用这种转换就可以形成一个线性系统。

2. 线性变换与矩阵

2.1 线性变换

线性变换是指在两个线性空间之间的映射，$ L: V ightarrow W $，这种映射满足两个条件：

[L(x+y) = L(x) + L(y), forall x, y in V ]

[L(alpha x) = alpha L(x), forall x in V, alpha in mathbb{R} ]

这种映射可以认为是对线性空间 $ V $ 中的基底进行变换，在标准正交基底 $ {e_1, dots, e_n} $ 的情况下：

[L(x) = Ax, forall x in V ]

[A = (L(e_1), L(e_2), dots, L(e_n)) in mathbb{R}^{m imes n} ]

所有 $ m imes n $ 矩阵组成的集合写作 $ mathscr{M}(m, n) $，当 (m = n) 时，$ mathscr{M}(m, n) equiv mathscr{M}(n) $，就形成了了数域 (mathbb{R}) 中的一个环（Ring），所谓的环就是在这个矩阵集合对矩阵的加法、乘法封闭。

线性变换是线性空间之间满足特定条件的映射，这种映射一般使用矩阵描述。

2.2 群与矩阵

群指线性变换的集合加上一种运算，$ circ: G imes G ightarrow G $ ，并且满足四个条件：

封闭（Closure）：$ g_1 circ g_2 : G, forall g_1, g_2 in G $
结合（Associativity）：$ (g_1 circ g_2)circ g_3 = g_1 circ (g_2 circ g_3), forall g_1, g_2, g_3 in G $
单位元（Identity Element）：$ exists e in G : e circ g = g circ e = g, forall g in G $
逆元（Inverse Element）：$ exists g^{-1} in G: g circ g^{-1} = g^{-1} circ g = e, forall g in G $

两个重要的群：一般线性群（General Linear Group）$ GL(n) $ 与特殊线性群（Special Linear Group）$ SL(n) $。

$ GL(n) $ 定义在所有可逆的 $ n imes n $ 矩阵组成的集合 (mathscr{M}(n)) 与矩阵乘法之上。

$ SL(n) $ 的集合是 $ GL(n) $ 集合的子集，$ SL(n) $ 要求集合元素 $ A $ 满足 $det(A) = 1 $, $ SL(n)$ 不仅对矩阵乘法封闭，也对矩阵逆封闭。

群 $ G $ 可以使用矩阵进行表示（Matrix Representation），以方便对群的性质进行研究（转化为对矩阵性质的研究）。群转换为矩阵的形式进行描述需要群中的元素（线性变换）能够在一般线性群中找到唯一的像，且群中不同元素的像不相同，这是一个单射映射（Injection）：

[R: G ightarrow GL(n) ]

这种映射还需要满足两个条件：

[R(e) = I_{n imes n}, R(g circ h) = R(g)R(h), forall g, h in G ]

即幺元的像是单位阵，群内的运算对应矩阵的乘法。

2.3 MVG 中涉及的群

2.3.1 仿射群（Affine Group $ A(n) $）

仿射变换（Affine Transformation） $ L : mathbb{R}^n ightarrow mathbb{R}^n $ 由一个矩阵 $ A in GL(n)$ 和一个向量 $ v in mathbb{R}^n $ 定义：

[L(x) = Ax + b ]

所有的这种仿射变换组成的集合称作仿射群（Affine Group），用 $ A(n) $ 表示。

如果用齐次坐标表示向量，仿射群可以使用矩阵的形式表示：

[L : mathbb{R}^{n+1} ightarrow mathbb{R}^{n+1}, egin{bmatrix} x \ 1 end{bmatrix} mapsto egin{bmatrix} A quad b \ 0 quad 1end{bmatrix} egin{bmatrix} x \ 1 end{bmatrix} ]

[A(n) = left{egin{bmatrix} A quad b \ 0 quad 1end{bmatrix} left. ight| A in GL(n), v in mathbb{R}^n ight} ]

2.3.2 正交群（Orthogonal Group $ O(n) $）

矩阵 $ R $ 正交（Orthogonal）指满足条件：

[<Rx, Ry> = <x, y>, forall x, y in mathbb{R}^{n} ]

所有的 $ n imes n $ 的正交矩阵组成正交群（Orthogonal Group） $ O(n) $，由上式可得：

[x^TR^TRy = x^Ty, forall x, y in mathbb{R}^{n} ]

所以 $ R^TR = RR^T = I $，得到正交群的定义：

[O(n) = { R in GL(n) | R^TR = I } ]

[det(R^TR) = det(R)^2 = det(I) = 1 ]

[det(R) in {pm1} ]

正交群有一子群叫做特殊正交群（Special Orthogonal Matrix）$ SO(n) $，特殊正交群中的元素 (det(R) = +1)。特殊正交群可以看做特殊线性群与正交群的交集，(SO(n) = O(n) cap SL(n))。

$ SO(3) $ 对应三维空间中所有的旋转矩阵。

2.3.3 欧几里德群（Euclidean Group $ E(n) $）

欧式变换（Euclidean Transformation）由一个正交矩阵 $ R in O(n) $ 和一个向量 $ T in mathbb{R}^n $ 定义：

[L: mathbb{R}^n ightarrow mathbb{R}^n, x mapsto Rx + T ]

写作齐次坐标，得到欧几里德群的定义：

[E(n) = left{ egin{bmatrix} R quad T \ 0 quad 1 end{bmatrix} left. ight| R in O(n), T in mathbb{R}^n ight} ]

注意偶几里德群里面的矩阵 $ R $ 是正交阵，其行列式为 (pm 1)。对 $ R $ 进行进一步的限制 $ R in SO(n) $，就能得到特殊欧几里德群（Speical Euclidean Group）的定义：

[SE(n) = left{ egin{bmatrix} R quad T \ 0 quad 1 end{bmatrix} left. ight| R in SO(n), T in mathbb{R}^n ight} ]

$ SE(3) $ 对应三维空间的刚体变换（Rigid Transformation）。

2.3.4 小结

[SO(n) subset O(n) subset GL(n) ]

[SE(n) subset E(n) subset A(n) subset GL(n+1) ]

3. 矩阵的性质

矩阵的性质就是矩阵的秩、特征值、特征向量。

3.1 秩

矩阵 $ A in mathbb{R}^{m imes n}$ 表示从线性空间 $ mathbb{R}^n $ 到线性空间 $ mathbb{R}^m $ 的映射，它的值域（Range）$ rang(A) $ 表示 $ A $ 在 $ mathbb{R}^m $ 中能映射到的范围：

[rang(A) = { y in mathbb{R}^m | exists x in mathbb{R}^n : Ax = y } ]

矩阵 $ A $ 的核（Kernel || Nullspace）是在 $ mathbb{R}^n $ 能被矩阵 $ A $ 映射到0的元素的集合：

[null(A) = ker(A) = {x in mathbb{R}^n | Ax = 0 } ]

矩阵的秩（Rank）是矩阵值域的维度：

[rank(A) = dim(range(A)) ]

秩的性质：

$ rank(A) = n - dim(ker(A)) $；
$ 0 le rank(A) le min{m, n} $；
$ rank(A) $ 是 $ A $ 最大线性无关行（列）向量的个数；
$ rank(A) $ 是 $ A $ 最高阶非零余子式的阶数；
$B in mathbb{R}^{n imes k}, rank(A) + rank(B) - n le rank(AB) le min{ rank(A), rank(B) } $；
对于任意两个非奇异矩阵 (C in mathbb{R}^{m imes m}, D in mathbb{R}^{n imes n})，$ rank(A) = rank(CAD) $。

3.2 特征值与特征向量

特征值与特征向量（Eigenvalues and Eigenvectors）有左右之分，一般情况下默认为右特征值与右特征向量。

$ A in mathbb{C}^{m imes n} $ 的右特征值是一个非零的向量 $ v in mathbb{C}^n $：

[Av = lambda v, lambda in mathbb{C} ]

$ A in mathbb{C}^{m imes n} $ 的左特征值是一个非零的向量 $ v in mathbb{C}^m $：

[v^TA = lambda v^T, lambda in mathbb{C} ]

相对应的 (lambda) 就称作 $ A $ 的特征值。

矩阵 $ A $ 所有特征值组成的集合叫做矩阵 $ A $ 的谱（Spectrum），记作 (sigma(A))。

(A in mathbb{R}^{n times n})，特征值与特征向量的性质：

左右特征值是一一对应的，对 $ Av = lambda v, lambda in mathbb{R}$，存在左特征值 (eta in mathbb{R}^n) 使得 $ eta ^TA = lambda A $，左右转置可知 $ sigma(A^T) = sigma(A) $；
不同特征值的特征向量之间线性无关；
$ sigma(A) $ 是特征多项式 (det(lambda I - A) = 0) 的根，所以 (det(A)) 等于所有特征值的乘积；
若 (B = PAP^{-1})，$ P $ 是可逆矩阵，那么 (sigma(B) = sigma(A))；
特征值与其共轭复数成对出现，即 (lambda in mathbb{C}) 是 $ A $ 的一个特征值，$ ar{lambda} $ 也是 $ A $ 的一个特征值，有 (sigma(A) = ar{sigma(A)})。

3.3 对称阵与反对称阵

若方阵 $S in mathbb{R}^{n imes n} $ 满足 (S^T = S)，则称 $ S $ 是对称阵（Symmetric Matrix）。若对称阵满足 $ x^TSx ge 0, forall x in mathbb{R}^n $ 则称其半正定的（Positive Semi-Definite），记作 $ S ge 0 $。若对称阵满足 $ x^TSx gt 0 $ ，则称其正定的（Positive Definite）。

实对称阵 $ S in mathbb{R}^{n imes n} $ 具有以下性质：

所有的特征值都为实数，即 (sigma(S) in mathbb{R})；
特征值互异的特征向量正交，即 $ S v_i = lambda_i v_i, S v_j = lambda_j v_j, lambda_i e lambda_j Rightarrow v_i^Tv_j = 0 $；
有 (n) 个单位正交的特征向量，这些特征向量组成线性空间 (mathbb{R}^n) 的一组基底，将特征向量组成矩阵 (V = (v_1, dots, v_n) in O(n))，特征值组成对角矩阵 (Lambda = diag{ lambda_1, dots, lambda_n })，$ S $ 可以用这两个矩阵分解 $ S = V Lambda V^T $；
$ S $ 所有的特征值为非负数，则 $ S $ 为半正定矩阵； $ S $ 所有的特征值为正数，则 $ S $ 为正定矩阵。

矩阵范数（Matrix Norm）有2范数（2-norm）和F范数（Frobenius norm）：

矩阵 $ A in mathbb{R}^{m imes n} $

[{|A|}_2 equiv max_{|x|_2=1} |Ax|_2 = max_{|x|_2=1}sqrt{<x, A^TAx>} ]

[{|A|}_f equiv sqrt{Sigma_{i,j}a_{ij}^2} = sqrt{trace(A^TA)} ]

矩阵 (A^TA) 是对称阵，且半正定，所以 $ A^TA $ 可分解为 (A^TA = Vdiag{ sigma_1^2, dots, sigma_n^2}V^T, sigma_1^2 ge sigma_i^2 ge 0)，可得

[{| A |}_2 = sigma_1 ]

[{| A |}_f = sqrt{sigma_1^2 + dots + sigma_n^2} ]

若方阵 $A in mathbb{R}^{n imes n} $ 满足 (A^T = -A)，则称 $ A $ 是反对称阵（Skew-symmetric Matrix）。

反对称阵具有以下性质：

所有特征值都为0或者纯虚数；
可以分解为 $ A = V Lambda V^T $，其中 (Lambda) 是块对角矩阵 $$ Lambda = diag{ A_1, dots, A_m, 0, dots, 0 }, A_i = egin{bmatrix} 0 quad a_i -a_i quad 0 end{bmatrix} in mathbb{R}^{2 imes2}, i = 1, dots, m$$；
秩为偶数。

4. 奇异值分解

矩阵 (A in mathbb{R}^{m imes n}, m gt n, rank(A) = p)，则 $ A $ 能够分解为

[A = U Sigma V^T ]

其中

$ U in mathbb{R}^{m imes p} $，列向量单位正交；
$ V in mathbb{R}^{n imes p} $，列向量单位正交；
$ Sigma in mathbb{R}^{p imes p}, Sigma = diag{sigma_1, dots, sigma_p}, sigma_1 ge dots ge sigma_n$。

奇异值分解的应用，广义逆（Moore–Penrose Pseudoinverse）：

[A^dagger = V Sigma^dagger U^T, Sigma^dagger = egin{bmatrix} Sigma^{-1}_1 quad 0 \ 0 quad quad 0 end{bmatrix} in mathbb{R}^{m imes n} ]

广义逆具有以下的性质：

[A^dagger A A^dagger = A^dagger, A A^dagger A = A ]

广义逆可用于解线性系统 (Ax = b, A in mathbb{R}^{m imes n}, rank(A) le min(m, n))，(x_{min} = A^dagger b) 是在所有最小化误差 $ | Ax-b |^2 $ 的解中，自身模 (|x|) 最小的那个。

【多视图几何】TUM 课程 第1章 数学基础：线性代数