Logo

最小二乘问题

1. 最小二乘问题概述

在实际应用中，由于数据不完整或噪声等原因，我们经常会遇到一些不相容的方程组。这种情况下，虽然没有精确解，但我们仍然需要找到一个近似解，使得方程的左右两边差距尽可能小。为了解决这个问题，我们引入最小二乘法 (least squares solution) ~(\textbf{least squares solution})~，它通过最小化误差的平方和来找到最优的近似解。

开通会员解锁全部动画

在几何上，最小二乘问题的解可以通过正交投影来理解。向量 b ~\mathbf{b}~和 Col A ~\text{Col}\,\mathbf{A}~之间的距离是通过投影来最小化的。

2. 一般最小二乘问题的解

接下来，我们将讨论如何求解最小二乘问题，并分析其解所满足的数学特性。这些特性不仅揭示了最小二乘解的几何意义，还确保了它在误差最小化方面的最优性。

开通会员解锁全部动画

2.1 正交投影与最优逼近

在求解最小二乘问题时，我们应用最佳逼近定理。设 A ~\mathbf{A}~是 m×n ~m\times n~矩阵， b ~\mathbf{b}~是 Rm ~\mathbb{R^m}~中的一个向量。我们希望找到一个 x∈Rn ~\mathbf{x} \in \mathbb{R}^n~，使得Ax\mathbf{A}\mathbf{x}与 b ~\mathbf{b}~之间的误差 ∥Ax−b∥ ~\|\mathbf{A}\mathbf{x} - \mathbf{b}\|~最小。 根据正交投影的性质，我们可以找到 b ~\mathbf{b}~在列空间 Col A ~\text{Col}\,A~上的正交投影：
b^=projColAb\mathbf{\hat{b}} = \text{proj}_{\text{Col}A} \mathbf{b}
由于 b^ ~\hat{\mathbf{b}}~是 ColA ~\text{Col}\mathbf{A}~上离 b ~\mathbf{b}~最近的向量，最小二乘解满足：
Ax^=b^\mathbf{A} \hat{\mathbf{x}} = \hat{\mathbf{b}}
这保证了 Ax^ ~\mathbf{A}\hat{\mathbf{x}}~在 ColA ~\text{Col}\mathbf{A}~内，并且是最接近 b ~\mathbf{b}~的向量。

2.2 误差向量的正交性质

误差向量 b−Ax^ ~\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}~与 ColA ~\text{Col}\mathbf{A}~正交，，这意味着它与 A ~\mathbf{A}~的每一列都正交。设 aj ~\mathbf{a}_j~是 A ~\mathbf{A}~的任意列，那么 aj⋅(b−Ax^)=0~\mathbf{a}_j\cdot (\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}) = 0，根据点积的矩阵乘法的形式还可以写为 ajT(b−Ax^)=0 ~\mathbf{a}_j^T(\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}) = 0 ~，用矩阵形式表示：
[a1Ta2T⋮anT](b−Ax^)=AT(b−Ax^)=0(2)\begin{bmatrix}\mathbf{a}_1^T \\[1ex] \mathbf{a}_2^T \\[1ex] \vdots \\[1ex] \mathbf{a}_n^T \end{bmatrix}(\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}) = \mathbf{A}^T(\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}) = \mathbf{0}\tag{2}
对 (2) ~(2)~展开：
ATb−ATAx^=0\mathbf{A}^T \mathbf{b} - \mathbf{A}^T \mathbf{A} \hat{\mathbf{x}} = \mathbf{0}
整理得：
ATAx^=ATb(3)\colorbox{#F0F8FF}{$\mathbf{A}^T \mathbf{A} \hat{\mathbf{x}} = \mathbf{A}^T \mathbf{b}$}\tag{3}
这就是法方程(Normal Equations)(\textbf{Normal Equations})或正规方程，其解即为最小二乘解。

2.3 最小二乘解与法方程的关系

下面的定理说明法方程的解集就是最小二乘解集：

假设 x^ ~\hat{\mathbf{x}}~是Ax=b\mathbf{A}\mathbf{x} = \mathbf{b} 的最小二乘解， 即它使得误差r=b−Ax^\mathbf{r} = \mathbf{b} - \mathbf{A}\hat{\mathbf{x}}的范数最小：
x^=argmin⁡x∈Rn∥Ax−b∥\hat{x} = \text{arg} \min_{\mathbf{x} \in \mathbb{R}^n} \|\mathbf{A}\mathbf{x} - \mathbf{b}\|
根据最佳逼近定理，最优解 Ax^ ~\mathbf{A}\hat{\mathbf{x}}~必须是 b ~\mathbf{b}~在 ColA ~\text{Col}\mathbf{A}~上的正交投影：
Ax^=b^A\hat{x} = \mathbf{\hat{b}}
其中 b^ ~\hat{\mathbf{b}}~是 b ~\mathbf{b}~在 A ~\mathbf{A}~的列空间上的正交投影。 由于投影误差向量 r=b−b^ ~\mathbf{r} = \mathbf{b} - \mathbf{\hat{b}}~必须与 ColA ~\text{Col}\mathbf{A}~正交，因此对于 A ~\mathbf{A}~的每一列 aj ~\mathbf{a}_j~，都有：
ajT(b−Ax^)=0\mathbf{a}_j^T (\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}) = 0
以矩阵形式写出：
AT(b−Ax^)=0\mathbf{A}^T (\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}) = \mathbf{0}
展开整理可得：
ATAx^=ATb\mathbf{A}^T \mathbf{A} \hat{\mathbf{x}} = \mathbf{A}^T \mathbf{b}
因此，每一个最小二乘解都满足法方程。

