附录B 重要推导与证明补充 (Mathematical Derivations & Proofs)

前言： 很多算法在论文中直接给出了迭代公式（Update Rules），这让初学者常常感到“知其然不知其所以然”。 本附录旨在揭开这些公式背后的“黑盒”，展示它们是如何通过凸分析、KKT 条件和代数变换一步步推导出来的。掌握这些推导模板，你将具备修改经典模型以适应特定工程需求的能力。

1. 基础构件：Fenchel 对偶与共轭函数

Fenchel 对偶是现代图像处理算法（特别是 Chambolle-Pock 和 Split Bregman）的理论基石。

1.1 共轭函数的几何推导

定义函数 $f(x)$ 的共轭为 $f^*(y) = \sup_x (\langle x, y \rangle - f(x))$。 让我们推导几个图像处理中最核心的共轭对。

案例 A：$\ell_1$ 范数 (Total Variation 的基础)

设 $f(x) = |x|_1 = \sum |x_i|$。 $$ f^*(y) = \sup_x \sum_i (x_i y_i - |x_i|) $$ 由于求和符号可分离，我们只需看一维情况：$\sup_t (ty - |t|)$。

  • 若 $|y| > 1$（例如 $y=2$）：取 $t \to \infty$，则 $2t - t = t \to \infty$，上界为 $+\infty$。
  • 若 $|y| \le 1$：$ty - |t| \le |t||y| - |t| \le |t| - |t| = 0$。当 $t=0$ 时取到最大值 0。

结论：$\ell_1$ 的共轭是 $\ell_\infty$ 单位球的指示函数： $$ (\ell_1)^*(y) = \delta_{B_\infty}(y) = \begin{cases} 0 & \text{if } |y|_\infty \le 1 \\ +\infty & \text{otherwise} \end{cases} $$

直觉：这解释了为什么 TV 去噪的对偶算法总是包含一个 $y \leftarrow y / \max(1, |y|)$ 的投影步骤。

案例 B：二次函数 (Tikhonov / 高斯先验)

设 $f(x) = \frac{1}{2}|x|_2^2$。 $$ f^*(y) = \sup_x (\langle x, y \rangle - \frac{1}{2}|x|^2) $$ 这是一个对 $x$ 的凹函数，求导令梯度为 0：$y - x = 0 \implies x^* = y$。 代回原式：$\langle y, y \rangle - \frac{1}{2}|y|^2 = \frac{1}{2}|y|^2$。 结论：自共轭，$f^*(y) = \frac{1}{2}|y|_2^2$。

2. 近端算子 (Proximal Operator) 的推导

近端算子 $\text{prox}_{\lambda f}(v) = \arg\min_x \frac{1}{2}|x-v|^2 + \lambda f(x)$ 是分裂算法（ADMM, ISTA）的每一步核心。

2.1 软阈值 (Soft Thresholding) 的由来

目标：解 $\min_x \frac{1}{2}(x-v)^2 + \lambda |x|$。 这是一个凸问题，0 包含在次微分中： $$ 0 \in x - v + \lambda \partial |x| \implies v - x \in \lambda \cdot \text{sign}(x) $$ 分情况讨论（基于 $v$ 的值）：

  1. $v > \lambda$：假设 $x > 0$，则 $v - x = \lambda \implies x = v - \lambda$。由于 $v > \lambda$，确实 $x>0$，假设成立。
  2. $v < -\lambda$：假设 $x < 0$，则 $v - x = -\lambda \implies x = v + \lambda$。假设成立。
  3. $|v| \le \lambda$：假设 $x = 0$，次微分区间为 $[-\lambda, \lambda]$。若 $v \in [-\lambda, \lambda]$，则 $v-0 = v$ 确实落在次微分区间内。解为 $x=0$。

结论：合并上述三种情况，即得到软阈值算子 $\mathcal{S}_\lambda(v)$。

      Output x
        /
       / slope=1
