Qia Li, Lixin Shen, Yuesheng Xu, and Na Zhang
Abstract: We introduce in this paper a class of multi-step proximity algorithms for solving an optimization problem (in the context of image processing) whose objective function is the sum of two convex functions with one composed by an affine transformation. We are particularly interested in the scenario when the convex functions involved in the objective function have low regularity (not differentiable) since many 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. A class of multi-step iterative schemes are developed based on the fixed-point equations appearing in the characterization of 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 via a multi-step iteration is convergent. We use this general convergence result to conclude that the proposed multi-step algorithms converge. We in particular design a new two-step algorithm for solving the optimization problem which includes several existing algorithms as special examples. Moreover, we reinterpret the well-known alternating split Bregman iteration method as a special case of the proposed algorithm and modify it to improve its convergence result. Numerical experiments for the L1-TV image denoising model for impulsive noise removal are presented to compare the approximation accuracy and computational efficiency of the two-step algorithm with those of a benchmark algorithm of Chambolle and Pock.
UCLA Computational and Applied Mathematics Reports (12-65)