Fast iterative shrinkage thresholding algorithm

The iterative shrinkage thresholding (IST) is one of the most effective methods to solve problem 2:

$$\mathbf{m}_{n+1} = \mathbf{T}_{\tau}\left[\mathbf{m}_{n} + (\math... ...bf{A}^{-1})^H(\mathbf{d}_{obs}-(\mathbf{S}\mathbf{A}^{-1})\mathbf{m}_n)\right],$$ (4)

where $\mathbf{m}_n$ denotes the coefficients model after $n$th iteration, $\mathbf{T}_{\tau}$ denotes a thresholding operator (which is a nonlinear operator) with an input parameter $\tau$, and $[\cdot]^H$ denotes the adjoint operator. It's worth noting that $\tau$ has different connections with $\lambda$ according to the thresholding type (Chen et al., 2014a).

Due to the $O(1/k)$ convergence of IST, implementing IST is usually very time-consuming in practice. Beck and Teboulle (2009) proposed the fast iterative shrinkage thresholding algorithm (FISTA) to improve the convergence rate:

$$\begin{split} \mathbf{m}_{n}' &= \mathbf{m}_n + \frac{v_n-1}{... ...thbf{S}\mathbf{A}^{-1})\mathbf{m}_n'\right)\right], \end{split}$$ (5)

where $v_n$ is a controlling parameter with the initial value $v_0=1$ and $\mathbf{v}_{n+1}=(1+\sqrt{1+4v_n^2})/2$.

The improved convergence rate is $O(1/k^2)$, and thus becomes widely used in the image-processing field since its invention.