现在，假设x^\hat{\mathbf{x}}是法方程的解，即：
ATAx^=ATb\mathbf{A}^T \mathbf{A} \hat{\mathbf{x}} = \mathbf{A}^T \mathbf{b}
对误差向量 r=b−Ax^\mathbf{r} = \mathbf{b} - A\hat{x}进行分析：
ATr=AT(b−Ax^)=ATb−ATAx^=0\mathbf{A}^T \mathbf{r} = \mathbf{A}^T (\mathbf{b} -\mathbf{A}\hat{\mathbf{x}}) = \mathbf{A}^T \mathbf{b} - \mathbf{A}^T A\hat{\mathbf{x}} = 0
这说明 r ~\mathbf{r}~与 A ~\mathbf{A}~的列空间正交，即 r ~\mathbf{r}~是 b ~\mathbf{b}~在 ColA ~\text{Col}\mathbf{A}~的正交补空间上的分量。因此，Ax^\mathbf{A}\hat{\mathbf{x}}是 b ~\mathbf{b}~在ColA\text{Col}\mathbf{A}上的正交投影：
Ax^=b^\mathbf{A}\hat{\mathbf{x}} = \hat{\mathbf{b}}
由正交投影的唯一性，x^\hat{\mathbf{x}}是最小二乘解。

3. 最小二乘法求解

