This is Iterative Shrinkage Thresholding Algorithm (ISTA) for solving LASSO problem. LASSO problem assumes that signal x be sparse, and this assumption is not wrong. Most natural siggnal can be represented sparse in some domain. For example, natural scenes are sparse in Fourier transform domain or DCT domain. Sometimes the scene itself can be very sparse (e.g. stars at night).

ISTA is a first-order method which is gradient-based so it is simple and efficient. However, its convergence is slow - O(1/k). A fast ISTA (FISTA) is developed for faster convergence, which gives an improved complexity, O(1/(k^2)).

Here we will compare the LASSO problem with ISTA and FISTA to CLS problem with CG. You will see ISTA and FISTA work well on the sparse signal while CLS doesn't. You will see the improved performance of FISTA over ISTA as well.

• demo_ista.m: test script
• /opt: includes functions for optimization methods
• /func: includes functions for objective function and corresponding gradient function, and hessian function.
• /result: includes result images

• Degradation model: y = Hx = HPb = Ab where A = HP, P:representation matrix (P = I in my example)
• Deconvolution:
  (1) LASSO: min_x ||y-Ab||2 + lambda*||b||1
  (2) CLS: min_x 0.5||y-Hx||2 + 0.5lambda||Cx||2
  

Each approach is solved by a different numerical optimization method. ISTA/FISTA are used for LASSO problem and CG method is used for CLS.
(1) ISTA: A type of proximal gradient method
(2) FISTA: Fast version of ISTA
(3) Conjugate Gradient A efficient optimization algorithm for solving Ax=b (or quadratic objective function)

Seunghwan Yoo ([email protected])