Inverse Problem: algorithm

Section: Inverse Problems

How to minimize

$$ \alpha = \mathrm{argmin} \frac{1}{2} ||y - A\Phi\alpha ||_2^2 + \lambda ||\alpha||_1 $$

  • It is a non smooth convex problem
  • It is known as the LASSO or Basis Pursuit Denoising

Proximal operator and Soft Thresholding

Consider the denoising case :

$$ \alpha = \mathrm{argmin} \frac{1}{2} ||y - \alpha ||_2^2 + \lambda ||\alpha||_1 $$

We can show that the solution is given by the so-called Soft-Thresholding operator :

$$ \alpha = \mathcal{S}_{\lambda} \left( y \right) = y \left( 1 - \frac{\lambda}{|y |}\right)^+ $$ with $(x)^+ = \max(0,x)$, and all the operation are applied coordinatewise.

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)$

Remark: we have $ ||A\Phi ||^2 \leq ||A||^2 ||\Phi||^2 $, then if $\Phi$ is a Parseval frame, we simply have $L\leq ||A||^2$.