奇异值分解求线性方程组的最小二乘解

线性方程组一般考虑两类：

非齐次线性方程组：Ax = b
齐次线性方程组：Ax = 0

A 是 m * n 矩阵，x 是 n * 1 的向量，b 是 m * 1 的向量。此类问题可以很方便地采用SVD奇异值分解来求解。

一. 讨论基于线性代数的解析解

关于线性方程组的解析解存在性的讨论在之前的博客中已经介绍，主要基于向量组的线性相关性理论。链接为：【线性代数】齐次与非齐次线性方程组有解的条件。

主要结论为：

对于齐次线性方程组 Ax = 0：

Ax = 0 有非零解的充分必要条件是 r(A) < n，即r(A)小于A的列数。
Ax = 0 只有零解的充分必要条件是 r(A) = n，即r(A)等于A的列数。

对于非齐次线性方程组 Ax = b：

Ax = b 有解的充分必要条件是 $r\{\widetilde{A}\}$ 。 $\widetilde{A}$ 是该方程组的增广矩阵 $[A, b] .$
Ax = b 有唯一解的充分必要条件是 $r\{\widetilde{A}\} = n$ .
Ax = b 有无穷多解的充分必要条件是 $r\{\widetilde{A}\} < n$ .

二. 超定方程组的最小二乘解

2.1 非齐次线性方程组的最小二乘解

重新考虑形如 Ax = b 的方程组，A 是 m * n 矩阵，则有三种可能性：

如果 m < n，那么未知数大于方程数，此时方程组没有唯一解，而是解的一个向量空间。
如果 m = n，只要 A 可逆，则方程组便有唯一解。
如果 m > n，那么方程数大于未知数，方程组一般没有解，即 $\neq r\{\widetilde{A}\}$ 。除非 b 在 A 的列空间中，即 $r\{\widetilde{A}\}$ .

满秩情况下的最小二乘解

在实际问题中，通常会遇到方程数大于未知数的情况，现在考虑 m ≥ n 并且 A 的秩为 n 的情形。如果解不存在，那么对许多情形，我们仍然希望寻找一个向量 x 使 || Ax - b || 最小，这样的 x 称为该 超定方程组的一个最小二乘解，用 SVD 奇异值分解方法可以方便地求最小二乘解。

下面直接给出结论。

给定对角方阵 $\Sigma$ ，定义它的伪逆 $\Sigma^\dagger$ 是对角矩阵，且其对角元素满足：
$\Sigma^\dagger_{ii} = 0, \qquad \mathrm{if} \; \Sigma_{ii}=0 \\ \Sigma^\dagger_{ii}= \Sigma^{-1}_{ii}，\mathrm{if} \; \Sigma_{ii}\neq0$
现在考虑 m * n 矩阵 A，其中 m ≥ n。令 A 的 SVD分解为 $U\Sigma V^T$ 。定义 A 的伪逆为矩阵

$A^{\dagger}=V\Sigma^{\dagger}U^T$

结论：秩为 n 的 $\times n$ 方程组 Ax = b 的最小二乘解由 x = A $^{\dagger}$ b 给出。

用正规方程解线性最小二乘问题

线性最小二乘问题也可以用一个涉及正规方程的方法来解。考虑线性方程组 Ax = b，其中 A 为 m * n 的矩阵并且 m > n。这个方程组一般不存在解 x。此时我们的任务是求最小化范数 || Ax - b || 的向量 x。

当 x 取遍所有的值时，Ax 将遍历 A 的整个列空间，即由 A 的列生成的一个 $R^m$ 子空间。因此我们的任务是在 A 的列空间中寻找最接近 b 的那个向量，接近程度由向量范数定义。
令 x 是这个问题的解，则 Ax 是最接近 b 的点。此时，两者的差 Ax - b 必然是与 A 的列空间垂直的向量，即 Ax - b 垂直于 A 的每一列，因此有 $A^T(A\mathbf{x} - \mathbf{b}) = 0$ ，进一步转化就得到方程：
$(A^TA)\mathbf{x} = A^T \mathbf{b}$

这是一个 $\times n$ 的线性方程组，称为 正规方程。该方程组有解并且可用来求问题 Ax = b 的最小二乘解。

即使 A 不满秩，这个方程组仍然应该有一个解，因为 $A^T\mathbf{b}$ 在 $A^TA$ 的列空间中（不过此时的解不是 Ax = b 可靠的最小二乘解）；
如果 A 的秩为 n，则矩阵 $A^TA$ 可逆，从而 x 可以通过 $\mathbf{x} = (A^TA)^{-1}A^T \mathbf{b}$ 求得。

由于 $\mathbf{x}=A^\dagger\mathbf{b}$ ，不难得到：如果 $\times n$ 矩阵 A 的秩为 n，那么 $A^\dagger=(A^TA)^{-1}A^T$ 。

该算法总结如下：

