05 最小二乘、约束问题与正则化

1. 几何条件：残差必须正交

对 $A\in {\mathbb{C}}^{m\times n}$，最小二乘问题是

$$\underset{x}{min}\parallel b-Ax{\parallel }_2.$$

最优残差 $r=b-Ax$ 满足

$$A^{\ast }r=0,$$

即 $r\perp \mathrm{range}(A)$。这给出正规方程

$$A^{\ast }Ax=A^{\ast }b.$$

2. 四种解法不是同一质量

正规方程

形成 $A^{\ast }A$ 后做 Cholesky。速度快，但

$${\kappa }_2(A^{\ast }A)={\kappa }_2(A{)}^2,$$

因此会放大病态性。

QR 分解

若 $A=QR$ 且满列秩，则

$$Rx=Q^{\ast }b.$$

Householder QR 不平方条件数，是一般稠密最小二乘的可靠默认选择。

SVD

若 $A=U\mathrm{\Sigma }{V}^{\ast }$，则

$$x=A^{†}b=V{\mathrm{\Sigma }}^{†}{U}^{\ast }b.$$

SVD 成本较高，但能处理秩亏并清楚显示不稳定方向。

增广系统

一阶条件可写成

$$\left(\begin{array}{cc}I& A\\ A^{\ast }& 0\end{array}\right)\left(\begin{array}{c}r\\ x\end{array}\right)=\left(\begin{array}{c}b\\ 0\end{array}\right).$$

它保留残差变量，适合某些稀疏或约束算法，但系统变成不定。

3. 列选主元 QR 与数值秩

当列近线性相关时，使用

$$AP=QR$$

并优先选择剩余范数较大的列。$R$ 的对角衰减可帮助估计数值秩。它比 SVD 便宜，但秩判定能力通常不如 SVD 精确。

若 $A$ 秩亏，最小二乘解不唯一。SVD 给出所有解

$$x=A^{†}b+(I-A^{†}A)z,$$

其中第二项位于 $\ker (A)$。令 $z=0$ 得到唯一的最小 2-范数解。伪逆满足四个 Penrose 条件：

$$A{A}^{†}A=A,A^{†}A{A}^{†}=A^{†},(A{A}^{†}{)}^{\ast }=A{A}^{†},(A^{†}A{)}^{\ast }=A^{†}A.$$

4. 等式约束最小二乘

问题

$$\underset{Cx=d}{min}\parallel Ax-b{\parallel }_2$$

可先用正交变换把约束 $C$ 化简，将变量分成被约束和自由两部分，再在自由变量上解较小的最小二乘问题。关键是避免显式构造约束零空间中条件不良的基。

另一条路线是 KKT 系统。对

$$\underset{x}{min}\frac{1}{2}\parallel Ax-b{\parallel }_2^2\text{s.t. }Cx=d,$$

一阶条件为

$$\left(\begin{array}{cc}{A}^{\ast }A& C^{\ast }\\ C& 0\end{array}\right)\left(\begin{array}{c}x\\ \lambda \end{array}\right)=\left(\begin{array}{c}{A}^{\ast }b\\ d\end{array}\right).$$

它形式直接但可能平方 $A$ 的条件数，并产生不定系统。零空间法若有稳定的正交基，通常更符合数值线性代数原则。

5. Tikhonov 正则化

岭回归/零阶 Tikhonov 问题为

$$\underset{x}{min}\parallel Ax-b{\parallel }_2^2+\lambda \parallel x{\parallel }_2^2,\lambda >0.$$

它等价于增广最小二乘

$$\underset{x}{min}{\Vert \left(\begin{array}{c}A\\ \sqrt{\lambda }I\end{array}\right)x-\left(\begin{array}{c}b\\ 0\end{array}\right)\Vert }_2^2.$$

因此可以直接用 QR/Givens 求解，而不必形成 $A^{\ast }A+\lambda I$。正则化压低小奇异值方向的响应，以偏差换取方差和稳定性。

6. 数据拟合与 Vandermonde 风险

多项式拟合常产生 Vandermonde 矩阵，高次数或节点分布不佳时会非常病态。改善方式包括：

• 缩放并平移自变量；
• 改用正交多项式基；
• 使用 QR/SVD，而非正规方程；
• 根据预测目标控制模型次数。

7. 最小二乘的扰动特征

满列秩最小二乘的敏感性不仅由 $\kappa (A)$ 决定，还与最优残差 $r$ 有关。当模型几乎能解释数据时，主要误差项通常与 $\kappa (A)$ 成正比；当残差很大且 $A$ 接近秩亏时，某些扰动项可能呈现 $\kappa (A{)}^2$。因此“最小二乘一定只受一个条件数控制”是不准确的。

可计算的最优性检查包括

$$\frac{\parallel A^{\ast }r{\parallel }_2}{\parallel A{\parallel }_2\parallel r{\parallel }_2}$$

和相对残差 $\parallel r{\parallel }_2/\parallel b{\parallel }_2$。前者检查正交条件，后者衡量拟合程度；二者回答不同问题。

8. 加权最小二乘

观测误差方差不同或彼此相关时，可解

$$\underset{x}{min}(Ax-b{)}^{\ast }W(Ax-b),W\succ 0.$$

若 $W=C^{\ast }C$，问题等价于 $\underset{x}{min}\parallel C(Ax-b){\parallel }_2$。$W$ 常取协方差矩阵的逆：噪声越小的观测权重越高。不要显式求 $W^{1/2}$ 的逆，优先用 Cholesky 因子和三角求解完成白化。

9. 正则化的奇异值滤波解释

设 $A=U\mathrm{\Sigma }{V}^{\ast }$。Tikhonov 解为

$$x_{\lambda }=\sum _i\frac{{\sigma }_i}{{\sigma }_i^2+\lambda }(u_i^{\ast }b)v_i.$$

普通伪逆中的系数是 $1/{\sigma }_i$，会猛烈放大小奇异值方向的噪声；正则化把它替换为平滑滤波因子。$\lambda$ 越大，方差越小但偏差越大。参数可用交叉验证、L 曲线或 discrepancy principle 选择，而不是机械设成机器精度。

10. 几何最小二乘与代数最小二乘

拟合平面时，代数最小二乘只沿指定坐标方向度量误差；总最小二乘则度量点到仿射子空间的正交距离，因而对坐标旋转不变。总最小二乘先减去样本均值，再对中心化数据矩阵做截断 SVD。最佳仿射子空间一定经过样本均值。

11. 自检

• [ ] 能从投影几何推出正规方程。
• [ ] 能解释为什么正规方程会平方条件数。
• [ ] 能按稳定性与成本比较 QR、SVD 和增广系统。
• [ ] 能把岭回归改写成增广最小二乘。
• [ ] 能写出秩亏最小二乘的通解与最小范数解。
• [ ] 能区分拟合残差与最优性残差。

下一章：幂法与子空间迭代。