SVD求Ax=0的非零解
最近解Homography的问题，看到这个解法，甚是科学。
通常情况下，一个线性方程组Ax = b，如果A不可逆，可以在等式两边乘上，变成，可以证明ATA一定可逆，其逆称为伪逆。把伪逆乘到右边就可以了。
| 但是如果是齐次方程组Ax = 0，求非零解，这招就不灵了。因为右边乘上AT还是零，再乘上伪逆还是零。本来，Ax=0的伪逆解法求的就是近似解，Ax=0无解，委屈求$$A^TAx = A$Tb$。看起来像是作弊，其实是最小化 | Ax – b | 的结果。等同于把向量b投影到A的列空间。用这个投影代替b，这样才有了解。但是Ax = 0，怎么可能无解，明明就存在一个解就是0，而且是毫无瑕疵的精确解（虽然往往没什么用）。所以这个方法就不好使了。 |
| 首先要解这个方程必须加上一些约束，否则0向量是必然的解。如果说0不要，那么越是接近0，就是一个越近似的解，那也没有意义。其实我们要求的是一个方向，使得经过A变换后模长“相对”最小。相对就是相对原来的模长来说。因为线性变换嘛，x缩放多少倍，Ax还缩放多少倍。因此可以约定 | x | =1，求一个单位向量。最小化Ax。 |
SVD的方法是把A分解成，UV是正交矩阵，W是一个对角矩阵。正交的意义在于模长不变，仅仅转了一个方向。想想对角化是做一件什么事情，对角化之后得到的特征向量，在线性变换之后方向不变而只有长度的变化。而任何一个向量可以放到特征向量组成的那个坐标系，然后每个分量在线性变换下就只有长度的变化，因此在这个坐标系下可以表示成一个对角阵。SVD差不多是对角化的推广，只不过现在不要求变换后的空间（值域）和原来的空间（定义域）使用同样的坐标系。现在，定义域用V坐标系，而值域使用U坐标系，则线性变换可以表示成对角矩阵。
齐次方程组里面右边的0，无论在哪个坐标系也还是0。太好了！因此把x放到V坐标系中，经过A变换，再放到U坐标系中看的话，数值上就只有每个分量缩放了一个奇异值的大小。并且，由于UV是正交的，整个过程除了A变换，是不改变模长的。原来模长是1，之后模长变了，完完全全是A在作怪。这也是为什么UV除了列向量正交还要求转置自乘为单位阵，也就是把各个维度归一化了。
| 现在要最小化 | Ax | ，UV两个坐标系，放到哪个下面看其实都一样。所以就不用变回去了，就在V下看吧，奇异值绝对值最小的那个方向就是咯。想象一下把x投影到V的各个列向量也就是坐标轴，得到n个互相垂直的小箭头。然后在A变换的作用下，每个小箭头伸缩了一下（有的还可能反向哦），伸缩的比例就是对应的奇异值。为了变换之后最短，当然取abs奇异值最小的那个方向了。还不清楚的话，想象一个椭球吧。原来x模长为1，所有可能的x集合组成一个球面。变换后每个方向按比例缩放，球就变成了椭球。这个椭球也是所有可能的Ax所组成的集合，模最小的在什么地方，短轴吧，也就是缩得最小的那个坐标轴方向。 |
如果有奇异值为0，那个方向施加A之后就成0了，那就是一个精确解。对应椭球就是被压扁了一个维度…
线性变换是不依赖矩阵而存在的，矩阵只是“皮相”，在一定坐标系下才有意义。前面的讨论都针对抽象的“向量”和“变换”，应该把向量想象成一个箭头，变换想象成这个箭头的一次运动，而不是一串不知所云的数字。但是最后要结束了，还是要接地气，毕竟要求的是一串数字。现在知道解是V坐标系下的一个坐标轴的方向，对应奇异值最小的那只，大小么，模为一。那他的坐标是什么呢？如果放在V坐标系下看，其中一个坐标轴，也就是一个基，也就是其中一个列向量，坐标为(0,0,…,1,…,0)，对应位置一个1，其他全0。放在原坐标下看呢，就是V的这个列本身了。原坐标也就是单位阵E对应的坐标。两个坐标系下同一个向量有不同的坐标，之间的转换就是一个V。原坐标下V的一列，变到V坐标，要乘上V的逆，是不是就变成了这个(0,0,…,1,…,0)？因为V是正交的，其逆也就是，然后每行和这个列作内积，其它行都和它正交，唯独它自己和自己内积为1。
所以最后的结果就是V中对应abs奇异值最小的那一列。
blog comments powered by Disqus