Multiple View Geometry - Lecture 1

Chapter 1: Linear Algebra

Vector Spaces(向量空间)

• 线性空间 / 域 $\mathbb{R}$ 上的向量空间

域 $\mathbb{R}$ 上的集合 $\mathbb{V}$ 对向量加法(vector summation)和数乘(scalar multiplication)封闭

$$\begin{align} +:\mathbb{V}\times\mathbb{V}\rightarrow\mathbb{V} \notag\\ \cdot:\mathbb{R}\times\mathbb{V}\rightarrow\mathbb{V} \notag \end{align}$$

即：$\forall \boldsymbol{v_1},\boldsymbol{v_2}\in\mathbb{V},\forall \alpha,\beta\in\mathbb{R}, \alpha\boldsymbol{v_1}+\beta\boldsymbol{v_2}\in\mathbb{V}$

加法和数乘具体定义和满足的条件见矩阵分析第一讲

• 子空间

$\mathbb{W}\subset\mathbb{V},\boldsymbol{0}\in\mathbb{W}$，且对加法和数乘封闭，则称 $\mathbb{W}$ 为向量空间 $\mathbb{V}$ 的子空间

• 线性无关

一组向量 $\mathbb{S}=\{\boldsymbol{v_1},…,\boldsymbol{v_k}\}\subset\mathbb{V}$ 的生成子空间定义为：

$$\text{span}(\mathbb{S})=\{\boldsymbol{v}\in\mathbb{V}|\boldsymbol{v}=\sum^k_{i=1}\alpha_i\boldsymbol{v_i}\}$$

集合 $\mathbb{S}$ 线性无关的条件：

$$\sum^k_{i=1}\alpha_i\boldsymbol{v_i}=0\Rightarrow\alpha_i=0\ \forall i$$

即集合中的所有向量都不能被其他向量所表示，反之则称该集合线性相关

• 线性空间的一组基(basis)

向量组 $\mathbb{B}=\{\boldsymbol{v_1},…\boldsymbol{v_n}\}$ 线性无关且生成子空间为 $\mathbb{V}$ ，则称向量组 $\mathbb{B}$ 为线性空间 $\mathbb{V}$ 的一组基，即线性无关向量的最大集合

若向量组 $\mathbb{B}$ 和 $\mathbb{B’}$ 是线性空间 $\mathbb{V}$ 的两组基，那么有以下三个结论

1. $\mathbb{B}$ 和 $\mathbb{B’}$ 中的向量个数相等，均为 $n$ ，称为线性空间 $\mathbb{V}$ 的维度

2. $\forall \boldsymbol{v}\in\mathbb{V}$ 都可由向量组 $\mathbb{B}$ 中的基向量唯一线性表出

3. 特殊地，向量组 $\mathbb{B’}$ 中的所有向量都可由 $\mathbb{B}$ 线性表出：

   $$b'_i=\sum^n_{j=1}a_{ji}b_j$$

   该基变换中的系数 $a_{ji}$ 组成矩阵 $\boldsymbol{A}$，$\boldsymbol{B}=[b_1,…b_n],\boldsymbol{B’}=[b_1’…,b_n’]$ ，故上式可写作：

   $$\boldsymbol{B'}=\boldsymbol{BA}\Leftrightarrow\boldsymbol{B}=\boldsymbol{B'A^{-1}}$$

• 内积(Inner Product)

  在向量空间中定义内积（点积）$\langle\cdot,\cdot\rangle:\mathbb{V}\times\mathbb{V}\rightarrow\mathbb{R}$ ，满足以下三个条件：

  1. 线性性：$\langle\boldsymbol{u},\alpha\boldsymbol{v}+\beta\boldsymbol{w}\rangle=\alpha\langle\boldsymbol{u},\boldsymbol{v}\rangle+\beta\langle\boldsymbol{u},\boldsymbol{w}\rangle$
  2. 对称性：$\langle\boldsymbol{u},\boldsymbol{v}\rangle=\langle\boldsymbol{v},\boldsymbol{u}\rangle$
  3. 正定性：$\langle\boldsymbol{v},\boldsymbol{v}\rangle\geq0$ 且 $\langle\boldsymbol{v},\boldsymbol{v}\rangle=0\Leftrightarrow\boldsymbol{v}=\boldsymbol{0}$

  从而定义了一个范数(norm) ：

  $$|\cdot|:\mathbb{V}\rightarrow\mathbb{R},|\boldsymbol{v}|=\sqrt{\langle\boldsymbol{v},\boldsymbol{v}\rangle}$$

  和一个度量(metric) ：

  $$\text{d}:\mathbb{V}\times\mathbb{V}\rightarrow\mathbb{R},\text{d}(\boldsymbol{v},\boldsymbol{w})=|\boldsymbol{v}-\boldsymbol{w}|=\sqrt{\langle\boldsymbol{v}-\boldsymbol{w},\boldsymbol{v}-\boldsymbol{w}\rangle}$$

  分别用来计算向量长度和向量间的距离，这使得 $\mathbb{V}$ 成为一个度量空间，又因为该度量是由向量内积定义的，所以又称 $\mathbb{V}$ 为希尔伯特空间(Hilbert Space)

