개요

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$는 이산 웨이블릿 변환

1단계 : 정지 조건을 보면 결과를 출력하고 종료
2단계:

\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})

3단계: $k\leftarrow k+1$
4단계: 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$는 이산 웨이블릿 변환

1단계 : 정지 조건을 보면 결과를 출력하고 종료
2단계:

\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}

3단계: $k\leftarrow k+1$
4단계: 1단계로 돌아가기

$\frac{t_{k}-1}{t_{k+1}}$는 소위 모멘트에서 $k=1$에서 0, $k\rightarrow\infty$에서 1이므로 최적해 근처에서 느려진다 수렴을 가속하는 기능이 있습니다.

수치 실험

이미지 bokeh 제거과 같은 검증 방법으로 ISTA와 FISTA를 비교했다.
샘플 코드 는 이쪽.





FISTA는 ISTA의 약 1/5의 반복 횟수로 피크의 PSNR을 얻을 수 있었다.

감상

Adam을 사용할 수 있습니다.