8. 范数逼近与正则化

# 范数逼近

范数逼近问题旨在找到向量 $x$，使得 $Ax$ 在某种范数意义下最接近 $b$。不同的范数选择会导致不同的逼近性质和求解方法。

1. 线性范数逼近 (Linear Norm Approximation)

   问题形式

   考虑线性范数逼近问题：

   $$\min \quad \|Ax - b\|$$

   其中 $A \in \mathbb{R}^{m \times n}$，$m \geq n$，$\|\cdot\|$ 是 $\mathbb{R}^m$ 上的范数。

   解的几何解释

   解 $x^* = \arg\min_x \|Ax - b\|$ 的几何意义：

   • 几何解释：$Ax^*$ 是 $A$ 的列空间 $R(A)$ 中离 $b$ 最近的点
   • 估计解释：在线性测量模型 $y = Ax + v$ 中，$y$ 是观测值，$x$ 是未知参数，$v$ 是测量误差

   Galileo 的误差假设

   在 Galileo Galilei 的《关于托勒密和哥白尼两大世界体系的对话》中，提出了以下误差假设：

   1. 误差确实存在
   2. 误差分布是对称的
   3. 大误差出现的概率小于小误差出现的概率

   这些假设为范数逼近问题提供了理论依据。

2. 常见范数逼近方法

   最小二乘逼近（$\ell_2$ 范数）

   最小二乘逼近使用 $\ell_2$ 范数：

   $$\min \quad \|Ax - b\|_2^2$$

   解满足正规方程（normal equations）：

   $$A^T A x = A^T b$$

   如果 $\text{Rank}(A) = n$，则解为：

   $$x^* = (A^T A)^{-1} A^T b$$

   简要证明：因为 $f(x) = x^T A^T A x - 2b^T A x + b^T b$，点 $x$ 最小化 $f(x)$ 当且仅当

   $$\nabla f(x) = 2A^T A x - 2A^T b = 0$$

   Chebyshev 逼近（$\ell_\infty$ 范数）

   Chebyshev 逼近使用 $\ell_\infty$ 范数（最大误差）：

   $$\min \quad \|Ax - b\|_\infty$$

   可以转化为线性规划（LP）问题：

   $$\begin{align*} \min \quad & t \\ \text{s.t.} \quad & -t \cdot \mathbf{1} \leq Ax - b \leq t \cdot \mathbf{1} \end{align*}$$

   其中 $\mathbf{1}$ 是全 1 向量。

   绝对残差和逼近（$\ell_1$ 范数）

   绝对残差和逼近使用 $\ell_1$ 范数：

   $$\min \quad \|Ax - b\|_1$$

   可以转化为线性规划问题：

   $$\begin{align*} \min \quad & \mathbf{1}^T y \\ \text{s.t.} \quad & -y \leq Ax - b \leq y \end{align*}$$

   其中 $y \in \mathbb{R}^m$ 是辅助变量。

3. 非线性范数逼近 (Nonlinear Norm Approximation)

   问题形式

   非线性范数逼近问题：

   $$\begin{align*} \min \quad & \phi(r_1) + \cdots + \phi(r_m) \\ \text{s.t.} \quad & r = Ax - b \end{align*}$$

   其中 $A \in \mathbb{R}^{m \times n}$，$\phi: \mathbb{R} \to \mathbb{R}$ 是凸惩罚函数。

   常见惩罚函数

   • 二次惩罚：$\phi(u) = u^2$（对应最小二乘）
   • 死区线性惩罚（宽度为 $a$）：$\phi(u) = \max\{0, |u| - a\}$
   • 对数障碍惩罚（限制为 $a$）：

     $$\phi(u) = \begin{cases} -a^2 \log(1 - (u/a)^2) & |u| < a \\ \infty & \text{否则} \end{cases}$$

   惩罚函数对残差分布的影响

   惩罚函数的形状对残差的分布有重要影响：

   • $\phi(u) = |u|$：$\ell_1$ 范数，对异常值鲁棒
   • $\phi(u) = u^2$：$\ell_2$ 范数，对异常值敏感
   • $\phi(u) = \max\{0, |u| - a\}$：死区线性，忽略小误差
   • $\phi(u) = -\log(1 - u^2)$：对数障碍，强制误差在 $[-a, a]$ 内

   Huber 惩罚函数

   Huber 惩罚函数（参数为 $M$）：

   $$\phi_{\text{hub}}(u) = \begin{cases} u^2 & |u| < M \\ M(2|u| - M) & |u| \geq M \end{cases}$$

   特点：

   • 对于小误差（$|u| < M$），使用二次惩罚（类似 $\ell_2$）
   • 对于大误差（$|u| \geq M$），使用线性增长（类似 $\ell_1$）
   • 线性增长使得逼近对异常值（outliers）不那么敏感
   • 结合了 $\ell_2$ 和 $\ell_1$ 的优点

   应用示例

   使用二次惩罚（虚线）和 Huber 惩罚（实线）拟合 42 个数据点 $(t_i, y_i)$ 的仿射函数 $f(t) = \alpha + \beta t$：

   • 二次惩罚对异常值敏感，可能被异常值拉偏
   • Huber 惩罚对异常值更鲁棒，拟合结果更稳定