法方程 ATAx^=ATb ~\mathbf{A}^T \mathbf{A} \hat{\mathbf{x}} = \mathbf{A}^T \mathbf{b}~是一个 n×n ~n\times n~的线性方程组，如果 ATA ~\mathbf{A}^T\mathbf{A}~可逆（即列向量线性无关），我们可以直接求解：
x=(ATA)−1ATb(4)\colorbox{#F0F8FF}{$\mathbf{x} = (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T \mathbf{b}$}\tag{4}
如果 ATA ~\mathbf{A}^T\mathbf{A}~不可逆，则最小二乘解不唯一。这个结论可由下面定理给出：

下面通过两个示例来说明这两种情况。

3.1 存在唯一解的情况

求下面这个不相容的方程组 Ax=b ~\mathbf{A}\mathbf{x} = \mathbf{b}~的最小二乘解，其中：
A=[400211],b=[2011]\mathbf{A} = \begin{bmatrix} 4 & 0 \\ 0 & 2 \\ 1 & 1 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 2 \\ 0 \\ 11 \end{bmatrix}
计算：
ATA=[17115],ATb=[1911]\mathbf{A}^T \mathbf{A} = \begin{bmatrix} 17 & 1 \\ 1 & 5 \end{bmatrix}, \quad \mathbf{A}^T \mathbf{b} = \begin{bmatrix} 19 \\ 11 \end{bmatrix}
由于 det⁡(ATA)≠0 ~\det(\mathbf{A}^T\mathbf{A}) \neq 0~，解得：
x^=(ATA)−1ATb=[12]\hat{\mathbf{x}} = (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T \mathbf{b} = \begin{bmatrix} 1 \\ 2 \end{bmatrix}
即 x^=[12]T ~\hat{\mathbf{x}} = \begin{bmatrix} 1 & 2 \end{bmatrix}^T~是最小二乘的唯一解，它使得 Ax^ ~\mathbf{A}\hat{\mathbf{x}}~最接近 b ~\mathbf{b}~。

3.2 最小二乘解不唯一的情况

求下面这个不相容的方程组 Ax=b ~\mathbf{A}\mathbf{x} = \mathbf{b}~的最小二乘解，其中
A=[110011001010101010011001],b=[−3−10251]\mathbf{A} = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} -3 \\ -1 \\ 0 \\ 2 \\ 5 \\ 1 \end{bmatrix}
计算
ATA=[6222220020202002],ATb=[4−426]\mathbf{A}^T\mathbf{A} = \begin{bmatrix} 6 & 2 & 2 & 2 \\ 2 & 2 & 0 & 0 \\ 2 & 0 & 2 & 0 \\ 2 & 0 & 0 & 2 \end{bmatrix},\quad \mathbf{A}^T\mathbf{b} = \begin{bmatrix} 4 \\ -4 \\ 2 \\ 6 \end{bmatrix}
由于 det⁡(ATA)=0 ~\det(\mathbf{A}^T\mathbf{A}) = 0~，ATA \mathbf{A}^T\mathbf{A}~不可逆。我们需要通过矩阵方程 ATA=ATb ~\mathbf{A}^T\mathbf{A} = \mathbf{A}^T\mathbf{b}~的增广矩阵来求解，增广矩阵为：
[622242200−42020220026]∼[10013010−1−5001−1−200000]\left[\begin{array}{cccc|c} 6 & 2 & 2 & 2 & 4 \\ 2 & 2 & 0 & 0 & -4 \\ 2 & 0 & 2 & 0 & 2 \\ 2 & 0 & 0 & 2 & 6 \end{array}\right] \sim \left[\begin{array}{cccc|c} 1 & 0 & 0 & 1 & 3 \\ 0 & 1 & 0 & -1 & -5 \\ 0 & 0 & 1 & -1 & -2 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right]
从化简后的增广矩阵，我们可以解出：
x1=3−x4,x2=−5+x4,x3=−2+x4,x4 是自由变量x_1 = 3-x_4,\quad x_2 = -5 + x_4,\quad x_3 = -2 + x_4, \quad x_4 ~ \text{是自由变量}
所以，Ax=b\mathbf{A}\mathbf{x} = \mathbf{b}的最小二乘具有下面通解形式：
x^=[3−5−20]+x4[−1111]\mathbf{\hat{x}} = \begin{bmatrix} 3 \\ -5 \\ -2 \\ 0 \end{bmatrix} + x_4 \begin{bmatrix} -1 \\ 1 \\ 1 \\ 1 \end{bmatrix}

4. 最小二乘法的误差分析

当使用最小二乘解 x^ ~\hat{\mathbf{x}}~计算 Ax^ ~\mathbf{A}\hat{\mathbf{x}}~作为 b ~\mathbf{b}~的近似时， b ~\mathbf{b}~与 Ax^ ~\mathbf{A}\hat{\mathbf{x}}~的距离称为最小二乘误差 (least-squares error) ~(\textbf{least-squares error})~。数学上，这个误差由欧几里得范数（ ℓ2 ~\ell_2~范数）表示，即：
∥b−Ax^∥\|\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}\|
借用前面 3.1 中的示例，我们来计算最小二乘解的最小二乘误差。已知：
b=[2011],Ax^=[400211][12]=[443]\mathbf{b} = \begin{bmatrix} 2 \\ 0 \\ 11 \end{bmatrix} ,\quad \mathbf{A}\hat{\mathbf{x}} = \begin{bmatrix} 4 & 0 \\ 0 & 2 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix} = \begin{bmatrix} 4 \\ 4 \\ 3 \end{bmatrix}
计算 r=b−Ax^ ~\mathbf{r} = \mathbf{b} - \mathbf{A}\hat{\mathbf{x}}~（r \mathbf{r}~也被称作残差向量，Residual Vector\textbf{Residual Vector}）：
b−Ax^=[2011]−[443]=[−2−48]\mathbf{b} - \mathbf{A}\hat{\mathbf{x}} = \begin{bmatrix} 2 \\ 0 \\ 11 \end{bmatrix} - \begin{bmatrix} 4 \\ 4 \\ 3 \end{bmatrix} = \begin{bmatrix} -2 \\ -4 \\ 8 \end{bmatrix}
计算最小二乘误差：
∥b−Ax^∥=(−2)2+(−4)2+82=4+16+64=84\| \mathbf{b} - \mathbf{A}\hat{\mathbf{x}} \| = \sqrt{(-2)^2 + (-4)^2 + 8^2} = \sqrt{4 + 16 + 64} = \sqrt{84}

