Linear Convergence of ISTA and FISTA

doi:10.1007/s40305-024-00561-0

Abstract

Abstract: In this paper, we revisit the iterative shrinkage-thresholding algorithm (ISTA) for solving linear inverse problems with sparse representation, commonly found in signal and image processing. We conduct numerical experiments and observe that the convergence behavior of ISTA tends to be linear instead of logarithmic, resulting in a flat approximation on the logarithmic-scale ordinate. Through meticulous observations, we find that assuming the smooth part to be strongly convex, rather than just convex, is more reasonable for the least-square model, even when dealing with ill-conditioned image matrices. We also improve the pivotal inequality for composite optimization by considering the smooth part to be strongly convex instead of general convex, which was first introduced in Li et al. (Proximal Subgradient Norm Minimization of ISTA and FISTA, arXiv:2211.01610, 2022). By utilizing this pivotal inequality, we extend linear convergence to composite optimization, both in terms of the objective value and the square of the proximal subgradient norm. To support our findings, we use a simple ill-conditioned matrix that allows for easy computation of the singular values, instead of the original blur matrix. The new numerical experiment demonstrates that the fast iterative shrinkage-thresholding algorithm for strongly convex functions has a faster linear convergence rate compared to ISTA. Furthermore, based on the tighter pivotal inequality, we also generalize the faster linear convergence rate to composite optimization, considering both the objective value and the square of the proximal subgradient norm. We achieve this by leveraging a well-constructed Lyapunov function with slight modifications and the phase-space representation based on the high-resolution ordinary differential equation framework from the implicit-velocity scheme.

Key words: Composite optimization, ISTA, FISTA, s-Proximal operator, s-Proximal subgradient operator, μ-strongly convex function

CLC Number:

Bo-Wen Li, Bin Shi, Ya-Xiang Yuan. Linear Convergence of ISTA and FISTA[J]. Journal of the Operations Research Society of China, 2026, 14(2): 345-363.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00561-0

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I2/345

References

[1] Attouch, H., Chbani, Z., Fadili, J., Riahi, H.: First-order optimization algorithms via inertial systems with hessian driven damping. Math. Program. 193, 113–155(2020)
[2] Attouch, H., Peypouquet, J., Redont, P.: A dynamical approach to an inertial forward–backward algorithm for convex minimization. SIAM J. Optim. 24(1), 232–256(2014)
[3] Beck, A.: First-order methods in optimization. SIAM, Philadelphia (2017)
[4] Beck, A., Teboulle, M.: A fast iterative shrinkage–thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183–202(2009)
[5] Chambolle, A., Pock, T.: An introduction to continuous optimization for imaging. Acta Numer. 25, 161–319(2016)
[6] Chen, S., Shi, B., Yuan, Y.-X.: Gradient norm minimization of nesterov acceleration: o(1/k3) (2022). arXiv:2209.08862
[7] Chen, S., Shi, B., Yuan, Y.-X.: Revisiting the high-resolution phenomenon via high-resolution differential equations (2022). arXiv:2212.05700
[8] Engl, H.W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems, vol. 375. Springer, Dordrecht (1996)
[9] Figueiredo, M.A., 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. 1(4), 586–597(2007)
[10] Hansen, P.C., Nagy, J.G., O’leary, D.P.: Deblurring Images: Matrices, Spectra, and Filtering. SIAM, Philadelphia (2006)
[11] Jordan, M.I.: Dynamical, symplectic and stochastic perspectives on gradient-based optimization. In: Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pp. 523–549. World Scientific (2018)
[12] Li, B., Shi, B., Yuan, Y.-X.: Proximal subgradient norm minimization of ISTA and FISTA (2022). arXiv:2211.01610
[13] Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, vol. 87. Springer Science & Business Media, Berlin (1998)
[14] Nesterov, Y.: Recent advances in structural optimization. In: Proceedings of the International Congress of Mathematicians 2010, pp. 2964–2978. World Scientific (2010)
[15] Nesterov, Y.E.: A method for solving the convex programming problem with convergence rate O(1/k2). Dokl. Akad. Nauk SSSR 269, 543–547(1983)
[16] Osher, S., Ruan, F., Xiong, J., Yao, Y., Yin, W.: Sparse recovery via differential inclusions. Appl. Comput. Harmon. Anal. 41(2), 436–469(2016)
[17] Polyak, B.T.: Some methods of speeding up the convergence of iteration methods. USSR Comput. Math. Math. Phys. 4(5), 1–17(1964)
[18] Rockafellar, R.T.: Convex Analysis, vol. 18. Princeton University Press, Princeton (1970)
[19] Shi, B., Du, S.S., Jordan, M.I., Su, W.J.: Understanding the acceleration phenomenon via highresolution differential equations. Math. Program. 195(1), 79–148(2022)
[20] Shi, B., Du, S.S., Su, W., Jordan, M.I.: Acceleration via symplectic discretization of high-resolution differential equations. Adv. Neural Inf. Process. Syst. 32(2019)
[21] Su, W., Bogdan, M., Candes, E.: False discoveries occur early on the lasso path. Ann. Stat. 2133–2150(2017)
[22] Su, W., Boyd, S., Candes, E.J.: A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights. J. Mach. Learn. Res. 17, 1–43(2016)
[23] Su, W., Candès, E.: SLOPE is adaptive to unknown sparsity and asymptotically minimax. Ann. Stat. 44(3), 1038–1068(2016)