本人讲解关于slam一系列文章汇总链接:史上最全slam从零开始 有兴趣的朋友可以加微信 17575010159 相互讨论技术 - 文末公众号也可关注
一、前言
在讲解超定方程求解之前，以及为什么最小奇异值对应的特征特征向量为最优解之前，我们需要知道以下知识：矩阵的特征向量，特征值，EVD(特征分解)，SVD(奇异值分解)等相关知识。这些内容本人在上一篇博客中，有特别详细的讲解，链接如下：史上最简SLAM零基础解读(3) - 白话来说SVD奇异值分解(1)→原理推导与奇异值求解举例。请认真仔细的阅读这篇博客，阅读以及弄明白之后，就可以思考接下来的问题了。
二、适定、欠定、超定方程
在工程上，很多问题最终都会转换成 A ( m , n ) x ⃗ ( n , 1 ) = b ⃗ ( m , 1 ) A_{(m,n)}\vec x_{(n,1)}=\vec b_{(m,1)} A(m,n)x (n,1)=b (m,1) 方程的求解。其中 A ( m , n ) A_{(m,n)} A(m,n) 表示 m × n m\times n m×n 的矩阵； x ( n , 1 ) x_{(n,1)} x(n,1) 表示 n n n 个元素的列向量； b ( m , 1 ) b_{(m,1)} b(m,1) 表示 m m m 个元素的列向量。当然 x ( n , 1 ) x_{(n,1)} x(n,1) 与 b ( m , 1 ) b_{(m,1)} b(m,1) 也可当作矩阵来看待。 A ( m , n ) x ⃗ ( n , 1 ) = b ⃗ ( m , 1 ) (1) \tag{1} \color{blue} A_{(m,n)}\vec x_{(n,1)}=\vec b_{(m,1)} A(m,n)x (n,1)=b (m,1)(1)
若方程(1)至少有一个精确解，称为一致方程。
若方程(1)无任何精确解，称为非一致方程。
根据矩阵 A ( m , n ) A_{(m,n)} A(m,n) 秩的大小，矩阵方程又可以分成以下三种类型：
( 1 ) 适定方程 → \color{blue} (1)适定方程→ (1)适定方程→: 若 m = n m=n m=n , 并且 r a n k ( A ) = n {rank}(A)=n rank(A)=n , 即矩阵 A A A 非奇异, 则称矩阵方程 A x ⃗ = b ⃗ {A} {\vec x}={\vec b} Ax =b 为适定 (well-determined) 方程。
( 2 ) 欠定方程 → \color{blue} (2)欠定 方程→ (2)欠定方程→: 若独立的方程个数小于独立的末知参数个数, 则称矩阵方程 A x ⃗ = b ⃗ {A \vec x}={\vec b} Ax =b 为欠定 (under-determined) 方程。
( 3 ) 超定方程 → \color{blue} (3)超定方程→ (3)超定方程→: 若独立的方程个数大于独立的末知参数个数, 则称矩阵方程 A x ⃗ = b ⃗ {A \vec x}={\vec b} Ax =b 为超定 (over-determined) 方程。
下面是术语 “适定”、“欠定” 和 “超定” 的含义。 适定的双层含义 方程组的解是唯一的; 独立的方程个数与独立末知参数的个数相 同, 正好可以唯一地确定该方程组的解。适定方程 A x ⃗ = b ⃗ {A \vec x}={\vec b} Ax =b 的唯一解由 x ⃗ = A − 1 b ⃗ {\vec x}={A}^{-1} {\vec b} x =A−1b 给出。 适定方程为一致方程。
欠定的含义 独立的方程个数比独立的末知参数的个数少, 意味着方程个数不足于确定方程组的唯一解。事实上, 这样的方程组存在无穷多组解 x ⃗ {\vec x} x 。欠定方程为一致方程。
超定的含义 独立的方程个数超过独立的末知参数的个数, 对于确定方程组的唯一 解显得方程过剩。因此, 超定方程 A x ⃗ = b ⃗ {A \vec x}={\vec b} Ax =b 没有使得方程组严格满足的精确解 x ⃗ {\vec x} x 。超定方程为非一致方程。
三、超定方程求解
在计算机视觉或者说 slam 中，经常遇到超定方程求解的情形。比如三角化地图点，pnp，以及 Fundamental 与 Homography 矩阵的求解。那么我们就来介绍一下 超定方程 的求解。通过前面的介绍，我们已经知道超定方程没有精确解的，那么只能去求他的最优解。这个时候我们就需要引入最小二乘法了(关于最小二乘法的相关知识大家可以百度一下)。 A ( m , n ) x ⃗ ( n , 1 ) = b ⃗ ( m , 1 ) (1) \tag{1} \color{blue} A_{(m,n)}\vec x_{(n,1)}=\vec b_{(m,1)} A(m,n)x (n,1)=b (m,1)(1)这里我们先讨论一种情况，即 b ⃗ ( m , 1 ) = 0 \vec b_{(m,1)}=0 b (m,1)=0, 也就是求解如下超定方程(m>n,也就是行大于列)： A ( m , n ) x ⃗ ( n , 1 ) = 0 (2) \tag{2} \color{blue} A_{(m,n)}\vec x_{(n,1)}=0 A(m,n)x (n,1)=0(2) 很显然，上述公式中存在一个0解，但是我们工程实际应用中都是需要求非零解，为了求非零解，我们对 A A A 加上一个约束 ∣ ∣ x ⃗ ∣ ∣ 2 = 1 ||\vec x||^2=1 ∣∣x ∣∣2=1。也就是限制 x ⃗ \vec x x 的长度为1，并构建成一个带约束的最小二乘问题： x ^ = arg min ∥ A x ⃗ ∥ 2 , subject to ∥ x ⃗ ∥ 2 = 1 (3) \tag{3} \color{blue} \hat{{x}}=\arg \min \|{A} {\vec x}\|^{2}, \text { subject to }\|{\vec x}\|^{2}=1 x^=argmin∥Ax ∥2, subject to ∥x ∥2=1(3) 这是一个带约束的最小二乘问题，我们把拉格朗日搬出来： L ( x ⃗ , λ ) = ∥ A x ⃗ ∥ 2 + λ ( 1 − ∥ x ⃗ ∥ 2 ) = x ⃗ T A T A x ⃗ + λ ( 1 − x ⃗ T x ⃗ ) (4) \tag{4} \color{blue} \begin{aligned} L({\vec x}, \lambda) &=\|{A} {\vec x}\|^{2}+\lambda\left(1-\|{\vec x}\|^{2}\right) \\ &={\vec x}^{T} {A}^{T} {A} {\vec x}+\lambda\left(1-{\vec x}^{T} {\vec x}\right) \end{aligned} L(x ,λ)=∥Ax ∥2+λ(1−∥x ∥2)=x TATAx +λ(1−x Tx )(4)为了求极值，我们分别对 A A A 和 λ {\lambda} λ 求偏导数，令为0: ∂ L ( x ⃗ , λ ) ∂ x ⃗ = 2 A T A x ⃗ − 2 λ x ⃗ = 0 (5) \tag{5} \color{blue} \frac{\partial L({\vec x}, \lambda)}{\partial {\vec x}}=2 {A}^{T} {A} {\vec x}-2 \lambda {\vec x}=0 ∂x ∂L(x ,λ)=2ATAx −2λx =0(5) ∂ L ( x ⃗ , λ ) ∂ λ = 1 − x ⃗ T x ⃗ = 0 (6) \tag{6} \color{blue} \frac{\partial L({\vec x}, \lambda)}{\partial \lambda}=1-{\vec x}^{T} {\vec x}=0 ∂λ∂L(x ,λ)=1−x Tx =0(6)把(5)式整理一下： ( A T A − λ I ) x ⃗ = 0 (7) \tag{7} \color{blue} \left({A}^{T} {A}-\lambda {I}\right) {\vec x}=0 (ATA−λI)x =0(7) A T A x ⃗ = λ x ⃗ (8) \tag{8} \color{blue} {A}^{T} {A} {\vec x}=\lambda {\vec x} ATAx =λx (8)看到其上的公式(8), 根据上一篇博客我们讲解的内容，可以看出 λ {\lambda} λ 和 x ⃗ \vec x x 分别是 A T A A^T A ATA 的特征值和特征向量。也就是说超定方程 A ( m , n ) x ⃗ ( n , 1 ) = 0 A_{(m,n)}\vec x_{(n,1)}=0 A(m,n)x (n,1)=0 的解就是 A T A {A}^{T} {A} ATA 对应的特征向量，那么问题来了。这么多个特征向量，我们应该选择那一个呢?我们展开 ∥ A x ∥ 2 ∥Ax∥^2 ∥Ax∥2 看一下(利用(3)式中的 ∥ x ∥ 2 = 1 ∥x∥^2=1 ∥x∥2=1)： ∥ A x ⃗ ∥ 2 = x ⃗ T A T A x ⃗ = x ⃗ T λ x ⃗ = λ x T x ⃗ = λ (9) \tag{9} \color{blue} \|{A} {\vec x}\|^{2}={\vec x}^{T} {A}^{T} {A} {\vec x}={\vec x}^{T} \lambda {\vec x}=\lambda {x}^{T} {\vec x}=\lambda ∥Ax ∥2=x TATAx =x Tλx =λxTx =λ(9) 也就是说，我们想要 ∥ A x ∥ 2 ∥Ax∥^2 ∥Ax∥2 最小，就需要 λ λ λ 最小。对于 SVD 奇异值分解公式如下(上一篇博客有推导) A m × n = U m × m Σ m × n V n × n T A_{m\times n}=U_{m\times m}\Sigma_{m\times n}V^T_{n \times n} Am×n=Um×mΣm×nVn×nT其上的 Σ m × n \Sigma_{m\times n} Σm×n是对角矩阵，对角线元素称为奇异值，一般来说奇异值是按照从大到小的顺序降序排列。因为每一个奇异值都是一个残差项，因此最后一个奇异值最小，其含义是最优的残差。因此其对用的奇异值向量就是最优解。
四、结语通过上一篇博客，与这一篇博客的讲解，我相信大家对于 SVD奇异值分解 的原理，以及推导过程应该算是比较了解呢，但是与工程上的应用还是需要多磨合一下。毕竟理论没有实践，也仅仅是纸上谈兵。没有运用到现实生活的数学公式，还是比较空洞的。
