A new linear convergence result for the iterative soft thresholding algorithm

Abstract

The iterative soft thresholding algorithm (ISTA) is one of the most popular optimization algorithms for solving the regularized least squares problem, and its linear convergence has been investigated under the assumption of finite basis injectivity property or strict sparsity pattern. In this paper, we consider the regularized least squares problem in finite- or infinite-dimensional Hilbert space, introduce a weaker notion of orthogonal sparsity pattern (OSP) and establish the Q-linear convergence of ISTA under the assumption of OSP. Examples are provided to illustrate the cases where the linear convergence of ISTA can be established only by our result, but cannot be ensured by any existing result in the literature.

Keywords:

• Iterative soft thresholding algorithm
• linear convergence analysis
• linear inverse problems
• sparsity pattern

Acknowledgements

The authors are grateful to two anonymous reviewers for their valuable suggestions and remarks which helped to improve the quality of the paper.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

Yaohua Hu was partially supported by the National Natural Science Foundation of China [grant number 11601343]; Natural Science Foundation of Guangdong [grant number 2016A030310038]; Foundation for Distinguished Young Talents in Higher Education of Guangdong [grant number 2015KQNCX145]; Chong Li was supported in part by the National Natural Science Foundation of China [grant number 11571308]; Jen-Chih Yao was partially supported by the MOST [grant number 105-2115-M-039-002-MY3].