作者：Frank
时间：2016-09-03

在SLAM中，无论是计算Homography Matrix，Fundamental Matrix，还是做三角化(Triangulation)时，都会用到最小二乘法。而在最小二乘法中的最常用的解法就是SVD（Singular Value Decomposition）分解。本节就讲述SVD分解的基本概念以及其在最小二乘法中的应用和证明。

1. 数学基础

1.1. 正交矩阵

正交矩阵是在欧几里得空间里的叫法，在酉空间里面叫做酉矩阵，一个正交矩阵对应的变换叫做正交变换，这个变换的特点就是不改变向量的尺寸和向量间的夹角。正交变换的示意图如下所示：

假设二维空间中的一个向量$\vec{OA}$，它在标准坐标系也即$e_1$、$e_2$表示的坐标系中的表示为$[a,b]^T$，现在把它用另一组坐标$e_1’$、$e_2’$表示为$[a’,b’]^T$，存在矩阵U使得$[a’,b’]^T=[a,b]^T$，则U即为正交矩阵。从图中可以看出，正交变换只是将变换向量用另一组正交基来表示，在这个过程中并没有对向量做拉伸，也不改变向量的空间位置，假如对两个向量同时做正交变换，那么变换前后这两个向量的夹角显然不会改变。上面的例子只是正交变换的一个方面，即旋转变换，可以把$e_1’$、$e_2’$坐标系看成是$e_1$、$e_2$坐标系经过旋转某个$\theta$角度得到的，假设：
$$x=\left[\matrix{a \cr b \cr}\right] \tag{1}$$
$$a’=x \times e_1’ =e_1’^T x\tag{2}$$
$$a’=x \times e_2’ =e_2’^T x\tag{3}$$

$a’$和$b’$实际上是x在$e_1’$和$e_2’$轴上的投影大小，所以直接对其做内积可得：
$$\left[\matrix{a’ \cr b’ \cr}\right]=\left[\matrix{e_1’^T \cr e_2^T \cr}\right]x \tag{4}$$
从图中可以看出：
$$e_1’＝\left[\matrix{cos \theta \cr sin \theta \cr}\right] \ e_2’＝\left[\matrix{-sin \theta \cr cos \theta \cr}\right] \tag{5}$$
所以可以得到正交矩阵$U$为：
$$U=\left[\matrix{cos \theta & sin \theta \cr -sin \theta & cos \theta \cr}\right]\tag{6}$$

正交矩阵$U$行（列）向量之间都是单位正交向量。上面求得的是一个旋转矩阵，它对向量做旋转变换。
旋转矩阵只是正交变换的一方面，正交矩阵的另一方面是反射变换，也即$e_1’$的方向和图中方向相反。
总结：正交矩阵的行（列）向量都是两两正交的单位向量，正交矩阵对应的变换为正交变换，在酉空间里面称为酉变换。它有两种表现：旋转和反射。正交矩阵将标准正交基映射为另一组标准正交基。

1.2. 特征值分解–EVD

在讨论SVD分解之前我们先讨论矩阵的特征值分解(EVD)，在这里，选择一种特殊的矩阵—对称阵（酉空间里面叫heimite矩阵）。对称阵的重要性质是：它总能相似对角化，对称阵不同特征值对应的特征向量两两正交。一个矩阵能相似对角化说明其特征子空间即为其列空间，若不能相似对角化则其特征子空间为列空间的子空间。现在假设存在$m \times m$ 的满秩对称矩阵A，他有m个不同的特征值，设特征值为：
$$ \lambda_i, i=1,2…..m \tag{7} $$
对应的单位特征向量为$x_i$，则有：
$$ \matrix{Ax_1=\lambda_1 x_1 \cr Ax_2=\lambda_2 x_2 \cr … \cr Ax_m=\lambda_m x_m \cr}\tag{8} $$
进而：
$$\matrix{
AU=U\Lambda \cr
U=\left[\matrix{x_1&x_2&\cdots & x_m \cr}\right] \cr
\Lambda =\left[\matrix{
\lambda_1 & \cdots & 0 \cr
\vdots & \ddots & \vdots \cr
0 & \cdots & \lambda_m \cr
}\right]
} \tag{9}$$

所以可以得到A的特征值分解（由于对称矩阵特征向量两两正交，所以U为正交阵，正交阵的逆矩阵等于其转置）
$$A=U \Lambda U^{-1} =U \Lambda U^T \tag{10}$$
这里假设A有m个不同的特征值，实际上，只要A是对称阵其均有如上分解。
矩阵A分解了，相应的，其对应的映射也分解为三个映射。现在假设有$x$向量，用A将其变换到A的列向量空间中，那么首先由$U^T$对x做变换：
$$Ax=U\Lambda U^T x \tag{10} $$
U是正交阵$U^T$也是正交阵，所以$U^T$对x的变换也是正交变换，它将x用新的坐标系来表示，这个坐标系就是A的所有正交的特征向量构成的坐标系。比如讲x用A的所有特征向量表示为：
$$ x=a_1x_1+a_2x_2+….+a_mx_m \tag{11}$$
则通过第一个变换就可以把x表示为$\left[ \matrix{a_1 &a_2&…&a_m \cr}\right]^T$
$$U\Lambda U^Tx=U \Lambda \left[\matrix{x_1^T \cr x_2^T \cr \vdots \cr x_m^T \cr} \right](a_1x_1+a_2x_2+….+a_mx_m)=U\Lambda \left[\matrix{a_1 \cr a_2 \cr \vdots \cr a_m \cr}\right] \tag{12}$$
紧接着，在新的坐标系表示下，由中间的对角矩阵对新的向量进行坐标变换，其结果就是将向量向各个轴方向拉伸或者压缩：
$$U\Lambda\left[\matrix{a_1 \cr a_2 \cr \vdots \cr a_m \cr}\right]=U\left[\matrix{\lambda_1 & \cdots & 0 \cr \vdots & \ddots & \vdots \cr}\right]\left[\matrix{a_1 \cr a_2 \cr \vdots \cr a_m \cr}\right]=U\left[ \matrix{\lambda_1a_1 \cr \lambda_2a_2 \cr \vdots \cr \lambda_ma_m \cr}\right] \tag{13} $$

