快速迭代收缩阈值算法 FISTA 原理与实现

1. 数学与优化基础

在许多信号处理与机器学习问题中，我们希望获得稀疏解，即解向量中非零元素很少。直接以 L0'范数'（非零元素个数）作为稀疏性度量会导致非凸优化难题。一个常用的替代是采用 L1 范数（||x||_1 是各元素绝对值之和）作为正则项，它是 L0 的凸松弛，可以鼓励稀疏解。与 L2 正则化不同，L1 正则化对小系数给予恒定的惩罚减少，这使得较小的系数更容易被压缩到 0，从而产生稀疏性。简言之，L1 范数由于在零点处的尖锐拐角（梯度不连续）会诱导解的许多分量为零。

假设你有 5 个箱子，里面分别放了 x_1, x_2, x_3, x_4, x_5 个苹果。L0'范数'就是这 5 个箱子里有苹果的箱子的数量。若 x_2 = 0, x_4 = 0，其它 3 个箱子里苹果不为 0，那么 L0'范数'就是 3。想要让 L0 变小，就要'尽量让更多箱子变成空箱子'，从而达到稀疏 (空箱子越多，非零元素越少)。L0'范数'本身是不连续、不光滑的 (要么 0，要么 1)，在数学优化中很难直接求解 (优化过程不易'沿着梯度'慢慢变化，一下跳零一下跳非零)。这会导致'最小化 L0'时比较棘手。

L1 范数是一个凸函数，有很好处理的数学性质 (可以使用梯度或次梯度等优化算法)。虽然它并不会像 L0 一样'明确地'只算非零数量，但在最小化 L1 范数时，有很多解会自动出现'某些元素被压到正好为 0'——这就是所谓的'稀疏解'。依然用'箱子'来打比方。L1 范数就是把每个箱子里的苹果数量 (绝对值) 加起来之和，努力让这个总和尽量小。当某个箱子里的苹果数量比较小，L1 优化就会倾向于'干脆把这个箱子的苹果数量压到 0'，以进一步降低总和。于是就会出现类似 L0 的'有些箱子空了'的效果 (稀疏解)。

L2 范数是各元素平方和的开方，即 ||x||_2 = sqrt(x_1^2 + x_2^2 + ... + x_n^2)。它可以让解趋向于'总体较小'，但不会把任何一维直接压到完全 0。若还以箱子比方，L2 更像是在'平均地'减小每个箱子的苹果数量，而不会直接把其中某些箱子砍到空箱。

典型例子包括LASSO（最小绝对收缩选择算子）和**基础追踪（Basis Pursuit）**等，它们通过在最小二乘误差目标后加上 L1 范数惩罚来实现稀疏信号的估计。这种 L1 正则化问题属于凸优化，通常可转化为线性规划或二阶锥规划来求解。例如，有噪声情况下的基础追踪去噪（BPDN）和 LASSO 都考虑求解形如 min_x 1/2 ||Ax - b||_2^2 + lambda ||x||_1, 的凸问题，其中 lambda 为权衡稀疏度的正则化参数。

像上面这样的目标函数 F(x) = f(x) + g(x) 中，f(x) = 1/2 ||Ax - b||_2^2 是光滑凸函数，具有 Lipschitz 连续的梯度，而 g(x) = lambda ||x||_1 是连续凸函数但在 0 点不可微。

凸函数的一个重要性质是局部极小即全局极小，这为设计算法提供了可靠性保障。

梯度下降法是求解光滑凸优化的基本一阶方法：反复沿负梯度方向迭代。对于二次损失这样的 f(x)，梯度为 grad f(x) = A^T(Ax - b)，直接的梯度迭代为 x <- x - eta grad f(x)。然而，当存在非光滑项 g(x) 时（例如 L1 正则化），我们不能简单对其求梯度，而需借助次梯度或近端算法。

近端梯度（Proximal Gradient）方法通过引入近端算子来处理非光滑项，每步对光滑部分做梯度更新后，对非光滑部分应用一个近端映射 (即求解一个带 L2 范数惩罚的最优问题)。对于 L1 项，其近端映射就是**软阈值（soft-thresholding）**操作，其公式为： prox_{lambda ||cdot||_1}(v_i) = { 0, & |v_i| <= lambda, v_i - lambda sign(v_i), & |v_i| > lambda ~, } 即将向量 v 中每个分量按上述规则收缩。软阈值操作也通常写为 S_lambda(v) = sign(v) * max(|v| - lambda, 0)，把绝对值低于阈值 lambda 的系数设为 0，其余系数减小 lambda。软阈值是 L1 非光滑项的近端，因为它正是最小化 1/2 ||x-v||_2^2 + lambda ||x||_1 所得的解。这个操作在稀疏信号重建中可视为一种'去噪'步骤：减小信号中的小幅成分，同时保留/突出大幅成分，从而促进稀疏性。

2. FISTA 算法的原理、推导与机制

在引入 FISTA 前，先看其基础算法——迭代收缩阈值算法 (ISTA)。ISTA 是一种近端梯度下降方法，每次迭代包括一个梯度下降步骤和一个近端（软阈值）步骤。对目标 F(x) = f(x) + g(x)，给定梯度 Lipschitz 常数为 L，ISTA 的每步更新可表示为：

• 梯度步： y_k = x_{k-1} - 1/L grad f(x_{k-1})，即从上一步解 x_{k-1} 沿负梯度方向前进一步长度 1/L。
• 近端步： x_k = prox_{1/L g}(y_k)，即对 y_k 应用非光滑项 g 的近端算子。如果 g(x) = lambda ||x||{lambda/L}(y_k)。