4. 不确定矩阵 $A$ 的鲁棒逼近

   问题设定

   考虑不确定矩阵 $A$ 的范数逼近问题：

   $$\min \quad \|Ax - b\| \quad \text{with uncertain } A$$

   两种方法

   随机方法（Stochastic Approach）

   • 假设 $A$ 是随机的，最小化期望：

     $$\min \quad \mathbb{E}[\|Ax - b\|]$$

   • 适用于已知 $A$ 的概率分布的情况

   最坏情况方法（Worst-Case Approach）

   • 给定 $A$ 的可能值集合 $\text{Set}(A)$，最小化最坏情况：

     $$\min \quad \sup_{A \in \text{Set}(A)} \|Ax - b\|$$

   • 只在特殊情况下可处理（某些范数、分布、$A$ 的集合）

   例子：线性不确定

   考虑 $A(u) = A_0 + A_1 u$，其中 $u$ 是标量不确定参数：

   • $x_{\text{nom}}$ 最小化 $\|A_0 x - b\|_2^2$（标称情况）
   • $x_{\text{stoch}}$ 最小化 $\mathbb{E}[\|A(u)x - b\|_2^2]$，其中 $u$ 在 $[-1, +1]$ 上均匀分布（随机方法）
   • $x_{\text{wc}}$ 最小化 $\sup_{-1 \leq u \leq 1} \|A(u)x - b\|_2^2$（最坏情况方法）

   随机鲁棒最小二乘

   对于 $A = \bar{A} + U$，其中 $U$ 是随机矩阵，$\mathbb{E}[U] = 0$，$\mathbb{E}[U^T U] = P$：

   $$\min \quad \mathbb{E}[\|(\bar{A} + U)x - b\|_2^2]$$

   目标函数的显式表达式：

   $$\begin{aligned} \mathbb{E}[\|Ax - b\|_2^2] &= \mathbb{E}[\|\bar{A}x - b + Ux\|_2^2] \\ &= \|\bar{A}x - b\|_2^2 + \mathbb{E}[x^T U^T U x] \\ &= \|\bar{A}x - b\|_2^2 + x^T P x \end{aligned}$$

   这等价于带正则化的最小二乘问题：

   $$\min \quad \|\bar{A}x - b\|_2^2 + x^T P x$$

5. 不同范数逼近方法的比较

   方法	范数	求解方法	特点
   最小二乘	$\ell_2$	正规方程	对异常值敏感，有解析解
   Chebyshev	$\ell_\infty$	线性规划	最小化最大误差
   绝对残差和	$\ell_1$	线性规划	对异常值鲁棒
   Huber	混合	凸优化	结合 $\ell_2$ 和 $\ell_1$ 优点

# L1 魔法

$\ell_1$ 魔法（$\ell_1$ Magic）是指使用 $\ell_1$ 范数来近似求解 $\ell_0$ 范数问题（稀疏优化问题）的方法。这一方法在压缩感知、稀疏信号恢复、特征选择等领域有重要应用。

1. $\ell_0$ 问题与稀疏性 ($\ell_0$ Problem and Sparsity)

   $\ell_0$ 范数

   $\ell_0$ 范数定义为向量中非零元素的个数：

   $$\|x\|_0 = \#\{i : x_i \neq 0\}$$

   注意：$\ell_0$ 范数实际上不是真正的范数（不满足齐次性），但习惯上称为"范数"。

   稀疏优化问题

   考虑以下稀疏优化问题：

   $$\begin{align*} \min \quad & \|x\|_0 \\ \text{s.t.} \quad & Ax = b \end{align*}$$

   其中 $A \in \mathbb{R}^{m \times n}$，$b \in \mathbb{R}^m$，通常 $m < n$（欠定系统）。

   问题的困难性

   • $\ell_0$ 优化问题是 NP 难问题
   • 需要穷举所有可能的非零位置组合
   • 计算复杂度随 $n$ 指数增长
   • 在实际应用中难以直接求解

   稀疏性的重要性

   稀疏性在信号处理、图像处理、机器学习等领域非常重要：

   • 信号表示：许多自然信号在适当的基下是稀疏的
   • 特征选择：选择最重要的特征，提高模型可解释性
   • 压缩：稀疏表示可以大幅减少存储和传输需求
   • 去噪：稀疏性假设有助于从噪声数据中恢复真实信号