______/
 -L  /| L    <-- Input v (L = lambda)
    /
   /
  /

2.2 奇异值阈值 (SVT) 与核范数

问题：低秩矩阵恢复（Robust PCA）需要解 $\min_X \frac{1}{2}|X-Y|_F^2 + \lambda |X|_*$。 推导： 利用 Von Neumann 迹不等式：$\langle X, Y \rangle \le \sum \sigma_i(X) \sigma_i(Y)$，当且仅当 $X, Y$ 拥有相同的奇异向量时取等号。 由于 Frobenius 范数仅依赖于奇异值（$|X|_F^2 = \sum \sigma_i^2$），且核范数也仅依赖于奇异值（$|X|_* = \sum \sigma_i$）。 我们可以将问题在 SVD 域内解耦： 令 $Y = U \Sigma_Y V^T$。此时最优的 $X$ 必有形式 $X = U \Sigma_X V^T$（共享奇异向量）。 问题退化为对角线上标量的优化： $$ \min_{\sigma_i(X)} \sum_i \left( \frac{1}{2}(\sigma_i(X) - \sigma_i(Y))^2 + \lambda \sigma_i(X) \right) \quad \text{s.t. } \sigma_i(X) \ge 0 $$ 这正是上面的 $\ell_1$ 近端问题（加上非负约束）。 结论：对 $Y$ 做 SVD，对奇异值做软阈值，再重组。

3. ADMM 与 Split Bregman 的深层联系

3.1 增广拉格朗日乘子法 (ALM) 的推导

对于约束问题 $\min f(x) + g(z) \text{ s.t. } Ax + Bz = c$。 构造增广拉格朗日函数： $$ \mathcal{L}_\rho(x,z,u) = f(x) + g(z) + \langle u, Ax+Bz-c \rangle + \frac{\rho}{2}|Ax+Bz-c|^2 $$ ADMM 只是简单地交替最小化 $\mathcal{L}_\rho$：

  1. $x \leftarrow \arg\min_x \mathcal{L}_\rho(x, z, u)$
  2. $z \leftarrow \arg\min_z \mathcal{L}_\rho(x, z, u)$
  3. $u \leftarrow u + \rho(Ax+Bz-c)$ （这是梯度上升更新对偶变量）

3.2 Split Bregman 即为 ADMM

Split Bregman 迭代常用于解 $\min |x|_1 + \frac{\mu}{2}|Ax-f|^2$。 引入变量替换 $d = x$，约束 $d=x$？不，通常令 $d = \nabla u$ 来解 TV。 让我们看标准形式： Split Bregman 形式： $$ \begin{cases} x^{k+1} = \arg\min_x \dots + \frac{\lambda}{2}|d^k - x - b^k|^2 \\ d^{k+1} = \text{soft}(x^{k+1}+b^k, 1/\lambda) \\ b^{k+1} = b^k + x^{k+1} - d^{k+1} \end{cases} $$ ADMM 形式（令 $u$ 为缩放的对偶变量 $u_{admm} = \rho b$）： $$ u_{admm}^{k+1} = u_{admm}^k + \rho(x^{k+1} - d^{k+1}) $$ 对比可见，Split Bregman 中的 $b$ 实际上就是 ADMM 中的缩放对偶变量 (Scaled Dual Variable)。 两者在数学上是完全等价的。Split Bregman 只是 Goldstein 和 Osher 在 Bregman 迭代框架下独立发现的 ADMM 的一种特定应用形式。

4. 为什么 IRLS 和 MM 有效？(Majorization-Minimization)

非凸优化中，我们经常用 $\ell_2$ 来逼近 $\ell_p (0<p<1)$。推导其不等式基础。

4.1 凹函数的切线不等式