• 标准内积与生成内积(Canonical Inner Product and Induced Inner Product)

  特殊地，在 $\mathbb{V}=\mathbb{R}$ 时，可以由标准基 $\boldsymbol{B}=\boldsymbol{I}_n$ (n维单位矩阵)定义标准内积：$\langle \boldsymbol{x},\boldsymbol{y}\rangle=\boldsymbol{x}^T\boldsymbol{y}=\sum^n_{i=1}x_iy_i$ ，从而定义出了标准 $L_2$ 范数（欧几里得范数）$|\boldsymbol{x}|=\sqrt{\boldsymbol{x}^T\boldsymbol{x}}=\sqrt{x_1^2+…+x_n^2}$

  对于一个新给出的基底 $\boldsymbol{B}’$ ，有基变换 $\boldsymbol{A}$ 使得 $\boldsymbol{I}=\boldsymbol{B}’\boldsymbol{A}^{-1}$ ，那么标准内积用新坐标 $\boldsymbol{x}’,\boldsymbol{y}’$ 可表示为：$\langle\boldsymbol{x},\boldsymbol{y}\rangle=\boldsymbol{x}^T\boldsymbol{y}=(\boldsymbol{Ax}’)^T(\boldsymbol{Ay}’)=\boldsymbol{x}’^T\boldsymbol{A}^T\boldsymbol{A}\boldsymbol{y}’\equiv\langle\boldsymbol{x}’,\boldsymbol{y}’\rangle_{\boldsymbol{A}^T\boldsymbol{A}}$ ，后者成为变换矩阵 $\boldsymbol{A}$ 下的生成内积

  当且仅当 $\langle\boldsymbol{v},\boldsymbol{w}\rangle=0$ 时向量正交

• (新概念) 矩阵的 Kronecker积 和 Stack（堆）

  给定两个任意大小的矩阵 $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ 和 $\boldsymbol{B}\in\mathbb{R}^{k\times l}$ ，定义它们的 Kronecker积 如下：

  $$\boldsymbol{A}\otimes\boldsymbol{B}\equiv \left( \begin{matrix} a_{11}\boldsymbol{B} \ \cdots \ a_{1n}\boldsymbol{B}\\ \vdots \quad \ddots \quad \vdots \\ a_{m1}\boldsymbol{B} \ \cdots \ a_{mn}\boldsymbol{B} \end{matrix} \right) \in\mathbb{R}^{mk\times nl}.$$

  矩阵 $\boldsymbol{A}$ 的 Stack (堆) $\boldsymbol{A}^s$ 则定义为一个由所有n个列向量纵向堆叠而成的的列向量：

  $$\boldsymbol{A}^s\equiv \left( \begin{matrix} \boldsymbol{a_1}\\ \vdots \\ \boldsymbol{a_n} \end{matrix} \right)\in\mathbb{R}^{mn}.$$

  上述定义使得代数表达式可以被重写得更加直观，例如：

  $$\boldsymbol{u}^T\boldsymbol{A}\boldsymbol{v}=(\boldsymbol{v}\otimes\boldsymbol{u})^T\boldsymbol{A}^s$$

  这其实是容易证明的：

  $$\begin{align} \boldsymbol{u}^T\boldsymbol{A}\boldsymbol{v} &=(\quad\quad)_{1\times m}\left(\begin{matrix}\quad\quad\\ \\ \end{matrix}\right)_{m\times n}\left(\begin{matrix}\\ \\\end{matrix}\right)_{n\times1} \notag\\ &=\left(\boldsymbol{u}^T\boldsymbol{a_1}\ ...\ \boldsymbol{u}^T\boldsymbol{a_n}\right)_{1\times n}\left(\begin{matrix}\\\\\end{matrix}\right)_{n\times1} \notag \\ &=\boldsymbol{u}^T\boldsymbol{a_1}v_1+...+\boldsymbol{u}^T\boldsymbol{a_n}v_n \notag \\ &=\boldsymbol{u}^Tv_1\cdot\boldsymbol{a_1}+...+\boldsymbol{u}^Tv_n\cdot\boldsymbol{a_n} \notag \\ &=\left(\boldsymbol{u}^Tv_1\ ...\ \boldsymbol{u}^Tv_n\right)\left(\begin{matrix}\boldsymbol{a_1}\\\vdots\\\boldsymbol{a_n}\end{matrix}\right) \notag \\ &=\left(\begin{matrix}v_1\boldsymbol{u}\\\vdots\\v_n\boldsymbol{u}\end{matrix}\right)^T\left(\begin{matrix}\boldsymbol{a_1}\\\vdots\\\boldsymbol{a_n}\end{matrix}\right) \notag \\ &=(\boldsymbol{v}\otimes\boldsymbol{u})^T\boldsymbol{A}^s \notag \end{align}$$