2. $\ell_1$ 魔法 ($\ell_1$ Magic)

   基本思想

   虽然 $\ell_0$ 优化是 NP 难问题，但可以通过凸松弛（convex relaxation）将其转化为可求解的凸优化问题：

   $$\begin{align*} \min \quad & \|x\|_0 \\ \text{s.t.} \quad & Ax = b \end{align*}$$

   $$\quad \xrightarrow{\text{凸松弛}} \quad \begin{align*} \min \quad & \|x\|_1 \\ \text{s.t.} \quad & Ax = b \end{align*}$$

   将 $\ell_0$ 范数替换为 $\ell_1$ 范数，问题变为凸优化问题（线性规划）。

   为什么 $\ell_1$ 能促进稀疏性？

   几何解释：

   • $\ell_1$ 范数的单位球在 $\mathbb{R}^2$ 中是菱形（diamond），在 $\mathbb{R}^3$ 中是八面体
   • $\ell_2$ 范数的单位球是圆形/球形
   • $\ell_1$ 范数的单位球有"尖角"，这些尖角对应稀疏解（某些分量为零）
   • 当约束 $Ax = b$ 与 $\ell_1$ 单位球相交时，交点更可能落在尖角上，从而得到稀疏解

   数学解释：

   • $\ell_1$ 范数是 $\ell_0$ 范数在 $\ell_1$ 单位球上的凸包
   • 在满足某些条件（如 RIP、零空间性质）下，$\ell_1$ 最小化问题的解与 $\ell_0$ 最小化问题的解一致

   Basis Pursuit（基追踪）

   Basis Pursuit 是使用 $\ell_1$ 最小化来寻找稀疏表示的方法：

   $$\begin{align*} \min \quad & \|x\|_1 \\ \text{s.t.} \quad & Ax = b \end{align*}$$

   这可以转化为线性规划问题：

   $$\begin{align*} \min \quad & \mathbf{1}^T (u + v) \\ \text{s.t.} \quad & A(u - v) = b \\ & u \geq 0, \quad v \geq 0 \end{align*}$$

   其中 $x = u - v$，$u, v \in \mathbb{R}^n_+$。

   LASSO（Least Absolute Shrinkage and Selection Operator）

   LASSO 是带 $\ell_1$ 正则化的回归问题：

   $$\min \quad \|Ax - b\|_2^2 + \lambda \|x\|_1$$

   其中 $\lambda > 0$ 是正则化参数，控制稀疏性和拟合误差的权衡。

   特点：

   • 同时进行参数估计和特征选择
   • $\ell_1$ 正则化倾向于将不重要的系数压缩为零
   • 可以处理 $p \gg n$ 的情况（特征数远大于样本数）

3. 压缩感知 (Compressive Sensing)

   基本问题

   压缩感知（Compressed Sensing, CS）研究如何从远少于传统 Nyquist 采样定理要求的测量中恢复稀疏信号。

   问题设定

   假设信号 $x \in \mathbb{R}^n$ 在某个基 $\Psi$ 下是稀疏的：

   $$x = \Psi \theta$$

   其中 $\theta$ 是稀疏系数向量（$\|\theta\|_0 \ll n$）。

   观测模型为：

   $$y = \Phi x + e = \Phi \Psi \theta + e$$

   其中：

   • $\Phi \in \mathbb{R}^{m \times n}$ 是测量矩阵（$m \ll n$）
   • $y \in \mathbb{R}^m$ 是观测向量
   • $e$ 是测量噪声

   恢复问题

   从少量观测 $y$ 恢复原始信号 $x$：

   $$\begin{align*} \min \quad & \|\theta\|_1 \\ \text{s.t.} \quad & \|\Phi \Psi \theta - y\|_2 \leq \epsilon \end{align*}$$

   其中 $\epsilon$ 是噪声水平的上界。

   关键条件

   RIP（Restricted Isometry Property，限制等距性质）：

   矩阵 $A = \Phi \Psi$ 满足 $k$-RIP，如果存在常数 $\delta_k \in (0, 1)$ 使得对所有 $k$-稀疏向量 $x$：

   $$(1 - \delta_k)\|x\|_2^2 \leq \|Ax\|_2^2 \leq (1 + \delta_k)\|x\|_2^2$$

   零空间性质（Null Space Property）：

   矩阵 $A$ 满足零空间性质，如果对于所有 $h \in \text{null}(A)$ 和所有 $k$-稀疏向量 $x$：

   $$\|h_S\|_1 < \|h_{S^c}\|_1$$

   其中 $S$ 是 $x$ 的支撑集，$S^c$ 是补集。

   理论保证

   在满足 RIP 或零空间性质的条件下：

   • $\ell_1$ 最小化可以精确恢复 $k$-稀疏信号
   • 所需的测量数 $m = O(k \log(n/k))$
   • 远少于传统方法所需的 $m = n$ 个测量

   应用

   • 医学成像：压缩感知 MRI，减少扫描时间
   • 图像压缩：单像素相机
   • 信号处理：稀疏信号恢复
   • 通信：稀疏信道估计

