前言

之前将最小二乘法与线性方程组求解关联，得到了线性最小二乘的矩阵形式，以及线性最小二乘的几何意义。

本篇将介绍线性最小二乘的矩阵解法。

回顾最小二乘的线性解

对于线性超定方程组$Ax=b,A\in R^{m\times n},m>n$，其最小二乘解可表示为：
$$\begin{gathered} \underset{x}{\mathrm{argmin}}||Ax-b|{|}_2^2=\underset{x}{\mathrm{argmin}}(Ax-b{)}^T(Ax-b) \\ \to A^{T}Ax=A^{T}b \\ ifrank(A)=n,x=(A^{T}A{)}^{-1}{A}^{T}b \end{gathered}$$

以上解法具有两个问题：①$A^{T}A$求逆运算的效率；②$rank(A)<n$时的最小二乘解。

首先讨论问题①。

列满秩矩阵的最小二乘解法

对于线性方程组$Ax=b,A\in R^{m\times n},m>n,rank(A)=n$，有$A^{T}A$对称且可逆。回顾矩阵分解的知识，可知$A^{T}A$矩阵能够进行Cholesky分解和QR分解。

Cholesky分解求线性最小二乘解

通过将$A^{T}A$分解为下三角矩阵$L$的乘积$L{L}^T$：
$$A^{T}A=L{L}^T$$
则可以将复杂的线性方程组求解：
$$A^{T}Ax=A^{T}b$$
转化为两个简单的三角线性方程组求解：
$$L{L}^{T}x=A^{T}b\to L^{T}x=y,Ly=A^{T}b$$

Cholesky分解速度很快，但精度一般，稳定性差。适合在限定时间内的大规模超定线性方程计算求解。

QR分解求线性最小二乘解

对于列满秩矩阵$A$而言，可以唯一分解为正交矩阵与对角元为正的上三角矩阵的乘积：
$$A=QR=Q\left[\begin{array}{c}R\\ 0\end{array}\right]$$
现在考虑最小二乘法的QR分解法：
$$\begin{gathered} \underset{x}{\mathrm{argmin}}||Ax-b|{|}_2^2=\underset{x}{\mathrm{argmin}}||Q\left[\begin{array}{c}R\\ 0\end{array}\right]x-b|| \\ =\underset{x}{\mathrm{argmin}}||\left[\begin{array}{c}R\\ 0\end{array}\right]x-Q^{T}b|{|}_2^2 \\ =\underset{x}{\mathrm{argmin}}||\left[\begin{array}{c}Rx\\ 0\end{array}\right]-\left[\begin{array}{c}{\beta }_1\\ {\beta }_2\end{array}\right]|{|}_2^2 \\ =\underset{x}{\mathrm{argmin}}||Rx-{\beta }_1|{|}_2^2+||{\beta }_2|{|}_2^2 \\ ⟺\underset{x}{\mathrm{argmin}}||Rx-{\beta }_1|{|}_2^2 \\ \to Rx={\beta }_1,x=R^{-1}{\beta }_1 \\ \left[\begin{array}{c}{\beta }_1\\ {\beta }_2\end{array}\right]=Q^{T}b \end{gathered}$$

QR分解的速度较快，精度一般。不过由于存在高精度的QR分解方式，因此适合需要高精度解的小规模超定方程组计算。

亏秩矩阵的最小二乘解法

对于线性方程组$Ax=b,A\in R^{m\times n},m>n,rank(A)<n$，称为亏秩超定方程组。此时$A^{T}A$不是正定矩阵，QR分解也不是唯一的。通常使用SVD来解决亏秩问题。

SVD分解求亏秩最小二乘解

对于矩阵$A_{m\times n},m>n,rank(A)=r<n$，可分解为正交矩阵与奇异值矩阵的乘积：
$$\begin{gathered} A=U_{m\times m}\left[\begin{array}{cc}{\Sigma }_{r\times r}& 0_{r\times (n-r)}\\ 0_{(m-r)\times r}& 0_{(m-r)\times (n-r)}\end{array}\right]V_{n\times n}^T \\ {U}^{T}U=E,V^{T}V=E \end{gathered}$$
现在考虑最小二乘法的SVD解法：
$$\begin{gathered} \underset{x}{\mathrm{argmin}}||Ax-b|{|}_2^2=\underset{x}{\mathrm{argmin}}||U^{T}Ax-U^{T}b|{|}_2^2 \\ =\underset{x}{\mathrm{argmin}}||U^{T}U\left[\begin{array}{cc}\Sigma & 0\\ 0& 0\end{array}\right]V^{T}x-U^{T}b|{|}_2^2 \\ =\underset{x}{\mathrm{argmin}}||\left[\begin{array}{cc}\Sigma & 0\\ 0& 0\end{array}\right]V^{T}x-U^{T}b|{|}_2^2 \\ =\underset{x}{\mathrm{argmin}}||\left[\begin{array}{cc}\Sigma & 0\\ 0& 0\end{array}\right]\left[\begin{array}{c}{\alpha }_1\\ {\alpha }_2\end{array}\right]-\left[\begin{array}{c}{\beta }_1\\ {\beta }_2\end{array}\right]|{|}_2^2 \\ =\underset{x}{\mathrm{argmin}}||\left[\begin{array}{c}\Sigma {\alpha }_1\\ 0\end{array}\right]-\left[\begin{array}{c}{\beta }_1\\ {\beta }_2\end{array}\right]|{|}_2^2 \\ =\underset{x}{\mathrm{argmin}}||\Sigma {\alpha }_1-{\beta }_1|{|}_2^2+||{\beta }_2|{|}_2^2 \\ \to \Sigma {\alpha }_1={\beta }_1 \\ \left[\begin{array}{c}{\alpha }_1\\ {\alpha }_2\end{array}\right]=V^{T}x,\left[\begin{array}{c}{\beta }_1\\ {\beta }_2\end{array}\right]=U^{T}b \\ {\alpha }_1={\Sigma }^{-1}{\beta }_1,x=V\left[\begin{array}{c}{\alpha }_1\\ {\alpha }_2\end{array}\right] \end{gathered}$$
在上面的解法中，由于${\alpha }_2$是一个任意向量，因此求出的$x$不是唯一的。即亏秩方程的最小二乘解不唯一。可以选择范数最小的最小二乘解作为亏秩方程的解，即${\alpha }_2=\vec{0}$。

