Combining line search and trust-region methods for ℓ1-minimization

ABSTRACT

This study presents a new trust-region algorithm to solve the ${\ell }_1$-minimization problem with applications to compressed sensing (CS) and image deblurring that will be augmented with a shrinkage operation to produce a new iteration whenever an approximated solution of the trust-region subproblem lies within one and iterate is successful, simultaneously. Otherwise, a nonmonotone Armijo-type line search strategy incorporates with shrinkage technique, which includes a convex combination of the maximum function value of some preceding iterates and the current function value. Therefore, the proposed approach takes advantages of both the effective trust-region and nonmonotone Armijo-type line search with a shrinkage operation. It is believed that selecting an appropriate shrinkage parameter according to a new procedure can improve the efficiency of our algorithm. The global convergence and the R-linear convergence rate of the proposed approach are proved for which numerical results are also reported.

KEYWORDS:

• ${\ell }_1$-minimization
• compressed sensing
• image deblurring
• shrinkage operation
• trust-region framework
• nonmonotone line search
• global convergence

2010 AMS SUBJECT CLASSIFICATIONS:

• 65K05
• 90C25
• 90C06
• 94A08

Acknowledgement

The authors would like to thank two anonymous referees for their insightful comments and also for their help in improving the presentation of the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.