大家好，又见面了，我是你们的朋友全栈君。

Iterative Shrinkage Thresholding Algorithm(ISTA)

ISTA

对于一个基本的线性逆问题：
$$y=Ax+w\text{\hspace{1em}(1)}$$
其中$A\in {\mathbb{R}}^{M\times N}$，$y\in {\mathbb{R}}^{M\times 1}$，$w$是未知噪声。(1)式可用最小二乘法来求解：
$${\hat{x}}_{LS}=\underset{x}{\mathrm{argmi}}n\Vert Ax-y{\Vert }_2^2\text{\hspace{1em}(2)}$$
当 $M=N$ 且 $A$ 非奇异时，最小二乘法的解等价于$A^{-1}y$。然而，在很多情况下，$A$ 是病态的(ill-conditioned)。最小二乘是一种无偏估计方法，如果系统是病态的，则会导致其估计方差很大，因此最小二乘法不适用于求解病态方程。

为了求解病态线性系统的逆问题，可以使用岭回归。岭回归方法的主要思想是以可容忍的微小偏差来换取估计的良好效果，实现方差和偏差的一个trade-off。岭回归求解病态问题可以表示为：
$${\hat{x}}_T=\underset{x}{\mathrm{argmin}}\frac{1}{2}\Vert Ax-y{\Vert }_2^2+\lambda \Vert x{\Vert }_2^2\text{\hspace{1em}(3)}$$
其中$\lambda >0$ 为正则化参数。

另一种求解(1)式的方法是采用 ${\ell }_1$范数作为正则项，这就是经典的LASSO问题：
$$\hat{x}=\underset{x}{\mathrm{argmin}}\Vert Ax-y{\Vert }_2^2+\lambda \Vert x{\Vert }_1\text{\hspace{1em}(4)}$$
采用${\ell }_1$范数正则项相对于 ${\ell }_2$ 范数正则项有两个优势：

• ${\ell }_1$范数正则项能产生稀疏解；
• 对异常值不敏感。

式(4)是一个凸优化问题，通常可以转化为二阶锥规划问题，从而使用内点法等方法求解。然而在大规模问题中，由于数据维度太大，而内点法的算法复杂度为 $O(N^3)$，导致求解非常耗时。由于基于梯度的方法算法复杂度小，而且算法结构简单，容易操作，很多研究者研究通过简单的基于梯度的方法来求解(4)式。

在众多基于梯度的算法中，ISTA算法是一种非常受关注的算法，ISTA算法在每一次迭代中通过一个收缩/软阈值操作来更新$x$，其具体迭代格式如下：
$$\begin{array}{rl}{x}^{k+1}& =S_{\alpha \lambda }\left(x^k+\alpha A^T(y-A{x}^k)\right)\\ x^{k+1}& =S_{\frac{\lambda }{L}}\left(x^k+\frac{1}{L}{A}^T(y-A{x}^k)\right)(\alpha =\frac{1}{L})\end{array}\text{\hspace{1em}(5)}$$

PS：第二个式子就是$\alpha =\frac{1}{L}$时的情况，论文中证明只有当 $L\ge {\sigma }_{max}(D^{T}D)$时，才能保证收敛性， 其中${\sigma }_{max}(A)$表示 $A$ 的最大特征值。

其中 $S_{\theta }(x)$ 是软阈值操作函数：
$$S_{\theta }(x)=\mathrm{sign}(x)\cdot \max (|x|-\theta ,0)\text{\hspace{1em}(6)}$$
下面我们对式(5)进行推导：

首先，对于式(5)，我们记：
$$\underset{x}{\mathrm{argmin}}f(x):=\underset{x}{\mathrm{argmin}}\frac{1}{2}(Ax-y{)}^T(Ax-y)+\lambda {\Vert x\Vert }_1\text{\hspace{1em}(7)}$$
其中，$f(x)$的第一项可以看作时重构项，第二项可以看作是正则化项。对于该优化问题，我们可以很容易想到利用梯度下降法来求解。

首先，对$f$ 求 $x$ 的偏导：
$$\frac{\partial f}{\partial x}=\frac{\partial f_1}{\partial x}+\frac{\partial f_2}{\partial x}=A^T(Ax-y)+\lambda \mathrm{sign}(x)\text{\hspace{1em}(8)}$$
对于第一项：
$$x^{k+1}=x^k-\alpha A^T(Ax-y)\text{\hspace{1em}(9)}$$
对于第二项：
$$x^{k+1}=x^k-\alpha \lambda \mathrm{sign}(x)\text{\hspace{1em}(10)}$$
但是，符号函数$sign(z)$ 在 0 处是不可微的！怎么处理？

ISTA做了如下处理：
$$\mathrm{shrink}(x,\alpha \lambda ):\{\begin{array}{rl}& if\mathrm{sign}(x)\ne \mathrm{sign}(x-\alpha \lambda \mathrm{sign}(x)):thenx=0\\ & else:x=x-\alpha \lambda \mathrm{sign}(x)\end{array}\text{\hspace{1em}(11)}$$
简单来说，因为${\ell }_1$范数在0附近不可微，所以就将0的邻域设置为可微！下图其实就是收缩算子的图像。

上面的两项的处理过程概括起来就是ISTA算法：

• 初始化 $x^{(0)}=0$
• 当 $x^{(}k)$未收敛
  • $x^k=x^k-\alpha A^T(Ax-y)$
  • $x^{k+1}=\mathrm{shrink}\left(x^k,\alpha \lambda \right)$

其实带进去算一下，就可以知道$\mathrm{shrink}\left(x^k,\alpha \lambda \right)$其实就是上面的$S_{\theta }(x)$，所以ISTA可以总结如下：
$$\begin{array}{rl}{x}^{k+1}& =S_{\alpha \lambda }\left(x^k+\alpha A^T(y-A{x}^k)\right)\\ S_{\theta }(x)& =\mathrm{sign}(x)\cdot \max (|x|-\theta ,0)\end{array}\text{\hspace{1em}(12)}$$
证明完毕。

参考文献

• Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM journal on imaging sciences, 2009, 2(1): 183-202.