第6章 一阶优化与近端梯度：ISTA/FISTA 与变体

本章摘要：
图像处理中的变分模型通常由“光滑的数据项”和“非光滑的正则项”组成。传统的梯度下降法无法处理非光滑项，而次梯度法收敛太慢。本章将介绍近端梯度法（Proximal Gradient Descent, PGD），这是一种将“梯度下降”与“投影/阈值化”结合的优雅框架。我们将深入探讨其核心实例 ISTA，以及通过 Nesterov 动量加速的 FISTA，最后介绍在工程实践中必不可少的回溯线搜索与重启策略。

6.1 引言：克服非光滑性的障碍

在前面的章节中，我们建立了如下形式的通用变分模型： $$ \min_x F(x) \equiv f(x) + g(x) $$

• $f(x)$：光滑凸函数，梯度 $\nabla f$ 满足 Lipschitz 连续条件。
  • 例子：最小二乘数据保真项 $\frac{1}{2}|Ax-y|_2^2$。
• $g(x)$：非光滑（Non-smooth）凸函数，通常是“简单的”。
  • 例子：L1 稀疏正则 $\lambda|x|_1$，全变分（TV）正则，或指示函数 $\iota_C(x)$。

6.1.1 为什么标准梯度下降失效？

如果直接应用梯度下降 $x_{k+1} = x_k - \alpha \nabla F(x_k)$，我们在计算 $\nabla g(x)$ 时会遇到麻烦：$g(x)$ 在关键位置（如稀疏解的零点）不可导。

虽然可以使用次梯度法（Subgradient Method），但其收敛速率仅为 $O(1/\sqrt{k})$。对于百万像素级的图像重建，这意味着需要数万次迭代才能消除伪影，效率不可接受。

6.1.2 拆解策略

近端梯度法的核心哲学是“分而治之”：

1. 利用 $\nabla f(x)$ 处理光滑部分的信息。
2. 利用 Proximal Operator（近端算子） 处理非光滑部分的结构。

6.2 近端梯度法（PGD）：理论与直觉

6.2.1 二次极大化视角（Quadratic Majorization）

要理解 PGD，最好的方式是看它如何近似目标函数。在点 $x_k$ 处，我们在 $f(x)$ 处做一个二次近似（泰勒展开并在二次项中用 Lipschitz 常数 $L$ 放大），并保持 $g(x)$ 不变： $$ Q_L(x, x_k) = \underbrace{f(x_k) + \langle \nabla f(x_k), x - x_k \rangle + \frac{L}{2}|x - x_k|_2^2}_{\text{f(x) 的二次上界}} + \ g(x) $$ PGD 的每一步，实际上是在最小化这个代理函数 $Q_L(x, x_k)$： $$ x_{k+1} = \arg\min_x Q_L(x, x_k) $$ 通过配方和整理，上述最小化问题等价于： $$ x_{k+1} = \arg\min_x \frac{L}{2} \left| x - \left( x_k - \frac{1}{L}\nabla f(x_k) \right) \right|_2^2 + g(x) $$ 这正是近端算子的定义！

6.2.2 核心迭代格式

令步长 $\alpha = 1/L$，PGD 迭代如下： $$ x_{k+1} = \text{prox}_{\alpha g} \underbrace{\left( x_k - \alpha \nabla f(x_k) \right)}_{\text{前向步 (Forward)}} $$

1. 前向步：沿着数据保真项的梯度走一步，试图降低重构误差。
2. 后向步：通过近端算子，将解“拉回”到符合正则化约束（如稀疏、分段平滑）的流形上。

6.3 ISTA：迭代收缩阈值算法

当 $f(x) = \frac{1}{2}|Ax-y|_2^2$，$g(x) = \lambda |x|_1$ 时，PGD 就特化为 ISTA。这是稀疏编码和压缩感知中最基础的算法。

6.3.1 软阈值算子 (Soft Thresholding)

L1 范数的近端算子有一个封闭解，称为软阈值算子 $\mathcal{S}_{\tau}(u)$： $$ [\text{prox}_{\tau |\cdot|_1}(u)]_i = \mathcal{S}_{\tau}(u_i) = \text{sign}(u_i) \cdot \max(|u_i| - \tau, 0) $$ ASCII 图示：软阈值函数

      Output S_τ(u)
        ^
      / |
     /  |
    /   |
---/----+----/----> Input u
 -τ    0    τ

注：$[-\tau, \tau]$ 之间的输入全部被置零，这就是“稀疏性”的来源。

6.3.2 ISTA 完整步骤

1. 输入：观测 $y$，算子 $A$，正则参数 $\lambda$，步长 $\alpha$。
2. 迭代 $k=1, 2, \dots$：
   • 计算残差梯度：$d_k = A^T(Ax_k - y)$
   • 梯度更新：$z_k = x_k - \alpha d_k$
   • 软阈值：$x_{k+1} = \mathcal{S}_{\alpha \lambda}(z_k)$
3. 停止：当相对误差 $|x_{k+1}-x_k| / |x_k| < \epsilon$。

6.3.3 收敛性分析

ISTA 的收敛速率是 $O(1/k)$。

• 物理意义：虽然它一定能收敛到全局最优解，但非常慢。对于病态问题（$A$ 的条件数很大），ISTA 往往在最初几次迭代快速降低误差，随后陷入漫长的“长尾”收敛，解的变化极其微小。

6.4 FISTA：加速的 ISTA (Nesterov 动量)

为了解决 ISTA 慢的问题，Beck 和 Teboulle (2009) 将 Nesterov 的最优一阶方法引入 PGD，提出了 FISTA (Fast ISTA)。

