（线性代数最小二乘问题）Normal Equation（正规方程）

Normal Equation（正规方程） 是线性代数中的一个重要概念，主要用于解决最小二乘问题（Least Squares Problem）。它通过直接求解一个线性方程组，找到线性回归模型的最优参数（如权重或系数）。以下是详细介绍：

1. 定义与数学表达式

给定一个超定方程组（方程数量多于未知数）：
$$A\mathbf{x}=\mathbf{b}$$
其中：

• A∈Rm×nA \\in \\mathbb{R}^{m \\times n}A∈Rm×n（$m>n$）是一个设计矩阵（Design Matrix），
• x∈Rn\\mathbf{x} \\in \\mathbb{R}^nx∈Rn 是未知参数向量，
• b∈Rm\\mathbf{b} \\in \\mathbb{R}^mb∈Rm 是目标向量（通常不在 $A$ 的列空间中）。

由于 $A\mathbf{x}=\mathbf{b}$ 通常无解，Normal Equation 的目标是找到一个近似解 $\mathbf{x}$，使得残差向量 $\mathbf{e}=\mathbf{b}-A\mathbf{x}$ 的 L2 范数最小（即最小化误差平方和）。

Normal Equation 的公式为：
ATAx=ATbA^T A \\mathbf{x} = A^T \\mathbf{b}ATAx=ATb
如果 ATAA^T AATA 可逆，则最优解为：
x=(ATA)−1ATb\\mathbf{x} = (A^T A)^{-1} A^T \\mathbf{b}x=(ATA)−1ATb

2. 推导方法

方法一：矩阵求导

1. 定义损失函数（误差平方和）：
   J(x)=∥b−Ax∥22=(b−Ax)T(b−Ax)J(\\mathbf{x}) = \\|\\mathbf{b} - A\\mathbf{x}\\|_2^2 = (\\mathbf{b} - A\\mathbf{x})^T (\\mathbf{b} - A\\mathbf{x})J(x)=∥b−Ax∥22​=(b−Ax)T(b−Ax)
2. 对 $\mathbf{x}$ 求导并令导数为零：
   ∂J∂x=−2ATb+2ATAx=0\\frac{\\partial J}{\\partial \\mathbf{x}} = -2A^T \\mathbf{b} + 2A^T A \\mathbf{x} = 0∂x∂J​=−2ATb+2ATAx=0
3. 得到 Normal Equation：
   ATAx=ATbA^T A \\mathbf{x} = A^T \\mathbf{b}ATAx=ATb

方法二：几何投影

1. 几何视角：
   • $A\mathbf{x}$ 是 $\mathbf{b}$ 在 $A$ 的列空间（Column Space, $C(A)$）上的投影 $\mathbf{p}$。
   • 残差向量 $\mathbf{e}=\mathbf{b}-\mathbf{p}$ 必须正交于列空间，即：
     ATe=0⇒AT(b−Ax)=0A^T \\mathbf{e} = 0 \\quad \\Rightarrow \\quad A^T (\\mathbf{b} - A\\mathbf{x}) = 0ATe=0⇒AT(b−Ax)=0
   • 由此得到 Normal Equation：
     ATAx=ATbA^T A \\mathbf{x} = A^T \\mathbf{b}ATAx=ATb

3. 几何解释

• 列空间与投影：
  $A$ 的列空间 $C(A)$ 是所有可能的 $A\mathbf{x}$ 组成的子空间。由于 $\mathbf{b}$ 不在 $C(A)$ 中，我们寻找 $\mathbf{x}$ 使得 $A\mathbf{x}$ 是 $\mathbf{b}$ 在 $C(A)$ 上的投影 $\mathbf{p}$。

• 正交性条件：
  残差 $\mathbf{e}=\mathbf{b}-\mathbf{p}$ 必须与列空间正交（即 e∈N(AT)\\mathbf{e} \\in N(A^T)e∈N(AT)），从而导出 Normal Equation。

4. 应用场景

Normal Equation 是线性回归的核心工具，尤其适用于以下情况：

1. 小规模数据集：当特征数 $n$ 较小时（如 $n<10,000$），计算 (ATA)−1(A^T A)^{-1}(ATA)−1 的开销较小。
2. 无需迭代：与梯度下降等迭代方法不同，Normal Equation 直接通过矩阵运算得到解析解。
3. 理论分析：在数学推导中，Normal Equation 提供了最小二乘解的唯一性、存在性等性质。

5. 注意事项

1. 矩阵可逆性：

   • ATAA^T AATA 必须是可逆的（即 $A$ 列满秩，$\text{rank}(A)=n$）。
   • 如果 ATAA^T AATA 不可逆（如特征间线性相关），则有无穷多解，此时需选择最小范数解（通过伪逆 A†A^\\daggerA†）。

2. 计算复杂度：

   • 计算 (ATA)−1(A^T A)^{-1}(ATA)−1 的时间复杂度为 O(n3)O(n^3)O(n3)，当 $n$ 较大时效率较低。
   • 此时通常改用梯度下降或正则化方法（如岭回归）。

3. 数值稳定性：

   • 若 $A$ 接近病态矩阵（条件数很大），可能导致 ATAA^T AATA 不可逆或结果不稳定。

6. 示例

假设我们有以下数据：
A=[121314],b=[234]A = \\begin{bmatrix} 1 & 2 \\\\ 1 & 3 \\\\ 1 & 4 \\end{bmatrix}, \\quad \\mathbf{b} = \\begin{bmatrix} 2 \\\\ 3 \\\\ 4 \\end{bmatrix}A=​111​234​​,b=​234​​

1. 计算 ATAA^T AATA 和 ATbA^T \\mathbf{b}ATb：
   ATA=[39929],ATb=[929]A^T A = \\begin{bmatrix} 3 & 9 \\\\ 9 & 29 \\end{bmatrix}, \\quad A^T \\mathbf{b} = \\begin{bmatrix} 9 \\\\ 29 \\end{bmatrix}ATA=[39​929​],ATb=[929​]
2. 解 Normal Equation：
   [39929][x1x2]=[929]\\begin{bmatrix} 3 & 9 \\\\ 9 & 29 \\end{bmatrix} \\begin{bmatrix} x_1 \\\\ x_2 \\end{bmatrix} = \\begin{bmatrix} 9 \\\\ 29 \\end{bmatrix}[39​929​][x1​x2​​]=[929​]
   解得 x=[0,1]T\\mathbf{x} = [0, 1]^Tx=[0,1]T，即最佳拟合直线为 $y=0+1x$。

7. 总结