5. 求解最小二乘问题的其它方法

在求解最小二乘问题时，除了使用法方程 ATAx=ATb ~\mathbf{A}^T\mathbf{A}\mathbf{x} = \mathbf{A}^T\mathbf{b}~之外，在特定情况下可以采用更直接或更稳定的方法。如果矩阵 A ~\mathbf{A}~的列向量正交，则最小二乘解可以通过投影公式直接计算，无需求解方程组，计算过程更简单。而当矩阵 A ~\mathbf{A}~的列向量线性无关但不正交时，可以使用 QR 分解，将问题转换为求解上三角方程，从而避免法方程带来的数值不稳定性。下面分别来介绍这两种方法。

5.1 正交列矩阵下的最小二乘解计算

当矩阵 A ~\mathbf{A}~的列正交时，求解最小二乘问题 Ax=b ~\mathbf{A}\mathbf{x} = \mathbf{b}~的过程会很简单。最小二乘解的核心思想是找到向量 b ~\mathbf{b}~在矩阵 A ~\mathbf{A}~的列空间 ColA ~\text{Col}\mathbf{A}~上的正交投影 b^ ~\hat{\mathbf{b}}~，即：
b^=projColAb\mathbf{\hat{b}} = \text{proj}_{\text{Col}\mathbf{A}} \mathbf{b}
如果矩阵 A ~\mathbf{A}~的列是正交的（即 ai⋅aj=0,  i≠j ~\mathbf{a}_i\cdot \mathbf{a}_j = 0,~~i\neq j~），那么直接应用用投影计算公式即可：
b^=∑ib⋅aiai⋅aiai\mathbf{\hat{b}} = \sum_i \frac{\mathbf{b} \cdot \mathbf{a}_i}{\mathbf{a}_i \cdot \mathbf{a}_i} \mathbf{a}_i
下面的示例中 A ~\mathbf{A}~的列向量正交，我们来计算最小二乘解问题。条件如下：
A=[1−61−21117],b=[−1216]\mathbf{A} = \begin{bmatrix} 1 & -6 \\ 1 & -2 \\ 1 & 1 \\ 1 & 7 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} -1 \\ 2 \\ 1 \\ 6 \end{bmatrix}
由于列向量 a1 ~\mathbf{a}_1~和 a2 ~\mathbf{a}_2~正交，最小二乘解可通过如下投影公式得到：
b^=c1a1+c2a2=b⋅a1a1⋅a1a1+b⋅a2a2⋅a2a2=2[1111]+4590[−6−217]=[−115/211/2]\begin{align*}\mathbf{\hat{b}} &= c_1\mathbf{a}_1 + c_2\mathbf{a}_2 \\[2ex] &= \frac{\mathbf{b} \cdot \mathbf{a_1}}{\mathbf{a_1} \cdot \mathbf{a_1}} \mathbf{a_1} + \frac{\mathbf{b} \cdot \mathbf{a_2}}{\mathbf{a_2} \cdot \mathbf{a_2}} \mathbf{a_2}\\[3ex] &= 2\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} + \frac{45}{90}\begin{bmatrix} -6 \\ -2 \\ 1 \\ 7 \end{bmatrix} = \begin{bmatrix} -1 \\ 1 \\ 5/2 \\ 11/2 \end{bmatrix} \end{align*}
x^ \hat{\mathbf{x}}~由系数 c1, c2 ~c_1,~c_2~构成：
x^=[c1c2]=[21/2]\hat{\mathbf{x}} = \begin{bmatrix}c_1 \\ c_2 \end{bmatrix} = \begin{bmatrix}2 \\ 1/2\end{bmatrix}

5.2 QR 分解求最小二乘解

当矩阵 A ~\mathbf{A}~的列向量线性无关时，使用 QR 分解来计算最小二乘解效率更高。相比于直接求解法方程 ATAx=ATb ~\mathbf{A}^T\mathbf{A}\mathbf{x} = \mathbf{A}^T\mathbf{b}~，QR 分解可以避免求逆矩阵，更适用于大规模矩阵或病态矩阵(ill-conditioned matrix)(\textbf{ill-conditioned matrix})。

