1. 最小二乘问题概述 在实际应用中，由于数据不完整或噪声等原因，我们经常会遇到一些 不相容的方程组 最小二乘法 ( least squares solution ) ~(\textbf{least squares solution})~ ( least squares solution ) 最小化误差的平方和
在几何上，最小二乘问题的解可以通过正交投影来理解。向量 b ~\mathbf{b}~ b Col A ~\text{Col}\,\mathbf{A}~ Col A
2. 一般最小二乘问题的解 接下来，我们将讨论如何求解最小二乘问题，并分析其解所满足的数学特性。这些特性不仅揭示了最小二乘解的几何意义，还确保了它在误差最小化方面的最优性。
2.1 正交投影与最优逼近 在求解最小二乘问题时，我们应用 最佳逼近定理 。设 A ~\mathbf{A}~ A m × n ~m\times n~ m × n b ~\mathbf{b}~ b R m ~\mathbb{R^m}~ R m x ∈ R n ~\mathbf{x} \in \mathbb{R}^n~ x ∈ R n A x \mathbf{A}\mathbf{x} Ax b ~\mathbf{b}~ b ∥ A x − b ∥ ~\|\mathbf{A}\mathbf{x} - \mathbf{b}\|~ ∥ Ax − b ∥ b ~\mathbf{b}~ b Col A ~\text{Col}\,A~ Col A
b ^ = proj Col A b \mathbf{\hat{b}} = \text{proj}_{\text{Col}A} \mathbf{b} b ^ = proj Col A b 由于 b ^ ~\hat{\mathbf{b}}~ b ^ Col A ~\text{Col}\mathbf{A}~ Col A b ~\mathbf{b}~ b
A x ^ = b ^ \mathbf{A} \hat{\mathbf{x}} = \hat{\mathbf{b}} A x ^ = b ^ 这保证了 A x ^ ~\mathbf{A}\hat{\mathbf{x}}~ A x ^ Col A ~\text{Col}\mathbf{A}~ Col A b ~\mathbf{b}~ b
2.2 误差向量的正交性质 误差向量 b − A x ^ ~\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}~ b − A x ^ Col A ~\text{Col}\mathbf{A}~ Col A A ~\mathbf{A}~ A a j ~\mathbf{a}_j~ a j A ~\mathbf{A}~ A a j ⋅ ( b − A x ^ ) = 0 ~\mathbf{a}_j\cdot (\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}) = 0~ a j ⋅ ( b − A x ^ ) = 0 点积的矩阵乘法的形式 还可以写为 a j T ( b − A x ^ ) = 0 ~\mathbf{a}_j^T(\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}) = 0 ~ a j T ( b − A x ^ ) = 0
[ a 1 T a 2 T ⋮ a n T ] ( b − A x ^ ) = A T ( b − A x ^ ) = 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} a 1 T a 2 T ⋮ a n T ( b − A x ^ ) = A T ( b − A x ^ ) = 0 ( 2 ) 对 ( 2 ) ~(2)~ ( 2 )
A T b − A T A x ^ = 0 \mathbf{A}^T \mathbf{b} - \mathbf{A}^T \mathbf{A} \hat{\mathbf{x}} = \mathbf{0} A T b − A T A x ^ = 0 整理得：
A T A x ^ = A T b (3) \colorbox{#F0F8FF}{$\mathbf{A}^T \mathbf{A} \hat{\mathbf{x}} = \mathbf{A}^T \mathbf{b}$}\tag{3} A T A x ^ = A T b ( 3 ) 这就是法方程 ( Normal Equations ) (\textbf{Normal Equations}) ( Normal Equations ) 正规方程 ，其解即为最小二乘解。
2.3 最小二乘解与法方程的关系 下面的定理说明法方程的解集就是最小二乘解集：
3. 最小二乘法求解 法方程 A T A x ^ = A T b ~\mathbf{A}^T \mathbf{A} \hat{\mathbf{x}} = \mathbf{A}^T \mathbf{b}~ A T A x ^ = A T b n × n ~n\times n~ n × n A T A ~\mathbf{A}^T\mathbf{A}~ A T A
x = ( A T A ) − 1 A T b (4) \colorbox{#F0F8FF}{$\mathbf{x} = (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T \mathbf{b}$}\tag{4} x = ( A T A ) − 1 A T b ( 4 ) 如果 A T A ~\mathbf{A}^T\mathbf{A}~ A T A
下面通过两个示例来说明这两种情况。
3.1 存在唯一解的情况 求下面这个不相容的方程组 A x = b ~\mathbf{A}\mathbf{x} = \mathbf{b}~ Ax = b
A = [ 4 0 0 2 1 1 ] , b = [ 2 0 11 ] \mathbf{A} = \begin{bmatrix} 4 & 0 \\ 0 & 2 \\ 1 & 1 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 2 \\ 0 \\ 11 \end{bmatrix} A = 4 0 1 0 2 1 , b = 2 0 11 计算：
A T A = [ 17 1 1 5 ] , A T b = [ 19 11 ] \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} A T A = [ 17 1 1 5 ] , A T b = [ 19 11 ] 由于 det ( A T A ) ≠ 0 ~\det(\mathbf{A}^T\mathbf{A}) \neq 0~ det ( A T A ) = 0
x ^ = ( A T A ) − 1 A T b = [ 1 2 ] \hat{\mathbf{x}} = (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T \mathbf{b} = \begin{bmatrix} 1 \\ 2 \end{bmatrix} x ^ = ( A T A ) − 1 A T b = [ 1 2 ] 即 x ^ = [ 1 2 ] T ~\hat{\mathbf{x}} = \begin{bmatrix} 1 & 2 \end{bmatrix}^T~ x ^ = [ 1 2 ] T 唯一解 ，它使得 A x ^ ~\mathbf{A}\hat{\mathbf{x}}~ A x ^ b ~\mathbf{b}~ b
3.2 最小二乘解不唯一的情况 求下面这个不相容的方程组 A x = b ~\mathbf{A}\mathbf{x} = \mathbf{b}~ Ax = b
A = [ 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 ] , b = [ − 3 − 1 0 2 5 1 ] \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} A = 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 , b = − 3 − 1 0 2 5 1 计算
A T A = [ 6 2 2 2 2 2 0 0 2 0 2 0 2 0 0 2 ] , A T b = [ 4 − 4 2 6 ] \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} A T A = 6 2 2 2 2 2 0 0 2 0 2 0 2 0 0 2 , A T b = 4 − 4 2 6 由于 det ( A T A ) = 0 ~\det(\mathbf{A}^T\mathbf{A}) = 0~ det ( A T A ) = 0 A T A \mathbf{A}^T\mathbf{A}~ A T A A T A = A T b ~\mathbf{A}^T\mathbf{A} = \mathbf{A}^T\mathbf{b}~ A T A = A T b
[ 6 2 2 2 4 2 2 0 0 − 4 2 0 2 0 2 2 0 0 2 6 ] ∼ [ 1 0 0 1 3 0 1 0 − 1 − 5 0 0 1 − 1 − 2 0 0 0 0 0 ] \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] 6 2 2 2 2 2 0 0 2 0 2 0 2 0 0 2 4 − 4 2 6 ∼ 1 0 0 0 0 1 0 0 0 0 1 0 1 − 1 − 1 0 3 − 5 − 2 0 从化简后的增广矩阵，我们可以解出：
x 1 = 3 − x 4 , x 2 = − 5 + x 4 , x 3 = − 2 + x 4 , x 4 是自由变量 x_1 = 3-x_4,\quad x_2 = -5 + x_4,\quad x_3 = -2 + x_4, \quad x_4 ~ \text{是自由变量} x 1 = 3 − x 4 , x 2 = − 5 + x 4 , x 3 = − 2 + x 4 , x 4 是自由变量 所以， A x = b \mathbf{A}\mathbf{x} = \mathbf{b} Ax = b
x ^ = [ 3 − 5 − 2 0 ] + x 4 [ − 1 1 1 1 ] \mathbf{\hat{x}} = \begin{bmatrix} 3 \\ -5 \\ -2 \\ 0 \end{bmatrix} + x_4 \begin{bmatrix} -1 \\ 1 \\ 1 \\ 1 \end{bmatrix} x ^ = 3 − 5 − 2 0 + x 4 − 1 1 1 1 4. 最小二乘法的误差分析 当使用最小二乘解 x ^ ~\hat{\mathbf{x}}~ x ^ A x ^ ~\mathbf{A}\hat{\mathbf{x}}~ A x ^ b ~\mathbf{b}~ b b ~\mathbf{b}~ b A x ^ ~\mathbf{A}\hat{\mathbf{x}}~ A x ^ 最小二乘误差 ( least-squares error ) ~(\textbf{least-squares error})~ ( least-squares error ) ℓ 2 ~\ell_2~ ℓ 2
∥ b − A x ^ ∥ \|\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}\| ∥ b − A x ^ ∥ 借用前面 3.1 中的示例，我们来计算最小二乘解的最小二乘误差。已知：
b = [ 2 0 11 ] , A x ^ = [ 4 0 0 2 1 1 ] [ 1 2 ] = [ 4 4 3 ] \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} b = 2 0 11 , A x ^ = 4 0 1 0 2 1 [ 1 2 ] = 4 4 3 计算 r = b − A x ^ ~\mathbf{r} = \mathbf{b} - \mathbf{A}\hat{\mathbf{x}}~ r = b − A x ^ r \mathbf{r}~ r 残差向量 ， Residual Vector \textbf{Residual Vector} Residual Vector
b − A x ^ = [ 2 0 11 ] − [ 4 4 3 ] = [ − 2 − 4 8 ] \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 − A x ^ = 2 0 11 − 4 4 3 = − 2 − 4 8 计算最小二乘误差：
∥ b − A x ^ ∥ = ( − 2 ) 2 + ( − 4 ) 2 + 8 2 = 4 + 16 + 64 = 84 \| \mathbf{b} - \mathbf{A}\hat{\mathbf{x}} \| = \sqrt{(-2)^2 + (-4)^2 + 8^2} = \sqrt{4 + 16 + 64} = \sqrt{84} ∥ b − A x ^ ∥ = ( − 2 ) 2 + ( − 4 ) 2 + 8 2 = 4 + 16 + 64 = 84 5. 求解最小二乘问题的其它方法 在求解最小二乘问题时，除了使用法方程 A T A x = A T b ~\mathbf{A}^T\mathbf{A}\mathbf{x} = \mathbf{A}^T\mathbf{b}~ A T Ax = A T b A ~\mathbf{A}~ A A ~\mathbf{A}~ A
5.1 正交列矩阵下的最小二乘解计算 当矩阵 A ~\mathbf{A}~ A A x = b ~\mathbf{A}\mathbf{x} = \mathbf{b}~ Ax = b b ~\mathbf{b}~ b A ~\mathbf{A}~ A Col A ~\text{Col}\mathbf{A}~ Col A b ^ ~\hat{\mathbf{b}}~ b ^
b ^ = proj Col A b \mathbf{\hat{b}} = \text{proj}_{\text{Col}\mathbf{A}} \mathbf{b} b ^ = proj Col A b 如果矩阵 A ~\mathbf{A}~ A a i ⋅ a j = 0 , i ≠ j ~\mathbf{a}_i\cdot \mathbf{a}_j = 0,~~i\neq j~ a i ⋅ a j = 0 , i = j
b ^ = ∑ i b ⋅ a i a i ⋅ a i a i \mathbf{\hat{b}} = \sum_i \frac{\mathbf{b} \cdot \mathbf{a}_i}{\mathbf{a}_i \cdot \mathbf{a}_i} \mathbf{a}_i b ^ = i ∑ a i ⋅ a i b ⋅ a i a i 下面的示例中 A ~\mathbf{A}~ A
A = [ 1 − 6 1 − 2 1 1 1 7 ] , b = [ − 1 2 1 6 ] \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} A = 1 1 1 1 − 6 − 2 1 7 , b = − 1 2 1 6 由于列向量 a 1 ~\mathbf{a}_1~ a 1 a 2 ~\mathbf{a}_2~ a 2
b ^ = c 1 a 1 + c 2 a 2 = b ⋅ a 1 a 1 ⋅ a 1 a 1 + b ⋅ a 2 a 2 ⋅ a 2 a 2 = 2 [ 1 1 1 1 ] + 45 90 [ − 6 − 2 1 7 ] = [ − 1 1 5 / 2 11 / 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*} b ^ = c 1 a 1 + c 2 a 2 = a 1 ⋅ a 1 b ⋅ a 1 a 1 + a 2 ⋅ a 2 b ⋅ a 2 a 2 = 2 1 1 1 1 + 90 45 − 6 − 2 1 7 = − 1 1 5/2 11/2 x ^ \hat{\mathbf{x}}~ x ^ c 1 , c 2 ~c_1,~c_2~ c 1 , c 2
x ^ = [ c 1 c 2 ] = [ 2 1 / 2 ] \hat{\mathbf{x}} = \begin{bmatrix}c_1 \\ c_2 \end{bmatrix} = \begin{bmatrix}2 \\ 1/2\end{bmatrix} x ^ = [ c 1 c 2 ] = [ 2 1/2 ] 5.2 QR 分解求最小二乘解 当矩阵 A ~\mathbf{A}~ A A T A x = A T b ~\mathbf{A}^T\mathbf{A}\mathbf{x} = \mathbf{A}^T\mathbf{b}~ A T Ax = A T b 病态矩阵 ( ill-conditioned matrix ) (\textbf{ill-conditioned matrix}) ( ill-conditioned matrix )
下面的示例中 A ~\mathbf{A}~ A
A = [ 1 3 5 1 1 0 1 1 2 1 3 3 ] , b = [ 3 5 7 − 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} A = 1 1 1 1 3 1 1 3 5 0 2 3 , b = 3 5 7 − 3 
