A REFINED PRIMAL-DUAL ALGORITHM FOR A SADDLE-POINT PROBLEM WITH APPLICATIONS TO IMAGING

摘要

There are rich literatures on primal-dual algorithms for a saddle-point problem; and they have been demonstrated to be very efficient for some image restoration models with the total variation regularization. How to determine the step sizes is crucial for ensuring the efficiency of these primal-dual algorithms, and it has received intensive attention in the literature. This paper shows that the step sizes can be substantially refined if the output of a primal-dual algorithm at each iteration is corrected slightly. A modified primal-dual algorithm with refined step sizes is thus proposed. We prove rigorously the convergence of this new algorithm, and establish its worst-case convergence rate measured by the iteration complexity in ergodic and non-ergodic senses. The acceleration effectiveness of the refined step sizes is demonstrated by the TV image deblurring and inpainting problems.