从式(13)可以看出，如果A不是满秩的话，那么就是说对角矩阵的对角线元素上存在0，这时候就会导致维度退化，这样就会使映射后的向量落入m维空间的子空间中。

最后一个变换就是U对拉伸或压缩后的向量做变换，由于U和$U’$互为逆矩阵，所以U变换是$U’$变换的逆变换。
因此，从对角矩阵分解对应的映射分解来分析一个矩阵的变换特点是非常直观的。假设对称阵特征值全为1那么显然它就是单位阵，如果对称阵的特征值酉个别是0其他全为1，那么它是一个正交投影矩阵，它将m维向量投影到它的列空间中。

1.3. 奇异值分解–SVD

上面的特征值分解的A矩阵式对称阵，根据EVD可以找到一个矩形使得其变换后还是矩形，也即A可以将一组正交基映射到另一组正交基，而对于任意的$M \times N $矩阵，也能找到一组正交基使得经过它变换后还是正交基，而这就是SVD的目的所在。
现在假设存在$M \times N $矩阵A，事实上，A矩阵将n维空间中的向量映射到k(k<=m)维空间中，k=Rank(A)。现在的目标就是：在n维空间中找一组正交基，使得经过A变换后还是正交的。假设已经得到了这样一组正交基：
$${v_1,v_2,\cdots,v_n} \tag{14} $$
则A矩阵将这组正交基映射为：
$${Av_1,Av_2,\cdots,Av_n} \tag{15}$$
如果要使得他们两两正交，即：
$$Av_i \cdot Av_j =(Av_i)^TAv_j=v_i^TA^TAv_j=0 \tag{16}$$
根据假设，存在
$$v_i^Tv_j=v_iv_j=0 \tag{17}$$
所以如果正交基v选择为$A^TA$的特征向量的话，由于$A^TA$是对称阵，v之间两两正交，那么：
$$v_i^TA^TAv_j=v_i^T \lambda_jv_j=\lambda_j v_i^T v_j=\lambda_j v_i v_j=0 \tag{18} $$
这样就找到了正交基使其映射后还是正交基了。现在，将映射后的正交基单位化。
因为：$ Av_i \cdot Av_i=\lambda_i v_i v_i=\lambda_i $，所以有：$|Av_i|^2=\lambda_i \geq 0 $，所以取单位向量$u_i={Av_i \over |Av_i|}={1 \over \sqrt{\lambda_i}}Av_i $，由此可得：
$$Av_i= \sigma _i u_i ,\sigma _i(奇异值)=\sqrt{\lambda_i},0 \leq i \leq k, k=Rank(A) \tag{19} $$
当$k< i \leq m$时，对$u_1,u_2,\cdots ,u_k$进行扩展成$u_{k+1},\cdots,u_m$，使得$u_1,u_2,\cdots ,u_m$为m维空间中的一组正交基，即将${u_1,u_2,\cdots ,u_k}$正交基扩展成${u_1,u_2,\cdots ,u_m}R^m$空间的单位正交基。同样的，对$v_1,v_2,\cdots ,v_k$进行扩展$v_{k+1},\cdots,v_n$(这n-k个向量存在于A的零空间中，即Ax=0的解空间的基)，使得$v_1,v_2,\cdots ,v_n$为n维空间中的一组正交基，即：在A的零空间中选取$v_{k+1},\cdots,v_n$使得$Av_i=0,i >k$，并取$\sigma _i=0$。则可以得到：
$$A=U \sum V^T \tag{20} $$
V是$n \times n $的正交阵，U是$m \times m $的正交阵，$\sum$是$m \times n$的对角阵。

2. 最小二乘中的SVD分解

为了求$Ax-b=0$的最优解，需要求取：$min||Ax-b||$，对A做SVD分解，有：
$$min||Ax-b||=min||UDV^Tx-b|| \tag{21}$$
将目标函数左乘$U^T$，鉴于$U^T$的正定性，有：
$$min||UDV^T-b||=min||DV^Tx-U^Tb|| \tag{22}$$
令$y=V^Tx,b’=U^Tb$，则有：
$$min||Dy-b’||=min||\left[\matrix{d_1&0&\cdots&0 \cr 0&d_2&\cdots&0 \cr \ddots \cr 0& \cdots & d_n \cr 0 \cr}\right]\left[\matrix{y_1 \cr y_2 \cr \vdots \cr y_n \cr}\right]-\left[\matrix{b_1^{‘} \cr b_1^{‘} \cr \vdots \cr b_n^{‘} \cr b_{n+1}^{‘} \cr \vdots \cr b_m^{‘} \cr}\right]|| \tag{23} $$
当$b_{n+1}^{‘} \cdots b_m^{‘}$均为0时得到最小值：
$$y_i={b_i^{‘} \over d_i} (i=1,2,\cdots ,n) \tag{24}$$

引用来源：1http://www.ams.org/samplings/feature-column/fcarc-svd;
2http://filer.blogbus.com/11139779/resource_11139779_13341356544.pdf;

转载请注明出处