目标：求最小化 ||Ax|| 的 x.
算法：
（1）解正规方程 $(A^TA)\mathbf{x} = A^T \mathbf{b}$ .
（2）如果 $A^TA$ 可逆，则解是 $\mathbf{x} = (A^TA)^{-1}A^T \mathbf{b}$ .

对于正规方程的求解，常用的方法还有 Cholesky 分解、QR分解等，该部分内容待后续补充。

2.2 齐次线性方程组的最小二乘解

与上一问题类似的是求齐次线性方程组 Ax = 0 的解。我们仍然考虑方程数大于未知数的情形——即超定方程组。平凡解 x = 0 不是我们期望的，因此重点关注其非零解。值得注意的是，如果 x 是该方程组的一个解，那么对任何标量 k，kx也是解，因此一个合理的约束是只求 || x || = 1 的解。

假定 A 的维数是 m * n，那么根据上面第一节的讨论，存在非零解析解的充要条件是 rank(A) < n。在实际应用中，齐次线性方程组一般不存在解析解。当没有精确解时，我们通常求它的一个最小二乘解，问题描述为：

求使|| Ax ||最小化并且满足 ||x|| = 1 的 x

该问题利用奇异值分解的求解思路如下。

令 A 的奇异值分解为 $U\Sigma V^T$ ，那么问题变为最小化 $\lVert U\Sigma V^T \mathbf{x} \rVert$ ；
根据正交变换的保范性（正交变换不改变向量的范数），有 $\lVert U\Sigma V^T \mathbf{x} \rVert = \lVert \Sigma V^T \mathbf{x} \rVert$ 和 $\lVert \mathbf{x} \rVert =\lVert V^T \mathbf{x} \rVert$ ，因此我们相当于需要在条件 $\lVert V^T\mathbf{x}=1\rVert$ 下最小化 $\lVert\Sigma V^T\mathbf{x}\rVert$ ；
令 $\mathbf{y}=V^T\mathbf{x}$ ，则问题转变为在条件 $\lVert \mathbf{y}=1\rVert$ 下最小化 $\lVert\Sigma \mathbf{y}\rVert$ ；
现在已知 $\Sigma$ 是对角元素按降序排列的一个对角矩阵，由此推出该问题的解是 $\mathbf{y} = (0,0,\cdots,0,1)^T$ ，即具有一个非零元素 1 并在最后的位置上。
于是， $\mathbf{x}=V\mathbf{y}$ 就是 $V$ 的最后一列。此外， $V$ 的最后一列也可以描述为对应于 $A^TA$ 最小特征值的特征向量。

该算法总结如下：

目标：给定行数不少于列数的一个矩阵A，求最小化 ||Ax|| 且满足 ||x|| = 1 的 x.
解：x 是 V 的最后一列，其中 $\Sigma V^T$ 是 A 的奇异值分解.

计算机视觉中的尺度等价性问题

在计算机视觉相关的应用中，通常会涉及到尺度等价性问题，比如本质矩阵、基础矩阵的求解等。待求解的齐次线性方程组为 Ax = 0，其中A 是 m * n 矩阵， x 是 n * 1 的向量。

对于齐次线性方程组的解，讨论其解空间的情况：

如果 r(A) = n（约束较强）
- m = n，此时A为方阵，则该问题有且只有零解，解空间即为零空间。
- m > n，此时解析解仍只有零解，解空间为零空间。通常求最小二乘近似非零解，与上面讨论的过程一致。
如果r(A) < n（约束不够）
- 此时该齐次线性方程组有非零解，且解空间的维数为 n - r(A)，即自由度为 n - r(A)。
- 如果其解空间的维度为1，也就是说约束方程的个数为 n - 1，那么该方程组的某个解本身乘以任何标量仍然是解，其恰好满足了尺度等价性的特点！

所以，在计算机视觉的某些应用中，对于具有尺度等价性的变量 x，构建 Ax = 0 齐次线性方程组时，约束个数 ≥ n - 1 时可应用奇异值分解求最小二乘解。

比如在《视觉SLAM十四讲》第7.3.2节中求解本质矩阵时，仅考虑尺度等价性，使用8对点来估计本质矩阵 E。E矩阵有9个元素，转换成向量的形式为 9 * 1 的向量 $\mathbf{e}$ ，每对点可以提供一个约束方程，那么总共构成 8 * 9 的系数矩阵 A，问题描述为 $A\mathbf{e} = \mathbf{0}$ .

此时可以用常规的高斯消元等基本线性代数方法求其基础解系
也可以用奇异值分解的方法求解，对于矩阵 A，维度为 8 * 9，则奇异值分解为 $A=U\Sigma V^T$ ，其中前8个奇异值非0，最后一个奇异值为0，那么最后一个奇异值对应的右奇异向量（V的最后一列）即为 $\mathbf{e}$ 的一个非零最小二乘解。