Linear Transformations and Matrices(线性变换和矩阵)

线性代数研究的是两个线性空间之间的线性变换，由于这些线性变换都可以用矩阵表示，所以线性代数相当于在研究矩阵的特性。

两个线性空间 $\mathbb{V}$ 和 $\mathbb{W}$ 之间的 线性变换(Linear Transformation) 是一个映射 $\boldsymbol{L}: \mathbb{V}\rightarrow\mathbb{W}$ ，它满足以下两个条件：

1. $\boldsymbol{L}(\boldsymbol{x}+\boldsymbol{y})=\boldsymbol{L}(\boldsymbol{x})+\boldsymbol{L}(\boldsymbol{y})\quad\forall\boldsymbol{x},\boldsymbol{y}\in\mathbb{V}$
2. $\boldsymbol{L}(\alpha\boldsymbol{x})=\alpha\boldsymbol{L}(\boldsymbol{x})\quad \forall\boldsymbol{x}\in\mathbb{V},\alpha\in\mathbb{R}$

由于线性性，线性变换 $\boldsymbol{L}$ 对空间 $\mathbb{V}$ 的操作可以唯一定义为对 $\mathbb{V}$ 上基向量的操作，对标准基 $\{\boldsymbol{\theta_1},…,\boldsymbol{\theta_n}\}$ 有：$\boldsymbol{L}(\boldsymbol{x})=\boldsymbol{Ax}\quad \forall\boldsymbol{x}\in\mathbb{V}$ 其中 $\boldsymbol{A}=(\boldsymbol{L}(\boldsymbol{\theta_1}),…,\boldsymbol{L}(\boldsymbol{\theta_n}))\in\mathbb{R}^{m\times n}$

所有 $m\times n$ 维实矩阵组成的集合记为 $\mathcal{M}(m,n)$ ，当 $m=n$ 时，集合 $\mathcal{M}(m,n)\equiv\mathcal{M}(n)$ 就形成了域 $\mathbb{R}$ 上的一个 环，即满足对矩阵乘法和矩阵加法封闭

• 线性群 $GL(n)$ 和 $SL(n)$

  群 的概念：集合 $\mathbb{G}$ 与集合 $\mathbb{G}$ 上定义的一种运算：$\circ :\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}$ 满足以下四个条件：

  1. 封闭性：$\boldsymbol{g}_1\circ\boldsymbol{g}_2\in\mathbb{G},\quad\forall\boldsymbol{g}_1,\boldsymbol{g}_2\in\mathbb{G}$
  2. 结合律：$(\boldsymbol{g}_1\circ\boldsymbol{g}_2)\circ\boldsymbol{g}_3=\boldsymbol{g}_1\circ(\boldsymbol{g}_2\circ\boldsymbol{g}_3),\quad\forall\boldsymbol{g}_1,\boldsymbol{g}_2,\boldsymbol{g}_3\in\mathbb{G}$
  3. 幺元：$\exists\boldsymbol{e}\in\mathbb{G},\ s.t.\ \boldsymbol{e}\circ\boldsymbol{g}=\boldsymbol{g}\circ\boldsymbol{e}=\boldsymbol{g},\quad \forall\boldsymbol{g}\in\mathbb{G}$
  4. 可逆性：$\exists\boldsymbol{g}^{-1}\in\mathbb{G},\ s.t.\ \boldsymbol{g}\circ\boldsymbol{g}^{-1}=\boldsymbol{g}^{-1}\boldsymbol{g}=\boldsymbol{e},\quad\forall\boldsymbol{g}\in\mathbb{G}$

  这样的集合就称为群 。

  • 所有可逆（非奇异）$n\times n$ 维实矩阵和矩阵乘法就构成了一个群，这个群称为 general linear group，记作 $GL(n)$ ，该群中包含了所有行列式非零的 $n\times n$ 维方阵；
  • 进一步，$GL(n)$ 中所有行列式为1的矩阵又组成了一个群，称为 special linear group ，记作 $SL(n)$ ，根据可逆性，该群中的方阵满足：$\text{det}(\boldsymbol{A}^{-1})=\text{det}(\boldsymbol{A})^{-1}$
