FISTA: some remarks

Fast Iterative Shrinkage/Thresholding algorithm (FISTA)

Initialization: $\alpha^{(0)}\in\mathbb{R}^N$, $z^{(0)}\in\mathbb{R}^N$, $L \leq ||A\Phi ||^2$, $t=0$
Do until convergence :
- $\alpha^{(t+1)} = \mathcal{S}_{\lambda/L} \left( z^{(t)} + \frac{1}{L}\Phi^* A^* \left( y - A\Phi z^{(t)} \right) \right)$
- $z^{(t+1)} = \alpha^{(t+1)} + \frac{t}{t+5} \left( \alpha^{(t+1)} - \alpha^{(t)} \right)$

In practice, the algorithm must be run with various value of lambda.
When $\lambda\rightarrow 0$ we have $|y - A\Phi\alpha| \rightarrow 0$.
When $\lambda = ||\Phi^* A^*y||_\infty$, the solution is $\alpha = 0$
One can choose these value distributed on a log scale in $\in [ 10^{-4}||\Phi^* A^*y||_\infty, ||\Phi^* A^*y||_\infty)$, with a fixed number of $\lambda$, such as we have $\lambda_1 > \lambda_2 > \ldots > \lambda_I$
The idea is to initialize the algorithm for $\lambda_i$ with the results get from $\lambda_{i-1}
Set $L \leq ||A\Phi ||^2$ and $\alpha_{(0)} = z_{(0)} = 0$
for i = 1:I
- Chose $\lambda = \lambda_i$
- Initialization: $\alpha_{(i)}^{(0)} = z_{(i)}^{(0)} = \alpha_{(i-1)}$, $t=0$
- Do until convergence :
  - $\alpha_{(i)}^{(t+1)} = \mathcal{S}_{\lambda/L} \left( z_{(i)}^{(t)} +\frac{1}{L} \Phi^* A^* \left( y - A\Phi z_{(i)}^{(t)} \right) \right)$
  - $z_{(i)}^{(t+1)} = \alpha_{(i)}^{(t+1)} + \frac{t}{t+5} \left( \alpha_{(i)}^{(t+1)} - \alpha_{(i)}^{(t)} \right)$

The Soft-thresholding can be replaces by any thresholding rules
Some examples:
- Hard Thresholding : $\mathcal{H}_\lambda(\alpha) = \alpha \boldsymbol{1}_{| \alpha | > \lambda}$
- Empirical Wiener: $\mathcal{S}^{EW}_\lambda(\alpha) = \alpha \left( 1 - \frac{\lambda^2}{|\alpha |^2}\right)^+$