Multi-step fixed-point proximity algorithms for solving a class of optimization problems arising from image processing

Qia Li, Lixin Shen, Yuesheng Xu, Na Zhang

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


We introduce in this paper a class of multi-step fixed-point proximity algorithms for solving optimization problems in the context of image processing. The objective functions of such optimization problems are the sum of two convex functions having one composed with an affine transformation which is often the regularization term. We are particularly interested in the scenario when the convex functions involved in the objective function have low regularity (not differentiable) since many practical problems encountered in image processing have this nature. We characterize the solutions of the optimization problem as fixed-points of a mapping defined in terms of the proximity operators of the two convex functions. The algorithmic and mathematical challenges come from the fact that the mapping is a composition of a firmly non-expansive operator with an expansive affine transform. A class of multi-step iterative schemes are developed based on the fixed-point equations that characterize the solutions. For the purpose of studying convergence of the proposed algorithms, we introduce a notion of weakly firmly non-expansive mappings and establish under certain conditions that the sequence generated from a weakly firmly non-expansive mapping is convergent. We use this general convergence result to conclude that the proposed multi-step algorithms converge. We in particular design a class of two-step algorithms for solving the optimization problem which include several existing algorithms as special examples and at the same time offer novel algorithms. Moreover, we identify the well-known alternating split Bregman iteration method as a special case of the proposed algorithm and modify it to improve its convergence result. A class of two-step algorithms for the total variation based image restoration models are presented.

Original languageEnglish (US)
Pages (from-to)387-422
Number of pages36
JournalAdvances in Computational Mathematics
Issue number2
StatePublished - May 8 2014


  • Convex optimization
  • Fixed-point algorithm
  • Image processing
  • Proximity operator

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Multi-step fixed-point proximity algorithms for solving a class of optimization problems arising from image processing'. Together they form a unique fingerprint.

Cite this