您當(dāng)前位置：首頁 > php開源 > 綜合技術(shù) > FISTA的由來：從梯度下降法到ISTA & FISTA

FISTA的由來：從梯度下降法到ISTA & FISTA

來源：程序員人生發(fā)布時間：2016-06-01 17:23:31 閱讀次數(shù)：14322次

前言：

FISTA（A fast iterative shrinkage-thresholding algorithm）是1種快速的迭代閾值收縮算法（ISTA）。FISTA和ISTA都是基于梯度降落的思想，在迭代進程中進行了更加聰明（smarter）的選擇，從而到達(dá)更快的迭代速度。理論證明：FISTA和ISTA的迭代收斂速度分別為O(1/k^₂)和O(1/k)。

　　本篇博文先從解決優(yōu)化問題的傳統(tǒng)方法“梯度降落”開始，然后引入ISTA，再上升為FISTA，最后在到其利用（主要在圖象的去模糊方面和特點匹配）。文章主要參考資料以下：
　　[1] A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems。

　　[2] Proximal Gradient Descent for L1 Regularization

　　[3] 線性回歸及梯度下

-------------------------------------------------------------------------------------------------------------------------------------------------------

--------------------------------------------------------我是分割線--------------------------------------------------------

1.梯度降落法

斟酌以下線性轉(zhuǎn)換問題：b = Ax + w　　（1）

　　例如在圖象模糊問題中，A為模糊模板（由未模糊圖象通過轉(zhuǎn)換而來），b為模糊圖象，w為噪聲。并且，A和b已知，x為待求的系數(shù)。

　　求解該問題的的傳統(tǒng)方法為最小2乘法，思想很簡單粗魯：使得重構(gòu)誤差||Ax-b||²最小。即：

對f(x) = ||Ax-b||²求導(dǎo)，可得其導(dǎo)數(shù)為：f'(x) = 2A^T(Ax-b)。對該問題，令導(dǎo)數(shù)為零便可以獲得最小值（函數(shù)f(x)為凸函數(shù)，其極小值即為最小值）。

　　1）如果A為非奇特矩陣，即A可逆的話，那末可得該問題的精確解為x=A^⑴b。

　2）如果A為奇特矩陣，即A不可逆，則該問題沒有精確解。退而求其次，我們求1個近似解就好，||Ax-b||²<=?。

其中,||x||_1為懲罰項，用以規(guī)范化參數(shù)x。該例子使用L1范數(shù)作為懲罰項，是希望x盡可能稀疏（非零元素個數(shù)盡量少），即b是A的1個稀疏表示。||Ax-b||²<=?則為束縛條件，即重構(gòu)誤差最小。問題(3)也能夠描寫為：

式子(4)即為1般稀疏表示的優(yōu)化問題。希望重構(gòu)誤差盡量小，同時參數(shù)的個數(shù)盡量少。

注：懲罰項也能夠是L2或其他范數(shù)。

1.1 梯度降落法的缺點

斟酌更加1般的情況，我們來討論梯度降落法。有沒有束縛的優(yōu)化問題以下：

梯度降落法基于這樣的視察：如果實值函數(shù)F(x)在點a處可微且有定義，那末函數(shù)F(x)在點a沿著梯度相反的方向-?F(a)降落最快。

　　基于此，我們假定f(x)連續(xù)可微（continuously differentiable）。如果存在1個足夠小的數(shù)值t>0使得x₂ = x₁ - t?F(a)，那末：

　　F(x₁) >= F(x₂)

　　梯度降落法的核心就是通過式子(6)找到序列{x_k}，使得F(x_k) >= F(x_k⑴)。

下圖詳細(xì)說明了梯度降落的進程：

從上圖可以看出：初始點不同，取得的最小值也不同。由于梯度降落法求解的是局部最小值，受初值的影響較大。如果函數(shù)f(x)為凸函數(shù)的話，則局部最小值亦為全局最小值。這時候，初始點只對迭代速度有影響。

　　再回頭看1下式子（6），我們使用步長t_k和導(dǎo)數(shù)?F(x_k)來控制每次迭代時x的變化量。再看1下上面那張圖，彩色繽紛那張。對每次迭代，我們固然希望F(x)的值降得越快越好，這樣我們就可以更快速得取得函數(shù)的最小值。因此，步長t_k的選擇很重要。

　　如果步長t_k太小，則找到最小值的迭代次數(shù)非常多，即迭代速度非常慢，或說迭代的收斂速度很慢；而步長太大的話，則會出現(xiàn)overshoot the minimum的現(xiàn)象，即不斷在最小值左右徘徊，跳來跳去的，以下圖所示：

但是，t_k最后還是作用在x_k⑴上，得到x_k。因此，更加樸素的思想應(yīng)當(dāng)是：序列{x_k}的個數(shù)盡量小，即每次迭代步伐盡量大，函數(shù)值減少得盡量多。那末就是關(guān)于序列{x_k}的選擇了，如何更好的選擇每個點x_k，使得函數(shù)值更快的趨近其最小值。

-----------------------------------------------------------------------------------------------------------------------------------------------------

