Abstract
作者考虑了一类迭代收缩阈值算法（ISTA），用于解决信号/图像处理中出现的线性逆问题。
这类方法可以被视为经典梯度算法的拓展，由于其简单性而具有吸引力，因此即使使用密集的矩阵数据，也足以解决大规模问题。
然而，众所周知，这些方法的收敛速度也相当缓慢。
这篇文章提出了一种新的快速迭代收缩阈值算法（FISTA），该算法保持了ISTA的计算简单性，但全局收敛速度在理论和实践上都明显更好。
基于小波的图像去模糊的初始数值结果表明，FISTA的能力比ISTA快几个数量级。
Introduction
线性逆问题出现在广泛的应用中，如天体物理学、信号和图像处理、统计推理和光学等。逆问题的跨学科性质通过大量文献显而易见，其中包括大量的数学和算法发展；例如，请参阅专著[13]及其中的参考文献。
一个基本的线性逆问题导致我们研究这种形式的离散线性系统:
\(Ax = b + w \tag{1.1}\) 其中 $A \in \mathbb{R}^{m \times n}$ 和 $b \in \mathbb{R}$ 是已知的，$w$ 是未知的噪声（或者扰动）向量， 并且 $x$ 是真值或者要估计的位置信号/图像。在图像去模糊问题中， $b \in \mathbb{R}^m$ 表示模糊的图像， $x \in \mathbb{R}^n$ 是未知的真值图像， 其大小假设和 $b$ 相等(即 $m = n$)。 $b$ 和 $x$ 通过堆叠二维图像的列形成。在这些应用中，矩阵 $A$ 描述模糊算子，其在空间不变模糊的情况下，它代表一个二维卷积算子。从观察到的模糊和噪声图像 $b$ 中估计 $x$ 的问题被称为图像去模糊问题。
Background
一个解决问题$(1.1)$ 问题的经典方法是最小二乘法(LS)， 其估计最小化数据误差：
\[(LS): \hat x_{LS} = \mathop{\text{argmin}}_x \| Ax - b \|^2\]其中 $m = n$ (像一些图像处理一样) 并且 $A$ 是非奇异的， LS 估计仅仅是最朴素的解 $A^{-1}b$。 在许多应用中，例如图像模糊，$A$ 往往状 ill-conditioned的， 在这些情况下，LS解通常具有巨大的范数，因此毫无意义。为了克服这一困难，需要正则化方法来稳定解。正则化的基本思想是用一个“近似” well-conditioned 的问题取代原始的 ill-conditioned 问题，其解接近所需的解。流行的正则化技术之一是 Tikhonov 正则化[33]，其中在目标函数中添加二次惩罚：
\((T): \hat x_{TIK} = \mathop{\text{argmin}}_x \{\|Ax - b\|^2 + \lambda \| L x\|^2\} \tag{1.2}\) 上述最小化问题中的第二个项是控制解范数（或半范数）的正则化项。正则化参数 $\lambda > 0$ 提供观测保真度和噪声敏感度之间权衡。通常 $L$ 的选择是单位阵或近似一阶或二阶导数算子的矩阵。
$l_1$ 正则化方法在信号处理文献中引起了人们的兴趣和相当大的关注， 其寻找下式的解：
\(\min_x \{F(x) \equiv \|Ax - b\|^2 + \lambda \|x\|_1 \} \tag{1.3}\) 其中 $|x|_1$ 表示 $x$ 左右元素的绝对值之和。在图像去模糊应用中，特别是在基于小波的恢复方法中，$A$ 通常选择 $A = RW$， 其中 $R$ 是模糊矩阵， $W$ 包含小波基(乘以 $W$ 对应于执行逆小波变换)。 向量 $x$ 包含未知图像的系数。处理 $l_1$ 范数正则化准则的基本哲学是，大多数图像在小波域中的表征很稀疏。$l_1$ 项的存在用于引导 $(1.3)$ 最优解的稀疏性。基于 $l_1$ 的正则化 $(1.3)$ 相对于基于 $l_2$ 的正则化 $(1.2)$ 的另一个重要优势是，与后者相反，$l_1$ 正则化对异常值不太敏感，在图像处理应用中，异常值对应于尖锐的边缘。
凸优化问题（1.3）可以转换为二阶锥规划问题，因此可以通过内点方法解决[1]。然而，在大多数应用中，例如在图像模糊中，问题不仅是大规模的（可以达到数百万个决策变量），还涉及密集的矩阵数据，这往往排除了复杂内点方法的使用和潜在优势。这启发了寻找更简单的基于梯度的算法用以求解 $(1.3)$， 其中主要的计算成本是相对便宜的包括 $A$ 和 $A^T$ 的 matrix-vector 乘法。
The building blocks of the analysis.
The building blocks of the analysis.
考虑连续可微函数的无约束最小化问题 $f: \mathbb{R}^n \rightarrow \mathbb{R}$
\((U) \min \{f(x) : x \in \mathbb{R}^n\}\) 最简单的求解 $(U)$ 的方法是梯度下降算法， 其生成一个序列 ${x_k}$ 通过：
\[x_0 \in \mathbb{R}^n, \quad x_k = x_{k-1} - t_k \nabla f(x_{k-1}) \tag{2.1}\]其中 $t_k > 0$ 是步长。梯度迭代过程可以视作线性函数 $f$ 在 $x_{k-1}$ 的近端正则化， 等价写为：
\[x_k = \mathop{\text{argmin}}_x \left\{ f(x_{k-1}) + \langle x - x_{k-1}, , \nabla f(x_{k-1}) \rangle + \frac{1}{2 t_k} \|x - x_{k-1}\|^2 \right\}\]对非光滑的 $l_1$ 正则化问题采用相同的基本梯度思想：
\[x_k = \mathop{\text{argmin}}_x \left\{ f(x_{k-1}) + \langle x - x_{k-1}, , \nabla f(x_{k-1}) \rangle + \frac{1}{2 t_k} \|x - x_{k-1}\|^2 + \lambda J(x) \right\}\]忽略掉常数项， 可以重写为：
\[x_k = \mathop{\text{argmin}}_x \left\{\frac{1}{2 t_k} \|x - (x_{k-1} - \rho \nabla f(x_{k-1}))\|^2 + \lambda J(x)\right\}\]