6.4.1 核心思想：惯性与外推

FISTA 不在当前的 $x_k$ 处计算梯度，而是在一个“预测点”（或称外推点） $y_k$ 处计算。这个 $y_k$ 是 $x_k$ 和 $x_{k-1}$ 的线性组合。

直觉：如果算法在前几步一直向某个方向移动，那么很可能下一步还在那个方向。动量项利用了这个历史信息。

6.4.2 FISTA 算法流程

初始化 $x_0 = x_{-1} = 0$，动量参数 $t_0 = 1$。 在第 $k$ 步 ($k \ge 0$)：

1. 外推 (Extrapolation)： $$ y_k = x_k + \frac{t_k - 1}{t_{k+1}} (x_k - x_{k-1}) $$ 注：$\frac{t_k - 1}{t_{k+1}}$ 是动量系数，随着 $k$ 增加，它从 0 逐渐趋近于 1。

2. 梯度与近端 (Proximal Step on $y_k$)： $$ x_{k+1} = \text{prox}_{\alpha g} \left( y_k - \alpha \nabla f(y_k) \right) $$

3. 更新动量参数： $$ t_{k+1} = \frac{1 + \sqrt{1 + 4t_k^2}}{2} $$

6.4.3 性能对比

• 收敛率：$O(1/k^2)$。
• 代价：每步计算量几乎与 ISTA 相同（仅多了简单的向量加法），但迭代次数大幅减少。

ASCII 轨迹对比

等高线图 (Contour Map)
----------------------
      /   \
     /  *  \    <-- 最优解
    | ISTA  |   ISTA: 像醉汉一样沿着梯度线垂直方向“之”字形前进
     \     /
      \   /

      /   \
     /  *  \    <-- 最优解
    | FISTA |   FISTA: 利用惯性冲过弯道，轨迹更直，但也可能超调(overshoot)
     \     /
      \ /

6.5 实用工程策略：让算法更好用

在论文中，$L$（Lipschitz 常数）通常假设已知。但在实际工程（如盲反卷积或特定算子 MRI）中，计算 $L = \lambda_{\max}(A^TA)$ 很昂贵。

6.5.1 回溯线搜索 (Backtracking Line Search)

不要固定步长，而是自适应地寻找步长。我们寻找满足下降引理的步长 $\eta$。

算法步骤：

1. 设置初始步长 $\eta$（例如 1.0），缩放因子 $\beta \in (0, 1)$（例如 0.5）。
2. 在每一步迭代中：
   • 计算候选点 $z = \text{prox}_{\eta g}(x_k - \eta \nabla f(x_k))$。
   • 检查条件：$f(z) \le f(x_k) + \langle \nabla f(x_k), z - x_k \rangle + \frac{1}{2\eta}|z - x_k|_2^2$。
     • （直观解释：二次近似必须是 $f(z)$ 的上界）。
   • 如果条件不满足：$\eta \leftarrow \beta \eta$，重新计算 $z$。
   • 如果条件满足：接受 $x_{k+1} = z$，并可尝试在下一步略微增大 $\eta$。

Rule of Thumb：虽然线搜索增加了每步的计算成本（可能需要多次评估 $f$），但它保证了算法在任何数据下都不会发散，是工业级代码的标配。

6.5.2 重启 FISTA (Restarting FISTA)

FISTA 虽然快，但由于动量存在，它会在最优解附近产生“涟漪”（震荡）。这会导致目标函数值出现非单调的波折。

策略：当检测到动量把我们带向“错误方向”时，重置动量（令 $t_k = 1, x_{k-1} = x_k$）。 检测准则（常用）： $$ \langle y_k - x_{k+1}, x_{k+1} - x_k \rangle > 0 $$ 或者简单的：如果目标函数变大了，就重启。这通常能消除涟漪并进一步加速收敛。

6.6 常见陷阱与错误 (Gotchas)

1. 阈值参数缩放错误 (The Scaling Bug)

• 陷阱：在使用 prox 时，直接用 $\lambda$ 作为参数。
• 正确：$\text{prox}_{\alpha g}$ 的参数必须是 $\alpha \cdot \lambda$（步长 $\times$ 正则系数）。
• 原理：观察 $x_{k+1} = \arg\min \frac{1}{2\alpha}|x - z|^2 + \lambda |x|_1$，提取 $1/\alpha$ 后变为 $\frac{1}{2}|x-z|^2 + (\alpha\lambda)|x|_1$。
• 症状：如果步长很小，图像会变得非常黑或极度稀疏。

2. 算子伴随不匹配 (Adjoint Mismatch)

• 陷阱：你写了 A(x) (Forward) 和 At(y) (Adjoint)，但它们不是数学上的共轭转置。
  • 例如：卷积边界处理不一致（Forward 用零填充，At 用循环卷积）。
• 后果：PGD/FISTA 无法收敛，或者收敛到一个错误的解，误差曲线不再下降。
• 调试技巧 (Dot Product Test)： 生成随机向量 $u, v$，计算 $\langle A(u), v \rangle$ 和 $\langle u, At(v) \rangle$。两者必须在机器精度下相等（例如误差 < 1e-10）。

3. FISTA 的初始化

• 陷阱：$y_1$ 初始化错误。
• 建议：严格按照 $t_1=1, y_1=x_0$ 开始。

6.7 本章小结

| 特性 | 梯度下降 (GD) | ISTA | FISTA |

核心公式记忆： $$ x_{k+1} = \text{prox}_{\alpha g} ( x_k - \alpha \nabla f(x_k) ) $$ 这就这一章的全部精髓：梯度下降走一步，近端算子拉回来。

6.8 练习题

基础题

挑战题