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/FISTA to RLS problem with CG. You will see ISTA/FISTA work well on the sparse signal while RLS 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) RLS: 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 RLS.
(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 (seunghwanyoo2013@u.northwestern.edu)