4. $\ell_1$ 魔法的优势与局限性

   优势

   • 将 NP 难问题转化为凸优化问题（线性规划）
   • 有高效算法求解（内点法、ADMM 等）
   • 在满足某些条件下，解与 $\ell_0$ 问题一致
   • 对噪声鲁棒

   局限性

   • 需要满足 RIP 或零空间性质等条件
   • 对于某些矩阵 $A$，$\ell_1$ 最小化可能无法恢复真正的稀疏解
   • 正则化参数 $\lambda$ 的选择需要调优
   • 计算复杂度虽然比 $\ell_0$ 低，但对于大规模问题仍可能较高

5. 相关算法与工具

   算法

   • Basis Pursuit：精确约束下的 $\ell_1$ 最小化
   • Basis Pursuit Denoising (BPDN)：带噪声的 $\ell_1$ 最小化
   • LASSO：带 $\ell_1$ 正则化的回归
   • Dantzig Selector：另一种稀疏估计方法

   软件工具

   • $\ell_1$-Magic：MATLAB 工具箱，用于求解 $\ell_1$ 最小化问题
   • CVX：可以方便地表述和求解 $\ell_1$ 优化问题
   • SPGL1：大规模 $\ell_1$ 最小化求解器

# 正则化

正则化（Regularization）是解决不适定问题（ill-posed problems）的重要方法，通过在目标函数中添加正则化项来稳定解、防止过拟合，并提高模型的泛化能力。

1. Tikhonov 正则化 (Tikhonov Regularization)

   历史背景

   Tikhonov 正则化由 A. N. Tikhonov 在 1943 年提出，用于解决不适定逆问题（ill-posed inverse problems）的稳定性问题。

   问题设定

   考虑线性最小二乘问题：

   $$\min \quad \|Ax - b\|_2^2$$

   当 $A$ 的条件数很大或 $A$ 不满秩时，问题可能是不适定的，解对数据扰动非常敏感。

   Tikhonov 正则化问题

   Tikhonov 正则化通过添加正则化项来稳定解：

   $$\min \quad \|Ax - b\|_2^2 + \lambda \|Lx\|_2^2$$

   其中：

   • $\lambda > 0$ 是正则化参数，控制数据拟合项和正则化项的权衡
   • $L$ 是正则化算子（regularization operator），通常是单位矩阵 $I$ 或微分算子
   • $\|Lx\|_2^2$ 是正则化项，惩罚解的"复杂度"

   标准形式（$L = I$）

   当 $L = I$ 时，Tikhonov 正则化变为：

   $$\min \quad \|Ax - b\|_2^2 + \lambda \|x\|_2^2$$

   这称为岭回归（Ridge Regression），由 A. E. Hoerl 和 R. W. Kennard 在 1970 年提出。

   解析解

   Tikhonov 正则化问题的解析解为：

   $$x^* = (A^T A + \lambda L^T L)^{-1} A^T b$$

   当 $L = I$ 时：

   $$x^* = (A^T A + \lambda I)^{-1} A^T b$$

   正则化参数 $\lambda$ 的作用

   • $\lambda = 0$：退化为标准最小二乘问题
   • $\lambda > 0$：增加正则化项，使解更平滑、更稳定
   • $\lambda \to \infty$：解趋向于零

   与鲁棒最小二乘的关系

   从不确定矩阵 $A$ 的随机鲁棒最小二乘问题：

   $$\min \quad \mathbb{E}[\|(\bar{A} + U)x - b\|_2^2]$$

   其中 $A = \bar{A} + U$，$\mathbb{E}[U] = 0$，$\mathbb{E}[U^T U] = P$，可以推导出：

   $$\min \quad \|\bar{A}x - b\|_2^2 + \|P^{1/2} x\|_2^2$$

   这确实是 Tikhonov 正则化的一种形式。