可以通过正交矩阵分块，将SVD最小二乘解进一步化简：
$$\begin{gathered} U=[U_1,U_2],V=[V_1,V_2] \\ {U}_1\in R^{m\times r},V_1\in R^{n\times r} \\ {\alpha }_1={\Sigma }^{-1}{\beta }_1 \\ \left[\begin{array}{c}{\alpha }_1\\ {\alpha }_2\end{array}\right]=\left[\begin{array}{c}{V}_1^T\\ V_2^T\end{array}\right]x \\ \left[\begin{array}{c}{\beta }_1\\ {\beta }_2\end{array}\right]=\left[\begin{array}{c}{U}_1^T\\ U_2^T\end{array}\right]b \\ {V}_1^{T}x={\Sigma }^{-1}{U}_1^{T}b \\ x=V_1{\Sigma }^{-1}{U}_1^{T}b \end{gathered}$$

需要说明的是，SVD也适用于列满秩矩阵的最小二乘求解。实际上SVD分解是最常用的线性最小二乘解法之一。

补充1：超定齐次方程组的线性最小二乘解法

之前的最小二乘法都在考虑$Ax=b$的最小非齐次方程组问题。现在补充齐次方程组的最小二乘解法。

对于齐次方程组$A_{m\times n}x=0,m>n$而言，其最小二乘解就是$A$的SVD分解后的$V$的最后一个列向量。

证明：
$$\begin{gathered} A=U\left[\begin{array}{c}\Sigma \\ 0\end{array}\right]V^T \\ Ax=U\left[\begin{array}{c}\Sigma \\ 0\end{array}\right]V^{T}x=0 \\ y=V^{T}x,\Sigma y=0 \\ 也就是说，求Ax=0，转换为求\Sigma y=0的最小二乘解 \\ \underset{y}{\mathrm{argmin}}||\Sigma y|{|}_2^2 \\ =\underset{y}{\mathrm{argmin}}{y}^T{\Sigma }^T\Sigma y \\ =\underset{y}{\mathrm{argmin}}\sum _{i=1}^n{\sigma }_i^2{y}_i^2 \\ s.t.||y||>0 \\ \Sigma 对角线元素由大到小排列，则满足 \\ y=[0,0,\dots ,0,y_n{]}^T,y_n\ne 0 \\ 时，获得\Sigma y的最小二乘解 \\ {V}^{T}x=y,x=Vy=y_n{v}_n \\ if||y|{|}_2=1 \\ thenx=v_n \end{gathered}$$
进一步，超定齐次线性方程组$Ax=0$的最小二乘解还等于$A^{T}A$的最小特征值对应的特征向量：

证明：
$$\begin{gathered} A=U\left[\begin{array}{c}\Sigma \\ 0\end{array}\right]V^T \\ {A}^{T}A=V\left[\begin{array}{cc}\Sigma & 0\end{array}\right]\left[\begin{array}{c}\Sigma \\ 0\end{array}\right]V^T=V{\Sigma }^2{V}^T \\ {A}^{T}Ax=V{\Sigma }^2{V}^{T}x=0 \\ y=V^{T}x,\Lambda ={\Sigma }^2,\Lambda y=0 \end{gathered}$$
后面的证明就与上面一模一样了。

补充2：欠定行满秩方程组的线性最小二乘解法

还需要补充的是欠定方程组的最小二乘解法。虽然用的少，但却实实在在的碰到了这个问题：对极几何中本质矩阵的求解。

首先需要确定，线性齐次欠定方程组必然存在无穷组解析解。

对于非齐次欠定方程组$A_{m\times n}x=b,m<n,rank(A)=r$，其最小二乘也是通过SVD求解：
$$\begin{gathered} A=[U_1^{m\times r},U_2^{m\times (m-r)}]\left[\begin{array}{cc}{\Sigma }^{r\times r}& 0\\ 0& 0^{(m-r)\times (n-r)}\end{array}\right][V_1^{n\times r},V_2^{n\times (n-r)}{]}^T \\ Ax=U_1\Sigma V_1^{T}x=b \\ y=V_1^{T}x,U_1\Sigma y=b \\ 特别的，如果rank(A)=m，有 \\ U\Sigma y=b,y={\Sigma }^{-1}{U}^{T}b,x=V{\Sigma }^{-1}{U}^{T}b \end{gathered}$$

后记

本篇介绍了最小二乘的矩阵解法，包括列满秩超定方程组的Cholesky分解法和QR分解法，以及亏秩超定方程组的SVD解法。

后续将继续学习非线性方程组的最小二乘问题。