证明 x^=R−1QTb ~\hat{\mathbf{x}} = \mathbf{R}^{-1}\mathbf{Q}^T\mathbf{b}~是方程 Ax=b ~\mathbf{A}\mathbf{x} = \mathbf{b}~的唯一最小二乘解。
  1. 令x^=R−1QTb\hat{\mathbf{x}} = \mathbf{R}^{-1}\mathbf{Q}^T\mathbf{b}，则
    Ax^=QRx^\mathbf{A}\hat{\mathbf{x}} = \mathbf{Q}\mathbf{R} \hat{\mathbf{x}}
  2. 代入x^\hat{\mathbf{x}}：
    Ax^=QRR−1QTb\mathbf{A}\hat{\mathbf{x}} = \mathbf{Q} \mathbf{R} \mathbf{R}^{-1} Q^T \mathbf{b}
    由于 RR−1=I ~\mathbf{R}\mathbf{R}^{-1} = \mathbf{I}~，化简得：Ax^=QQTb\mathbf{A}\hat{\mathbf{x}} = \mathbf{Q} \mathbf{Q}^T \mathbf{b}
  3. 由定理 12，矩阵 Q ~\mathbf{Q}~的列向量是构成 ColA ~\text{Col}\mathbf{A}~的标准正交基，且QQTb\mathbf{Q}\mathbf{Q}^T\mathbf{b}是b\mathbf{b}在ColA\text{Col}\mathbf{A}上的正交投影：
    b^=QQTb\hat{\mathbf{b}} = \mathbf{Q}\mathbf{Q}^T\mathbf{b}
    因此：
    Ax^=b^\mathbf{A}\hat{\mathbf{x}} = \hat{\mathbf{b}}
    这说明 x^ ~\hat{\mathbf{x}}~是最小二乘解。
  4. 唯一性由定理 14保证，因为 A ~\mathbf{A}~的列向量线性无关，最小二乘解唯一。
  5. 结论： x^=R−1QTb ~\hat{\mathbf{x}} = \mathbf{R}^{-1}\mathbf{Q}^T\mathbf{b}~是 Ax=b ~\mathbf{A}\mathbf{x} = \mathbf{b}~的唯一最小二乘解。
下面的示例中 A ~\mathbf{A}~的列向量线性无关。给定矩阵和向量：
A=[135110112133],b=[357−3]\mathbf{A} = \begin{bmatrix} 1 & 3 & 5 \\ 1 & 1 & 0 \\ 1 & 1 & 2 \\ 1 & 3 & 3 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 3 \\ 5 \\ 7 \\ -3 \end{bmatrix}

  1. 进行 QR 分解：这里忽略矩阵 A ~\mathbf{A}~的 QR 分解过程，QR 分解后的形式如下：
    A=QR=[1/21/21/21/21/2−1/2−1/2−1/21/2−1/21/21/21/21/2−1/2−1/2][245023002000]\mathbf{A} = \mathbf{Q} \mathbf{R} = \begin{bmatrix} 1/2 & 1/2 & 1/2 & 1/2 \\ 1/2 & -1/2 & -1/2 & -1/2 \\ 1/2 & -1/2 & 1/2 & 1/2 \\ 1/2 & 1/2 & -1/2 & -1/2 \end{bmatrix} \begin{bmatrix} 2 & 4 & 5 \\ 0 & 2 & 3 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \end{bmatrix}
  2. 计算 QTb ~\mathbf{Q}^T\mathbf{b}~：
    QTb=[1/21/21/21/21/2−1/2−1/21/21/2−1/21/2−1/2][357−3]=[6−64]\mathbf{Q}^T \mathbf{b} = \begin{bmatrix} 1/2 & 1/2 & 1/2 & 1/2 \\ 1/2 & -1/2 & -1/2 & 1/2 \\ 1/2 & -1/2 & 1/2 & -1/2 \end{bmatrix} \begin{bmatrix} 3 \\ 5 \\ 7 \\ -3 \end{bmatrix} = \begin{bmatrix} 6 \\ -6 \\ 4 \end{bmatrix}
  3. 求解上三角方程 Rx=QTb ~\mathbf{R}\mathbf{x} = \mathbf{Q}^T\mathbf{b}~：
    [245023002][x1x2x3]=[6−64]\begin{bmatrix} 2 & 4 & 5 \\ 0 & 2 & 3 \\ 0 & 0 & 2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 6 \\ -6 \\ 4 \end{bmatrix}
    解得最小二乘解：
    x^=[10−62]\hat{\mathbf{x}} = \begin{bmatrix} 10 \\ -6 \\ 2 \end{bmatrix}

6.4 格拉姆-施密特正交化

6.6 机器学习和线性模型

bei an浙ICP备2024102481号