FISTA（A fast iterative shrinkage-thresholding algorithm）是1种快速的迭代阈值收缩算法（ISTA）。FISTA和ISTA都是基于梯度降落的思想，在迭代进程中进行了更加聪明（smarter）的选择，从而到达更快的迭代速度。理论证明：FISTA和ISTA的迭代收敛速度分别为O(1/k2)和O(1/k)。
本篇博文先从解决优化问题的传统方法“梯度降落”开始，然后引入ISTA，再上升为FISTA，最后在到其利用（主要在图象的去模糊方面和特点匹配）。文章主要参考资料以下：
[1] A
Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems。
[2] Proximal Gradient Descent for L1 Regularization
[3] 线性回归及梯度下
-------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------我是分割线--------------------------------------------------------
斟酌以下线性转换问题：b = Ax + w （1）
例如在图象模糊问题中，A为模糊模板（由未模糊图象通过转换而来），b为模糊图象，w为噪声。并且，A和b已知，x为待求的系数。
求解该问题的的传统方法为最小2乘法，思想很简单粗鲁：使得重构误差||Ax-b||2最小。即：
对f(x) = ||Ax-b||2求导，可得其导数为：f'(x) = 2AT(Ax-b)。对该问题，令导数为零便可以获得最小值（函数f(x)为凸函数，其极小值即为最小值）。
1）如果A为非奇特矩阵，即A可逆的话，那末可得该问题的精确解为x=A⑴b。
2）如果A为奇特矩阵，即A不可逆，则该问题没有精确解。退而求其次，我们求1个近似解就好，||Ax-b||2<=ϵ。
其中,||x||_1为惩罚项，用以规范化参数x。该例子使用L1范数作为惩罚项，是希望x尽可能稀疏（非零元素个数尽量少），即b是A的1个稀疏表示。||Ax-b||2<=ϵ则为束缚条件，即重构误差最小。问题(3)也能够描写为：
式子(4)即为1般稀疏表示的优化问题。希望重构误差尽量小，同时参数的个数尽量少。
注：惩罚项也能够是L2或其他范数。
斟酌更加1般的情况，我们来讨论梯度降落法。有没有束缚的优化问题以下：
梯度降落法基于这样的视察：如果实值函数F(x)在点a处可微且有定义，那末函数F(x)在点a沿着梯度相反的方向-∇F(a)降落最快。
基于此，我们假定f(x)连续可微（continuously differentiable）。如果存在1个足够小的数值t>0使得x2 = x1 - t∇F(a)，那末：
F(x1) >= F(x2)
梯度降落法的核心就是通过式子(6)找到序列{xk}，使得F(xk) >= F(xk⑴)。
下图详细说明了梯度降落的进程：
从上图可以看出：初始点不同，取得的最小值也不同。由于梯度降落法求解的是局部最小值，受初值的影响较大。如果函数f(x)为凸函数的话，则局部最小值亦为全局最小值。这时候，初始点只对迭代速度有影响。
再回头看1下式子（6），我们使用步长tk和导数∇F(xk)来控制每次迭代时x的变化量。再看1下上面那张图，彩色缤纷那张。对每次迭代，我们固然希望F(x)的值降得越快越好，这样我们就可以更快速得取得函数的最小值。因此，步长tk的选择很重要。
如果步长tk太小，则找到最小值的迭代次数非常多，即迭代速度非常慢，或说迭代的收敛速度很慢；而步长太大的话，则会出现overshoot the minimum的现象，即不断在最小值左右徘徊，跳来跳去的，以下图所示：
但是，tk最后还是作用在xk⑴上，得到xk。因此，更加朴素的思想应当是：序列{xk}的个数尽量小，即每次迭代步伐尽量大，函数值减少得尽量多。那末就是关于序列{xk}的选择了，如何更好的选择每个点xk，使得函数值更快的趋近其最小值。
-----------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------我是分割线--------------------------------------------------------
ISTA和FISTA求解最小化问题的思想就是基于梯度降落法的，它们的优化在于对{xk}的选择上。这里我们不讲证明，只讲思想。想看证明的话，请看参考资料[1]。
ISTA（Iterative shrinkage-thresholding algorithm），即迭代阈值收缩算法。
先从无束缚的优化问题开始，即上面的式子(5)：
这时候候，我们还假定了f(x)满足Lipschitz连续条件，即f(x)的导数有下界，其最小下界称为Lipschitz常数L(f)。这时候，对任意的L>=L(f)，有：
基于此，在点xk附近可以把函数值近似为：
在梯度降落的每步迭代中，将点xk⑴处的近似函数获得最小值的点作为下1次迭代的起始点xk，这就是所谓的proximal regularization算法（其中，tk=1/L）。
上面的方法只合适解决非束缚问题。而ISTA要解决的可是带惩罚项的优化问题，引入范数规范化函数g(x)对参数x进行束缚，以下：
使用更加1般的2次近似模型来求解上述的优化问题，在点y，F(x) := f(x) + g(x)的2次近似函数为：
该函数的最小值表示为,P_L是proximal（近端算子）的简写情势：
疏忽其常数项f(y)和∇F(y)，这些有和没有对结果没有影响。再结合式子(11)和(12)，PL(y)可以写成：
明显，使用ISTA解决带束缚的优化问题时的基本迭代步骤为：
固定步长的ISTA的基本迭代步骤以下（步长t = 1/L(f)）：
但是，固定步长的ISTA的缺点是：Lipschitz常数L(f)不1定可知或可计算。例如，L1范数束缚的优化问题，其Lipschitz常数依赖于ATA的最大特点值。而对大范围的问题，非常难计算。因此，使用以下带回溯（backtracking）的ISTA：
理论证明：ISTA的收敛速度为O(1/k)；而FISTA的收敛速度为O(1/k2)。实际利用中，FISTA亦明显快于ISTA。其证明进程还是看这篇文章：[1]。
FISTA（A fast iterative shrinkage-thresholding algorithm）是1种快速的迭代阈值收缩算法（ISTA）。
FISTA与ISTA的区分在于迭代步骤中近似函数起始点y的选择。ISTA使用前1次迭代求得的近似函数最小值点xk⑴，而FISTA则使用另外一种方法来计算y的位置。理论证明，其收敛速度能够到达O(1/k2)。固定步长的FISTA的基本迭代步骤以下：
固然，斟酌到与ISTA一样的问题：问题范围大的时候，决定步长的Lipschitz常数计算复杂。FISTA与ISTA1样，亦有其回溯算法。在这个问题上，FISTA与ISTA并没有区分，上面也说了，FISTA与ISTA的区分仅仅在于每步迭代时近似函数起始点的选择。更加简明的说：FISTA用1种更加聪明的办法选择序列{xk}，使得其基于梯度降落思想的迭代进程更加快速地趋近问题函数F(x)的最小值。
带回溯的FISTA算法基本迭代步骤以下：
值得注意的是，在每步迭代中，计算近似函数的起止点时，FISTA使用前两次迭代进程的结果xk⑴,xk⑴，对其进行简单的线性组合生成下1次迭代的近似函数起始点yk。方法很简单，但效果却非常好。固然，这也是有理论支持的。
-----------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------我是分割线--------------------------------------------------------
LASSO是1个图象处理中经典的目标方程
第2项的1范数限制了x的稀疏性，前文已说过，在此不再叙述。
比如在图象去模糊的问题中，已知模糊的图象b，和模糊函数R，我们想恢复去模糊的图象I。这些变量的关系可以表达成I*R=b，其中*为卷积。在理想状态下，b没有任何噪音，那末这个问题就很简单。基于卷积定理，两个函数在时域的卷积相当于频域的相乘，那末我们只需要求出b和R的傅里叶变换，然后相除得到I的傅里叶变换，再将其恢复到时域。但是1般来讲模糊图象b含有噪声，这使得频域中的操作异常不稳定，所以更多时候，我们希望通过以下方程求得I
其中模糊算子R表现成矩阵情势，I和b表示为1维向量，函数p作为规范项。我们将I小波分解，I=Wx,其中W为小波基，x为小波基系数。我们知道图象的小波表示是稀疏的，那末目标方程就变成了LASSO的情势
其中A=RW。现在的问题是，这个方程由于L1范数的存在，不是处处可微的，如果用subgradient的方法，收敛的速度会很慢。
因此我们用ISTA(Iterative Shrinkage-Thresholding Algorithm)。这个算法可以解决以上f+g情势的最小化问题，但ISTA适用于以下情势问题的求解：
1.目标方程是f+g的情势
2.f和g是凸的，f是可导的，g无所谓
3.g需要足够简单（可拆分的，可以做坐标降落的coordinate descent）
因而，我们首先看对f做1般的递归降落。我们可以参照（13）式，即可以得到：
这时候我们可以看到，假设g是1个开拆分的函数(比如L1范数)，我们就能够对每维分别进行坐标降落，也就是将N维的最小值问题，转化成N个1D的最小值问题。我们发现，如果
的话，那末这个问题有解析解,即每步的迭代可以写成：
其中
称作shrinkage operator。
FISTA其实就是对ISTA利用Nestrerov加速。1个普通的Nestrerov加速递归降落的迭代步骤是:
利用到FISTA上的话，就是把第3步换成ISTA的迭代步骤。可以证明FISTA可以到达1/(t^2)的收敛速度。（t是迭代次数）通过下面的实验可以看到，一样迭代了300次，左图(ISTA)仍未收敛，图象依然模糊。而右图(FISTA)已基本还原了去模糊的原图。
-----------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------我是分割线--------------------------------------------------------
f is the transformation function between U and V. Then we can see that:
through the above function. We can get:
=========================
参考自：
1、Junhao_wu: http://www.cnblogs.com/JunhaoWu/p/Fista.html
2、Beyond Algorithm is Math : http://blog.csdn.net/iverson_49/article/details/38354961
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