• **群的矩阵表示**

  一个群 $G$ 有矩阵表示（可被视为矩阵群）的条件：

  • 存在一个群的同构映射（群同态）$R:G\rightarrow GL(n)$ .

  该映射保留了群 $G$ 的群结构，即保留了幺元、群乘、可逆性等：

  $$\begin{align} &R(e)=I_{n\times n} \notag \\ &R(g\circ h)=R(g)R(h),\ \ \forall g,h\in G \notag \\ &\text{if}\ \ g\circ g^{-1}=g^{-1}\circ g=e,\ \ \text{then}\ \ R(g)R(g^{-1})=I_{n\times n} \notag \end{align}$$

  之所以引进群的矩阵表示，是因为这能实现从研究矩阵群的特征角度来研究更抽象的群。

  例如：物体旋转运动构成了一个群，如果能用矩阵表示旋转，那么研究旋转群的特征会容易很多

• 仿射群 $A(n)$

  仿射变换 $L:\mathbb{R}^n\rightarrow \mathbb{R}^n$ 可以由一个矩阵 $\boldsymbol{A}\in GL(n)$ 和一个向量 $\boldsymbol{b}\in \mathbb{R}^n$ 唯一定义 ：

  $$L(\boldsymbol{x})=\boldsymbol{Ax+b}$$

  由这些仿射变换构成的集合称为 $n$ 维仿射群 ，记作 $A(n)$

  显然，上述定义的仿射变换 $L$ 不是个线性映射，除非 $\boldsymbol{b}=\boldsymbol{0}$。通过引入 齐次坐标 （将 $\boldsymbol{x}\in\mathbb{R}^n$ 表示为 $\left(\begin{matrix}\boldsymbol{x}\\1\end{matrix}\right)\in\mathbb{R}^{n+1}$ ）可以把 $L:\mathbb{R}^n\rightarrow \mathbb{R}^n$ 变成一个线性映射 $L:\mathbb{R}^{n+1}\rightarrow \mathbb{R}^{n+1}$ ：

  $$\left( \begin{matrix} \boldsymbol{x} \\ 1 \end{matrix} \right) \mapsto \left( \begin{matrix} \boldsymbol{A} \quad \boldsymbol{b} \\ \boldsymbol{0} \quad\ 1 \end{matrix} \right) \left( \begin{matrix} \boldsymbol{x} \\ 1 \end{matrix} \right)$$

  矩阵 $\left(
  \begin{matrix}
  \boldsymbol{A} \quad \boldsymbol{b} \\
  \boldsymbol{0} \quad\ 1
  \end{matrix}
  \right)\in GL(n+1)$ 称为 仿射矩阵 ，所有仿射矩阵构成了 $GL(n+1)$ 的一个子群

• 正交群 $O(n)$

  所有 $n\times n$ 的正交矩阵构成了正交群 $O(n)=\{\boldsymbol{R}\in GL(n)|\boldsymbol{R}^T\boldsymbol{R}=\boldsymbol{I}\}$ ，显然它是群 $GL(n)$ 的子群，且 $\text{det}(\boldsymbol{R}^T\boldsymbol{R})=(\text{det}(\boldsymbol{R}))^2=\text{det}(\boldsymbol{I})=1\Rightarrow\text{det}(\boldsymbol{R})\in\{+1,-1\}$

  将 $O(n)$ 满足 $\text{det}(\boldsymbol{R})=+1$ 的子群称为 特殊正交群 ，记作 $SO(n)$ ，显然 $SO(n)=O(n)\cap SL(n)$ 。特别地，$SO(3)$ 即为三维旋转矩阵构成的群（行列式为-1的矩阵为镜像矩阵）

• 欧氏群 $E(n)$

  由正交阵 $\boldsymbol{R}\in O(n)$ 和向量 $\boldsymbol{T}\in \mathbb{R}^n$ 定义出一个欧氏变换：$L:\mathbb{R}^n\rightarrow \mathbb{R}^n;\quad \boldsymbol{x}\mapsto\boldsymbol{Rx+T}$

  由这种变换组成的集合称为欧几里得群（欧氏群）$E(n)$ ，显然它是仿射群 $A(n)$ 的子群，基于齐次坐标，欧氏群的矩阵表示如下：

  $$E(n)=\left\{ \left( \begin{matrix} \boldsymbol{R} \quad\boldsymbol{T}\\ \boldsymbol{0} \quad\ 1 \end{matrix} \right)\Bigg| \boldsymbol{R}\in O(n),\boldsymbol{T}\in\mathbb{R}^n \right\}$$

  对应地，若 $\boldsymbol{R}\in SO(n)$ ，那么此时的欧氏群称作 特殊欧氏群 ，记作 $SE(n)$ 。特别地，$SE(3)$ 表示的是三维刚体运动。

  综上，几个群之间的关系有：

  $$\boxed{SO(n)\subset O{n}\subset GL(n),\quad SE(n)\subset E(n)\subset A(n)\subset GL(n+1)}$$

Properties of Matrices(矩阵特征)

SVD(Singular Value Decomposition)