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

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

1. 定义与数学表达式

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

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

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

Normal Equation 的公式为：
$$A^{T}A\mathbf{x}=A^T\mathbf{b}$$
如果 $ A^T A $ 可逆，则最优解为：
$$\mathbf{x}=(A^{T}A{)}^{-1}{A}^T\mathbf{b}$$

2. 推导方法

方法一：矩阵求导

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

方法二：几何投影

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

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} $ 必须与列空间正交（即 $ \mathbf{e} \in N(A^T) $），从而导出 Normal Equation。

4. 应用场景

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

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

5. 注意事项

1. 矩阵可逆性：

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

2. 计算复杂度：

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

3. 数值稳定性：

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

6. 示例

假设我们有以下数据：
$$A=\left[\begin{array}{cc}1& 2\\ 1& 3\\ 1& 4\end{array}\right],\mathbf{b}=\left[\begin{array}{c}2\\ 3\\ 4\end{array}\right]$$

1. 计算 $ A^T A $ 和 $ A^T \mathbf{b} $：
   $$A^{T}A=\left[\begin{array}{cc}3& 9\\ 9& 29\end{array}\right],A^T\mathbf{b}=\left[\begin{array}{c}9\\ 29\end{array}\right]$$
2. 解 Normal Equation：
   $$\left[\begin{array}{cc}3& 9\\ 9& 29\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}9\\ 29\end{array}\right]$$
   解得 $ \mathbf{x} = [0, 1]^T $，即最佳拟合直线为 $ y = 0 + 1x $。

7. 总结