学习目标：
- 超越微积分：理解为何图像处理核心模型（TV, $\ell_1$）不可导，并掌握次梯度（Subgradient）这一工具。
- 变换的艺术：像傅里叶变换处理卷积一样，掌握Fenchel 共轭如何将“复杂的非光滑项”转化为“简单的约束项”。
- 算法积木：深入理解近端算子（Proximal Operator）的物理含义与计算规则，它是搭建 ISTA, ADMM, Primal-Dual 算法的核心原子。
- 对偶桥梁：熟练运用 Moreau 分解，在原始空间和对偶空间之间自由切换，找到求解的捷径。
在经典的图像处理（如高斯滤波、维纳滤波）中，我们处理的是线性算子和二次函数（Least Squares）。这些问题闭式解存在，且处处可导。
然而，现代图像复原（Image Restoration）的统治级模型通常具有以下特征：
传统的 $\nabla f(x) = 0$ 失效了。我们需要一套处理“广义导数”和“集合映射”的数学语言，这就是凸分析。本章将为您提供后续章节（ADMM, Primal-Dual）所需的所有数学武器。
如果集合 $C$ 中任意两点 $x, y$ 的连线都完全包含在 $C$ 中，即 $\theta x + (1-\theta)y \in C, \forall \theta \in [0,1]$，则称 $C$ 为凸集。
ASCII 直觉图：
(凸集) (非凸集)
___________ ___________
/ . \ / . \
/ / \ \ / / \ \
| x---y | | x y |
\ / \ \___/ / <-- 连线穿过了外部
\___________/ \___________/
成像中的凸集：
非负象限：${x x_i \ge 0}$（NMF 的基础）
$\ell_2$ 球：${x |x|_2 \le \epsilon}$（噪声约束）
半正定锥：${X X \succeq 0}$（SDP, 矩阵补全）
Rule of Thumb (收敛速度)：
- 优化普通凸函数，收敛速度通常是 $O(1/k)$ 或 $O(1/\sqrt{k})$。
- 优化强凸函数，收敛速度通常是线性的 $O(c^k)$（即对数坐标下的直线）。
- 这就是为什么我们在工程中有时会人为加上 $\frac{\epsilon}{2}|x|^2$ 这一项（Elastic Net），用微小的偏差换取指数级的收敛速度。
| 对于光滑函数，梯度是唯一的切线斜率。对于非光滑函数（如 $ | x | $ 在 0 处），可能存在无数条直线“支撑”在函数下方。 |
向量 $g \in \mathbb{R}^n$ 被称为凸函数 $f$ 在点 $x$ 处的次梯度，如果满足： \(f(z) \ge f(x) + \langle g, z-x \rangle, \quad \forall z\) 所有次梯度的集合称为次微分 (Subdifferential)，记为 $\partial f(x)$。
对于 $f(x) = |x|$（一维）： \(\partial |x| = \begin{cases} \{1\} & x > 0 \\ \{-1\} & x < 0 \\ [-1, 1] & x = 0 \quad (\text{核心：这里是一个区间}) \end{cases}\)
ASCII 直觉图：次梯度的几何意义
f(z) = |z|
\ /
\ /
\ / <-- 尖点 x=0
------*------
/ / | \ \
/ / | \ \
g=-1 g=-0.5 g=1
在 x=0 处，斜率为 -1 到 1 之间的任何直线，
都位于函数图像的下方（支撑线）。
这是变分法中最核心的条件。$x^*$ 是凸函数 $f(x)$ 全局极小值点的充要条件是： \(0 \in \partial f(x^*)\)
物理直觉：如果不光滑点包含 0 斜率，那么它就是谷底。例如 $ x $ 在 0 处，次微分 $[-1, 1]$ 包含 0，所以 0 是最小值。
在傅里叶变换中，时域的卷积等于频域的乘积。在凸分析中，我们有类似的对偶变换，称为 Fenchel-Legendre 变换。
函数 $f(x)$ 的共轭函数 $f^*(y)$ 定义为： \(f^*(y) = \sup_{x} \left( \langle y, x \rangle - f(x) \right)\)
几何意义：给定斜率 $y$，寻找一个超平面 $\langle y, x \rangle - b$，使其刚好接触 $f(x)$ 的图像，此时的最大截距 $b$ 就是 $f^*(y)$。
| 原函数 $f(x)$ | 共轭函数 $f^*(y)$ | 备注 |
|---|---|---|
| $\frac{1}{2}|x|_2^2$ | $\frac{1}{2}|y|_2^2$ | 自共轭，二次函数的对偶还是二次 |
| $|x|_1$ | $\delta_{B_\infty}(y)$ | $\ell_1$ 的对偶是 $\ell_\infty$ 球的指示函数 |
| $|x|_2$ | $\delta_{B_2}(y)$ | $\ell_2$ 的对偶是 $\ell_2$ 球的指示函数 |
| $\delta_C(x)$ | $\sigma_C(y) = \sup_{x \in C} \langle y, x \rangle$ | 指示函数的对偶是支撑函数 |
| $ax + b$ | $\delta_{{a}}(y) - b$ | 线性函数的对偶是指示函数 |
深入理解：为什么 $\ell_1$ 的对偶是 Box 约束？ $\ell_1$ 正则化倾向于产生稀疏解（推向 0），其对偶问题则是将对偶变量“裁剪”到 $[-1, 1]$ 之间。这种投影操作往往比处理稀疏性更容易计算。这正是 Split Bregman 和 Primal-Dual 算法高效的原因。
在非光滑优化中，我们无法计算梯度，也不能直接令导数为 0。我们退而求其次，寻找一个“既能降低函数值，又不离当前点太远”的新点。
\(\text{prox}_{\lambda f}(v) = \arg\min_x \left( f(x) + \frac{1}{2\lambda}\|x - v\|_2^2 \right)\) 或者等价地写成（更常见的形式）： \(\text{prox}_{\tau f}(v) = \arg\min_x \left( \frac{1}{2}\|x - v\|_2^2 + \tau f(x) \right)\)
1. 软阈值 (Soft Thresholding) —— $\ell_1$ 范数
\(f(x) = \lambda \|x\|_1 \implies [\text{prox}_{f}(v)]_i = \text{sign}(v_i)\max(|v_i| - \lambda, 0)\)
代码实现常写作 shrink(v, lambda)。这是小波去噪、Lasso、压缩感知的核心。
2. 投影 (Projection) —— 指示函数
\(f(x) = \delta_C(x) \implies \text{prox}_f(v) = \text{proj}_C(v) = \arg\min_{x \in C} \|x-v\|^2\)
如果 $C$ 是非负象限，则投影就是 max(v, 0)。
3. 线性收缩 —— 二次函数 \(f(x) = \frac{\lambda}{2}\|x\|^2 \implies \text{prox}_f(v) = \frac{v}{1+\lambda}\) Tikhonov 正则化的 Prox 只是简单的缩放。
这是本章的杀手锏。它像线性代数中的“正交分解”一样，联系了原空间和对偶空间。
对于任意凸函数 $f$，适当的 $\lambda > 0$ 和向量 $v$，有： \(v = \text{prox}_{\lambda f}(v) + \lambda \text{prox}_{f^*/\lambda}(v/\lambda)\)
求解全变分去噪（ROF 模型）的 Prox： \(\min_x \frac{1}{2}\|x-v\|^2 + \lambda \text{TV}(x)\) 直接求 $\text{prox}_{\text{TV}}$ 非常困难，因为 TV 项不可分且不可导。
利用 Moreau 分解的思路：
结论：很多时候，求解“去噪”问题（Prox）等价于求解其对偶的“投影”问题，然后再用原信号减去残差。
在第6章（PGD/FISTA）中，我们将处理 $F(x) = f(x) + g(x)$，其中 $f$ 光滑，$g$ 非光滑。
函数 $f$ 的梯度是 $L$-Lipschitz 连续的，意味着梯度的变化速度有上限： \(\|\nabla f(x) - \nabla f(y)\| \le L \|x - y\|, \quad \forall x, y\) 其中 $L$ 称为 Lipschitz 常数。对于二次函数 $f(x) = \frac{1}{2}|Ax-y|^2$，其 $L = |A|^2_{op}$（$A$ 的最大奇异值的平方）。
它是步长（Step Size）的交警。
Hint: 在不可导点，次微分是左导数和右导数构成的区间。
Hint: 计算其一阶导数，看是否连续且斜率有限。
Hint: 问题可对每个组分离求解。这实际上是 Block Soft Thresholding：$x_g \leftarrow x_g \cdot \max(0, 1 - \lambda/|x_g|_2)$。
Hint: 利用酉不变性质，将矩阵问题转化为对角线向量的 $\ell_1$ 问题。
| 错误：试图通过加一个小量 $\epsilon$ 把 $ | x | $ 平滑成 $\sqrt{x^2+\epsilon}$ 来用传统梯度下降。 |