概要
FISTAは、ISTAにNestrovの加速勾配法を応用したもの
FISTAとISTAの違いがわからずもやもやしていたので、元論文を読んだついでに、まとめておく。
Iterative Shrinkage-Thresholding Algorithm (ISTA)
\boldsymbol{b} = \boldsymbol{A\bar{x}} + \boldsymbol{n}
という観測モデルを考えます。
$\boldsymbol{\bar{x}}$は元画像のウェーブレット係数
$\boldsymbol{A}$は逆離散ウェーブレット変換＋ボケ作用素
$\boldsymbol{n}$は白色雑音
$\boldsymbol{b}$は観測画像
$\boldsymbol{b}$から$\boldsymbol{\bar{x}}$を復元します。以下の最適化問題を考えます。
\min_{\boldsymbol{x}}||\boldsymbol{Ax}-\boldsymbol{b}||^{2}_{2} + \lambda||\boldsymbol{x}||_{1}
ウェーブレット係数はスパースなためL1正則化します。$\lambda$は正則化の強さを調整する定数です。解法として、以下のISTAが知られています。
ISTAのアルゴリズム
入力：$||\boldsymbol{Ax}-\boldsymbol{b}||^{2}_{2}$のリプシッツ定数
L=2\lambda_{max}(\boldsymbol{A}^{T}\boldsymbol{A})
$\lambda_{max}(\boldsymbol{A}^{T}\boldsymbol{A})$は、$\boldsymbol{A}^{T}\boldsymbol{A}$の最大固有値
初期化：
\boldsymbol{x}_{0}=DWT(\boldsymbol{b}), k\leftarrow1,
$DWT$は離散ウェーブレット変換
ステップ１：停止条件を見たしているなら結果を出力して終了
ステップ２：
\boldsymbol{x}_{k}=T_{\frac{\lambda}{L}}(\boldsymbol{x}_{k-1}-\frac{1}{L} \boldsymbol{A}^{T}(\boldsymbol{Ax}_{k-1}-\boldsymbol{b}))
ただし、$T_{\alpha}$はソフト閾値処理
T_{\alpha}(\boldsymbol{x})_{i}=(|x_{i}|-\alpha)_{+}sgn(x_{i})
ステップ３：$k\leftarrow k+1$
ステップ４：ステップ１に戻る
ISTAは収束が遅いため、Nestrovの加速勾配法を応用したFast ISTA (FISTA)が提案されています。
FISTA
FISTAのアルゴリズム
入力：$||\boldsymbol{Ax}-\boldsymbol{b}||^{2}_{2}$のリプシッツ定数
L=2\lambda_{max}(\boldsymbol{A}^{T}\boldsymbol{A})
$\lambda_{max}(\boldsymbol{A}^{T}\boldsymbol{A})$は、$\boldsymbol{A}^{T}\boldsymbol{A}$の最大固有値
初期化：
\boldsymbol{x}_{0}=DWT(\boldsymbol{b}),
\boldsymbol{y}_{1}=\boldsymbol{x}_{0},
t_{1}=1,
k \leftarrow 1
$DWT$は離散ウェーブレット変換
ステップ１：停止条件を見たしているなら結果を出力して終了
ステップ２：
\begin{align}
\boldsymbol{x}_{k}&=T_{\frac{\lambda}{L}}(\boldsymbol{y}_{k}-\frac{1}{L} \boldsymbol{A}^{T}(\boldsymbol{Ay}_{k}-\boldsymbol{b}))
\\
t_{k+1}&=\frac{1+\sqrt{1+4t^{2}_{k}}}{2}
\\
\boldsymbol{y}_{k+1}&=\boldsymbol{x}_{k}+\biggl(\frac{t_{k}-1}{t_{k+1}}\biggr)(\boldsymbol{x}_{k}-\boldsymbol{x}_{k-1})
\end{align}
ステップ３：$k\leftarrow k+1$
ステップ４：ステップ１に戻る
$\frac{t_{k}-1}{t_{k+1}}$はいわゆるモーメントで$k=1$で0、$k \rightarrow \infty$で1なので、最適解の近くで遅くなる収束を加速する働きがあります。
数値実験
画像のボケ除去と同じ検証方法でISTAとFISTAを比較した。
サンプルコードはこちら。
FISTAはISTAの約1/5の反復回数でピークのPSNRがえられた。
感想
Adam使ってもいいよね