对于 $0 < p \le 1$，函数 $h(t) = t^{p/2}$ 是关于 $t \in [0, \infty)$ 的凹函数。 根据凹函数性质，其图像位于切线下方： $$ h(t) \le h(t_0) + h'(t_0)(t - t_0) $$ 令 $t = u^2$（这里 $u$ 代表像素值或梯度模长），$t_0 = (u^k)^2$。 $$ (u^2)^{p/2} \le |u^k|^p + \frac{p}{2}(u^k)^{p-2} (u^2 - (u^k)^2) $$ 忽略常数项，我们要最小化 $|u|^p$ 的上界，等价于最小化： $$ \frac{p}{2} \frac{u^2}{|u^k|^{2-p}} $$ 这就是迭代重加权最小二乘 (IRLS) 的权重来源：$w = |u^k|^{p-2}$。 当 $p=1$ (TV) 时，权重为 $1/|u^k|$。

Gotcha: 上述推导在 $u^k=0$ 时导数不存在。这就是为什么代码里必须写 1 / sqrt(u^2 + epsilon)。

5. 半正定规划 (SDP) 松弛的直觉

在第14章中，我们将二值/组合问题松弛为 SDP。 案例：Max-Cut 或 二值分割 原问题：$\min x^T Q x$ s.t. $x_i \in \{-1, 1\}$。 这很难解（NP-hard）。 变换： 令 $X = xx^T$。

  1. $X$ 是秩为 1 的矩阵。
  2. $X \succeq 0$ (半正定)。
  3. $X_{ii} = x_i x_i = 1$。 原问题变为：$\min \text{Tr}(QX)$ s.t. $X_{ii}=1, X \succeq 0, \text{rank}(X)=1$。 松弛： 去掉最难的非凸约束 $\text{rank}(X)=1$。 变为：$\min \text{Tr}(QX)$ s.t. $X_{ii}=1, X \succeq 0$。 这是一个标准的凸 SDP 问题，可以用内点法求解。解出 $X$ 后，通过特征值分解取最大特征向量，即可近似还原 $x$。

6. 参数选择的统计学推导 (Bayesian Interpretation)

为什么去噪模型中 $\lambda \propto 1/\sigma^2$？

MAP 估计： $$ \hat{x} = \arg\max_x P(x|y) = \arg\max_x P(y|x)P(x) $$ 取对数： $$ \hat{x} = \arg\min_x -\log P(y|x) - \log P(x) $$

  1. 似然项 $P(y|x)$：假设加性高斯白噪声 $n \sim N(0, \sigma^2I)$。 $$ P(y|x) \propto \exp\left( -\frac{|Ax-y|^2}{2\sigma^2} \right) \implies -\log P \approx \frac{1}{2\sigma^2}|Ax-y|^2 $$

  2. 先验项 $P(x)$：假设图像梯度服从拉普拉斯分布（稀疏性）$P(x) \propto \exp(-\beta |\nabla x|_1)$。 $$ -\log P \approx \beta |\nabla x|_1 $$ 合并目标函数： $$ \min \frac{1}{2\sigma^2}|Ax-y|^2 + \beta |\nabla x|_1 $$ 同乘 $\sigma^2$： $$ \min \frac{1}{2}|Ax-y|^2 + (\beta \sigma^2) |\nabla x|_1 $$ 结论：正则化参数 $\lambda = \beta \sigma^2$。即噪声越大 ($\sigma$ 大)，$\lambda$ 应该越大；先验越强 ($\beta$ 大)，$\lambda$ 应该越大。

7. 练习题 (Derivation Exercises)

习题 B.1：L2-L0 问题的解析解

题目：证明单变量问题 $\min_x \frac{1}{2}(x-y)^2 + \lambda |x|_0$ 的解是“硬阈值”算子（Hard Thresholding）。 提示：分别比较 $x=0$ 和 $x \ne 0$ 时的能量值。

答案提示： 若 $x=0$，能量 $E_0 = \frac{1}{2}y^2$。 若 $x \ne 0$，正则项为 $\lambda$。此时为使数据项最小，必有 $x=y$，能量 $E_1 = \lambda$。 比较 $E_0$ 和 $E_1$：当 $\frac{1}{2}y^2 > \lambda \implies |y| > \sqrt{2\lambda}$ 时，选 $x=y$；否则选 $x=0$。 这就是 Hard Thresholding，阈值为 $\sqrt{2\lambda}$。

