The over-relaxed monotone fast iterative shrinkage-thresholding algorithm (OMFISTA) needs to satisfy a complex convergence condition with respect to its additional parameters. To simplify the convergence condition, this study proposes a new OMFISTA, termed OMFISTAv2, using a parameter setting strategy which will derive a simple sufficient condition with respect to the additional parameters to guarantee the convergence of OMFISTAv2. Moreover, the authors find experimentally that OMFISTAv2 can accelerate MFISTA in some cases where the system matrix is ill-conditioned or rank-deficient, while OMFISTA cannot.

References

1. 1)
  - 17. Parikh, N., Boyd, S.: ‘Proximal algorithms’, Found. Trends Optim., 2014, 1, (3), pp. 123–231.
2. 2)
  - 14. Metzler, C.A., Maleki, A., Baraniuk, R.G.: ‘From denoising to compressed sensing’, IEEE Trans. Inf. Theory, 2016, 62, (9), pp. 5117–5144.
3. 3)
  - 9. Wen, Z.W., Yin, W.T., Goldfarb, D., et al: ‘A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization and continuation’, SIAM J. Sci. Comput., 2010, 32, (4), pp. 1832–1857.
4. 4)
  - 21. Beck, A., Teboulle, M.: ‘Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems’, IEEE Trans. Image Process., 2009, 18, (11), pp. 2419–2434.
5. 5)
  - 15. Zibulevsky, M., Elad, M.: ‘L1-L2 optimization in signal and image processing’, IEEE Signal Process. Mag., 2010, 27, (3), pp. 76–88.
6. 6)
  - 13. Donoho, D.L., Maleki, A., Montanari, A.: ‘Message-passing algorithms for compressed sensing’, Proc. Natl. Acad. Sci., 2009, 106, (45), pp. 18,914–18,919.
7. 7)
  - 8. Chen, S.S., Donoho, D.L., Saunders, M.A.: ‘Atomic decomposition by basis pursuit’, SIAM J. Rev., 2001, 43, (1), pp. 129–159.
8. 8)
  - 25. Donoho, D.L.: ‘De-noising by soft-thresholding’, IEEE Trans. Inf. Theory., 1995, 41, (3), pp. 613–627.
9. 9)
  - 18. Daubechies, I., Defrise, M., Mol, C.D.: ‘An iterative thresholding algorithm for linear inverse problems with a sparsity constraint’, Commun. Pure Appl. Math., 2004, 57, (11), pp. 1413–1457.
10. 10)
  - 7. Ghayem, F., Sadeghi, M., Babaie-Zadeh, M., et al: ‘Sparse signal recovery using iterative proximal projection’, IEEE Trans. Signal Process., 2018, 66, (4), pp. 879–894.
11. 11)
  - 12. Wright, S.J., Nowak, R.D., Figueiredo, M.A.T.: ‘Sparse reconstruction by separable approximation’, IEEE Trans. Signal Process., 2009, 57, (7), pp. 2479–2493.
12. 12)
  - 1. Elad, M.: ‘Sparse and redundant representations–from theory to applications in signal and image processing’ (Springer Press, New York, 2010).
13. 13)
  - 4. Vehkaperä, M., Kabashima, Y., Chatterjee, S.: ‘Analysis of regularized LS reconstruction and random matrix ensembles in compressed sensing’, IEEE Trans. Inf. Theory, 2016, 62, (4), pp. 2100–2124.
14. 14)
  - 27. Bertsekas, D.P.: ‘Nonlinear programming’ (Athena Scientific, Belmont, MA, 1999, 2nd edn.).
15. 15)
  - 10. Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.: ‘Gradient projection for sparse reconstruction application to compressed sensing and other inverse problems’, IEEE J. Sel. Top. Signal Process., 2007, 1, (4), pp. 586–597.
16. 16)
  - 3. Duarte, M.F., Eldar, Y.C.: ‘Structured compressed sensing from theory to applications’, IEEE Trans. Signal Process., 2011, 59, (9), pp. 4053–4085.
17. 17)
  - 22. Zibetti, M.V.W., Helou, E.S., Pipa, D.R.: ‘Accelerating over-relaxed and monotone fast iterative shrinkage-thresholding algorithms with line search for sparse reconstructions’, IEEE Trans. Image Process., 2017, 26, (7), pp. 3569–3578.
18. 18)
  - 29. Do, T.T., Gan, L., Nguyen, N.H., et al: ‘Fast and efficient compressive sensing using structurally random matrices’, IEEE Trans. Signal Process., 2012, 60, (1), pp. 139–154.
19. 19)
  - 16. Combettes, P.L., Pesquet, J.C.: ‘Proximal splitting methods in signal processing’, in Bauschke, H., Burachik, R., Combettes, P., et al (Eds.): ‘Fixed-point algorithms for inverse problems in science and engineering’ (Springer, New York, NY, USA, 2011), pp. 185–212.
20. 20)
  - 24. Zibetti, M.V.W., Helou, E.S., Miqueles, E.X., et al: ‘Accelerating the over-relaxed iterative shrinkage-thresholding algorithms with fast and exact line search for high resolution tomographic image reconstruction’. IEEE Int. Conf. on Image Processing, Quebec, 2015.
21. 21)
  - 26. Nocedal, J., Wright, S.: ‘Numerical optimization’ (Springer Science Business Media, New York, 2006).
22. 22)
  - 11. Gu, R.L., Dogandzic, A.: ‘Projected nesterov's proximal-gradient algorithm for sparse signal recovery’, IEEE Trans. Signal Process., 2017, 65, (13), pp. 3510–3525.
23. 23)
  - 28. Mallat, S.: ‘A wavelet tour of signal processing–the sparse way’ (Elsevier, Burlington, MA 01803, 2009, 3rd edn.).
24. 24)
  - 2. Donoho, D.L.: ‘Compressed sensing’, IEEE Trans. Inf. Theory, 2006, 52, (4), pp. 1289–1306.
25. 25)
  - 20. Kim, D., Fessler, J.A.: ‘Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)’, SIAM J. Opt., 2018, 28, (1), pp. 223–250.
26. 26)
  - 5. Becker, S., Bobin, J., Candès, E.J.: ‘NESTA: A fast and accurate first-order method for sparse recovery’, SIAM J. Imag. Sci., 2011, 4, (1), pp. 1–39.
27. 27)
  - 6. Sadeghi, M., Babaie-Zadeh, M.: ‘Iterative sparsification-projection: fast and robust sparse signal approximation’, IEEE Trans. Signal Process., 2016, 64, (21), pp. 5536–5548.
28. 28)
  - 23. Yamagishi, M., Yamada, I.: ‘Over-relaxation of the fast iterative shrinkage-thresholding algorithm with variable stepsize’, Inverse Probl., 2011, 27, (10), p. 105008.
29. 29)
  - 19. Beck, A., Teboulle, M.: ‘A fast iterative shrinkage-thresholding algorithm for linear inverse problems’, SIAM J. Imag. Sci., 2009, 2, (1), pp. 183–202.

New over-relaxed monotone fast iterative shrinkage-thresholding algorithm for linear inverse problems

References

Related content