2. 学习中的正则化 (Regularization in Learning)

   过拟合问题

   在机器学习中，当模型过于复杂时，可能会过度拟合训练数据，导致在测试数据上表现不佳。正则化是防止过拟合的重要方法。

   常见正则化方法

   $\ell_2$ 正则化（Ridge Regression）

   $$\min \quad \|Ax - b\|_2^2 + \lambda \|x\|_2^2$$

   • 惩罚大的参数值
   • 使参数向零收缩（shrinkage）
   • 不产生稀疏解

   $\ell_1$ 正则化（LASSO）

   $$\min \quad \|Ax - b\|_2^2 + \lambda \|x\|_1$$

   • 同时进行参数估计和特征选择
   • 产生稀疏解（某些参数精确为零）
   • 适用于特征选择场景

   弹性网络（Elastic Net）

   $$\min \quad \|Ax - b\|_2^2 + \lambda_1 \|x\|_1 + \lambda_2 \|x\|_2^2$$

   • 结合 $\ell_1$ 和 $\ell_2$ 正则化的优点
   • 在特征选择的同时保持稳定性

   正则化与支持向量机

   支持向量机（SVM）中的正则化：

   $$\min \quad \frac{1}{2}\|w\|_2^2 + C \sum_{i=1}^N \xi_i$$

   其中 $\|w\|_2^2$ 是正则化项，控制模型的复杂度；$C$ 是正则化参数，控制对误分类的惩罚。

   正则化与核方法

   在核方法中，正则化算子与支持向量核之间存在密切联系。通过选择合适的正则化算子，可以导出相应的核函数。

3. 成像不可见之物 (Imaging the Invisible)

   极端成像

   正则化在极端成像（Extreme Imaging）中有重要应用，例如：

   • 绕过角落成像（Seeing Around Corners）
   • 黑洞成像（Black Hole Imaging）

   黑洞成像

   2019 年，事件视界望远镜（Event Horizon Telescope, EHT）首次成功拍摄到黑洞图像。这一成就依赖于：

   物理模型反演

   • 使用物理模型来描述光在黑洞周围的传播
   • 通过反演观测数据来重建图像

   正则化的作用

   • 观测数据非常稀疏且噪声大
   • 需要正则化来稳定反演过程
   • 利用先验知识（如图像的平滑性、稀疏性）来约束解

   优化问题

   黑洞成像可以表述为：

   $$\min \quad \|A x - b\|_2^2 + \lambda R(x)$$

   其中：

   • $A$ 是物理模型算子（描述光传播）
   • $b$ 是观测数据
   • $R(x)$ 是正则化项（如总变分、稀疏性等）
   • $\lambda$ 是正则化参数

   挑战

   • 数据极其稀疏（只有少数几个观测站）
   • 噪声水平高
   • 需要结合多个物理约束
   • 计算复杂度高

4. 正则化的理论解释

   贝叶斯解释

   正则化可以解释为最大后验概率（MAP）估计：

   • 数据拟合项 $\|Ax - b\|_2^2$ 对应似然函数
   • 正则化项 $\lambda \|Lx\|_2^2$ 对应先验分布
   • 正则化参数 $\lambda$ 控制先验的强度

   偏差-方差权衡

   正则化通过引入偏差来减少方差：

   • 无正则化：低偏差，高方差（过拟合）
   • 适度正则化：偏差和方差的平衡（最佳泛化）
   • 过度正则化：高偏差，低方差（欠拟合）

   泛化误差

   正则化通过控制模型复杂度来改善泛化误差：

   • 减少模型对训练数据的过度拟合
   • 提高模型在测试数据上的表现

5. 正则化参数的选择

   交叉验证

   • 使用 $k$-折交叉验证选择最优的 $\lambda$
   • 在验证集上评估不同 $\lambda$ 值的性能

   L-曲线方法

   • 绘制数据拟合项与正则化项的关系曲线
   • 选择曲线拐点处的 $\lambda$

   广义交叉验证（GCV）

   • 基于留一交叉验证的近似方法
   • 计算效率高

6. 正则化的应用领域

   • 信号处理：去噪、反卷积、超分辨率
   • 图像处理：图像重建、去模糊、修复
   • 机器学习：防止过拟合、特征选择
   • 逆问题：医学成像、地球物理反演
   • 优化：稳定数值解、加速收敛