习题 B.2：Sylvester 方程在 ADMM 中的出现

题目：在使用 ADMM 求解去模糊（Deconvolution）时，x-update 步通常形如 $\min_x \frac{1}{2}|Ax-y|^2 + \frac{\rho}{2}|x - z + u|^2$。证明当 $A$ 为循环矩阵（卷积）时，该问题可通过 FFT 快速求解；若 $A$ 不是循环矩阵，这对应什么线性方程？

答案提示： 求导得正规方程：$(A^TA + \rho I)x = A^Ty + \rho(z-u)$。 若 $A$ 是卷积，在频域对角化：$F A^T A F^H = |\hat{k}|^2$（对角阵）。可以直接做逐点除法（Element-wise division）。 即 $\hat{x} = \frac{\overline{\hat{k}}\hat{y} + \rho(\hat{z}-\hat{u})}{|\hat{k}|^2 + \rho}$。这是 Wiener 滤波的形式。

习题 B.3：NMF 乘法更新规则的推导

题目：对于 NMF 目标 $|V - WH|_F^2$，利用梯度下降 $H_{t+1} = H_t - \eta \nabla_H$，并令学习率 $\eta$ 为特殊的“自适应”形式，推导 Lee & Seung 的乘法更新规则。

答案提示： 梯度 $\nabla_H = W^T(WH - V) = W^TWH - W^TV$。 令自适应步长 $\eta_{ij} = \frac{H_{ij}}{(W^TWH)_{ij}}$。 代入更新公式： $H \leftarrow H - \frac{H}{W^TWH} \odot (W^TWH - W^TV) = H - H + H \odot \frac{W^TV}{W^TWH} = H \odot \frac{W^TV}{W^TWH}$。 这就得到了著名的乘法更新公式，保证非负性自然保持（只要初始非负）。

8. 常见陷阱与调试指南 (Math-to-Code Gotchas)

8.1 对偶间隙 (Duality Gap) 的误解

  • 理论：原始问题值 $\ge$ 对偶问题值。最优时相等。
  • 陷阱：在迭代初期，计算出的 Gap 可能是负的？
  • 原因：你计算的“对偶变量”可能还没有投影回可行域（例如 TV 的对偶变量必须满足 $|p|_\infty \le 1$）。如果你用未投影的变量算对偶能量，那个公式是无效的。
  • Fix：计算 Gap 前，务必确保变量满足约束。

8.2 矩阵求逆引理 (Woodbury Identity)

  • 场景：稀疏编码中常遇到 $(I + D^TD)^{-1}$ 或 $(I + DD^T)^{-1}$。
  • 陷阱：直接求逆是 $O(N^3)$。
  • 技巧：如果 $D$ 是“胖”的（原子数多于维度）或“瘦”的，利用 Woodbury 恒等式将求逆转换到维度较小的那一侧。 $$ (I + UV^T)^{-1} = I - U(I + V^TU)^{-1}V^T $$ 这在字典学习和 RPCA 求解中能带来 10-100 倍的加速。

8.3 为什么我的 ADMM 不收敛？

  • 检查 1：你是否正确缩放了对偶变量？标准形式是 $u = (1/\rho) \cdot \text{LagrangeMultiplier}$。如果你混用了两种形式，更新公式会差一个 $\rho$ 因子。
  • 检查 2：子问题求解是否精确？ADMM 容忍子问题求解有误差，但如果误差太大（例如 Conjugate Gradient 步数太少），外层循环可能震荡。
  • 检查 3：非凸陷阱。如果你用 ADMM 解 SCAD 或 $\ell_0$，且 $\rho$ 选取不当，算法可能陷入循环震荡。尝试逐渐增大 $\rho$ (Continuation)。