概要

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使ってもいいよね