----------------------------------------------------------我是分割線--------------------------------------------------------

ISTA和FISTA求解最小化問題的思想就是基于梯度降落法的，它們的優(yōu)化在于對{x_k}的選擇上。這里我們不講證明，只講思想。想看證明的話，請看參考資料[1]。

2.ISTA算法

ISTA（Iterative shrinkage-thresholding algorithm），即迭代閾值收縮算法。

先從無束縛的優(yōu)化問題開始，即上面的式子(5)：

這時候候，我們還假定了f(x)滿足Lipschitz連續(xù)條件，即f(x)的導(dǎo)數(shù)有下界，其最小下界稱為Lipschitz常數(shù)L(f)。這時候，對任意的L>=L(f)，有：

基于此，在點x_k附近可以把函數(shù)值近似為：

在梯度降落的每步迭代中，將點x_k⑴處的近似函數(shù)獲得最小值的點作為下1次迭代的起始點x_k，這就是所謂的proximal regularization算法（其中，t_k=1/L）。

上面的方法只合適解決非束縛問題。而ISTA要解決的可是帶懲罰項的優(yōu)化問題，引入范數(shù)規(guī)范化函數(shù)g(x)對參數(shù)x進行束縛，以下：

使用更加1般的2次近似模型來求解上述的優(yōu)化問題，在點y，F(xiàn)(x) := f(x) + g(x)的2次近似函數(shù)為：

該函數(shù)的最小值表示為,P_L是proximal（近端算子）的簡寫情勢：

疏忽其常數(shù)項f(y)和?F(y)，這些有和沒有對結(jié)果沒有影響。再結(jié)合式子(11)和(12)，P_L(y)可以寫成：

明顯，使用ISTA解決帶束縛的優(yōu)化問題時的基本迭代步驟為：

固定步長的ISTA的基本迭代步驟以下（步長t = 1/L(f)）：

但是，固定步長的ISTA的缺點是：Lipschitz常數(shù)L(f)不1定可知或可計算。例如，L1范數(shù)束縛的優(yōu)化問題，其Lipschitz常數(shù)依賴于A^TA的最大特點值。而對大范圍的問題，非常難計算。因此，使用以下帶回溯（backtracking）的ISTA：

理論證明：ISTA的收斂速度為O(1/k)；而FISTA的收斂速度為O(1/k²)。實際利用中，F(xiàn)ISTA亦明顯快于ISTA。其證明進程還是看這篇文章：[1]。

3.FISTA

FISTA（A fast iterative shrinkage-thresholding algorithm）是1種快速的迭代閾值收縮算法（ISTA）。

FISTA與ISTA的區(qū)分在于迭代步驟中近似函數(shù)起始點y的選擇。ISTA使用前1次迭代求得的近似函數(shù)最小值點x_k⑴，而FISTA則使用另外一種方法來計算y的位置。理論證明，其收斂速度能夠到達(dá)O(1/k²)。固定步長的FISTA的基本迭代步驟以下：

固然，斟酌到與ISTA一樣的問題：問題范圍大的時候，決定步長的Lipschitz常數(shù)計算復(fù)雜。FISTA與ISTA1樣，亦有其回溯算法。在這個問題上，F(xiàn)ISTA與ISTA并沒有區(qū)分，上面也說了，F(xiàn)ISTA與ISTA的區(qū)分僅僅在于每步迭代時近似函數(shù)起始點的選擇。更加簡明的說：FISTA用1種更加聰明的辦法選擇序列{x_k}，使得其基于梯度降落思想的迭代進程更加快速地趨近問題函數(shù)F(x)的最小值。

　　帶回溯的FISTA算法基本迭代步驟以下：

值得注意的是，在每步迭代中，計算近似函數(shù)的起止點時，F(xiàn)ISTA使用前兩次迭代進程的結(jié)果x_k⑴,x_k⑴，對其進行簡單的線性組合生成下1次迭代的近似函數(shù)起始點y_k。方法很簡單，但效果卻非常好。固然，這也是有理論支持的。

-----------------------------------------------------------------------------------------------------------------------------------------------------

----------------------------------------------------------我是分割線--------------------------------------------------------

4.ISTA&FISTA的利用（去模糊）

LASSO是1個圖象處理中經(jīng)典的目標(biāo)方程

第2項的1范數(shù)限制了x的稀疏性，前文已說過，在此不再敘述。

比如在圖象去模糊的問題中，已知模糊的圖象b，和模糊函數(shù)R，我們想恢復(fù)去模糊的圖象I。這些變量的關(guān)系可以表達(dá)成I*R=b，其中*為卷積。在理想狀態(tài)下，b沒有任何噪音，那末這個問題就很簡單。基于卷積定理，兩個函數(shù)在時域的卷積相當(dāng)于頻域的相乘，那末我們只需要求出b和R的傅里葉變換，然后相除得到I的傅里葉變換，再將其恢復(fù)到時域。但是1般來講模糊圖象b含有噪聲，這使得頻域中的操作異常不穩(wěn)定，所以更多時候，我們希望通過以下方程求得I