Adaptive Proximal Point Algorithms for Total Variation Image Restoration
Abstract
Image restoration is a fundamental problem in various areas of imaging sciences. This paper presents a class of adaptive proximal point algorithms (APPA) with contraction strategy for total variational image restoration. In each iteration, the proposed methods choose an adaptive proximal parameter matrix which is not necessary symmetric. In fact, there is an inner extrapolation in the prediction step, which is followed by a correction step for contraction. And the inner extrapolation is implemented by an adaptive scheme. By using the framework of contraction method, global convergence result and a convergence rate of O(1/N) could be established for the proposed methods. Numerical results are reported to illustrate the efficiency of the APPA methods for solving total variation image restoration problems. Comparisons with the state-of-the-art algorithms demonstrate that the proposed methods are comparable and promising.References
K. J. Arrow, L. Hurwicz and H. Uzawa (1958), Studies in linear and non-linear programming, Stanford: Stanford University Press.
A. Auslender and M. Teboulle (2000), Lagrangian duality and related multiplier methods for variational inequality problems, SIAM Journal on Optimization, 10(4), 1097-1115.
D. P. Bertsekas (2009), Convex optimization theory, Cambridge: Athena Scientific.
J. H. Bramble, J. E. Pasciak and A. T. Vassilev (1997), Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM Journal on Numerical Analysis, 34(3), 1072-1092.
R. S. Burachik, A. N. Iusem and B. F. Svaiter (1997), Enlargement of monotone operators with applications to variational inequalities, Set-Valued Analysis, 5(2), 159-180.
J. V. Burke and M. Qian (2000), On the superlinear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating, Mathematical Programming, 88(1), 157-181.
A. Beck and M. Teboulle (2009), Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Transactions on Image Processing, 18(11), 2419-2434.
C. Brune, A. Sawatzky and M. Burger (2011), Primal and dual Bregman methods with application to optical nanoscopy, International Journal of Computer Vision, 92(2), 211-229.
T. F. Chan, G. H. Golub and P. Mulet (1999), A nonlinear primal-dual method for total variation-based image restoration, SIAM Journal on Scientific Computing, 20(6), 1964-1977.
X. Cai, D. Han and L. Xu (2012), An improved first-order primal-dual algorithm with a new correction step, Journal of Global Optimization, 1-10.
A. Chambolle (2004), An algorithm for total variation minimization and applications, Journal of Mathematical Imaging and Vision, 20(1-2), 89-97.
A. Chambolle and T. Pock (2011), A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision, 40(1), 120-145.
P. Chen, J. Huang and X. Zhang (2013), A primal-dual fixed point algorithm for convex separable minimization with applications to image restoration, Inverse Problems, 29(2), 025011.
P. L. Combettes and V. R. Wajs (2005), Signal recovery by proximal forward-backward splitting, Multiscale Modeling and Simulation, 4(4), 1168-1200.
X. Cai, G. Gu, B. He and X. Yuan (2011), A relaxed customized proximal point algorithm for separable convex programming, Optimization Online.
J. Douglas and H. H. Rachford (1956), On the numerical solution of heat conduction problems in two and three space variables, Transactions of the American mathematical Society, 82(2), 421-439.
J. Eckstein(1998), Approximate iterations in Bregman-function-based proximal algorithms, Mathematical Programming, 83(1-3), 113-123.
E. Esser, X. Zhang and T. Chan (2009), A general framework for a class of first order primal-dual algorithms for TV minimization, UCLA CAM Report, 09-67.
D. Han and B. He (2001), A new accuracy criterion for approximate proximal point algorithms, Journal of Mathematical Analysis and Applications, 263(2), 343-354.
D. Han (2003), A new hybrid generalized proximal point algorithm for variational inequality problems, Journal of Global Optimization, 26(2), 125-140.
B. He and X. Yuan (2010), A contraction method with implementable proximal regularization for linearly constrained convex programming, www.optimization-online.org/DB_HTML/2010/11/2817.html
B. He and X. Yuan (2012), Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective, SIAM Journal on Imaging Sciences, 5(1), 119-149.
B. He, X. L. Fu and Z. K. Jiang (2009), Proximal-point algorithm using a linear proximal term, Journal of Optimization Theory and Applications, 141(2), 299-319.
B. Martinet (1970), Brve communication Rgularisation d’inquations variationnelles par approximations successives, ESAIM: Mathematical Modelling and Numerical Analysis-Modlisation Mathmatique et Analyse Numrique, 4(R3), 154-158.
Y. Nesterov (1983), A method of solving a convex programming problem with convergence rate O(1/k2), In Soviet Mathematics Doklady, 27(2), 372-376.
C. A. Micchelli, L. Shen and Y. Xu (2011), Proximity algorithms for image models: denoising, Inverse Problems, 27(4), 045009.
A. Nemirovski (2004), Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM Journal on Optimization, 15(1), 229-251.
T. Pock and A. Chambolle (2011), Diagonal preconditioning for first order primal-dual algorithms in convex optimization, In 2011 IEEE International Conference on Computer Vision (ICCV), pp. 1762-1769.
L. I. Rudin, S. Osher and E. Fatemi (1992), Nonlinear total variation based noise removal algorithms, Physica D: Nonlinear Phenomena, 60(1), 259-268.
R. T. Rockafellar (1976), Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14(5), 877-898.
M. V. Solodov and B. F. Svaiter (2000), An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions, Mathematics of Operations Research, 25(2), 214-230.
S. Setzer (2011), Operator splittings, Bregman methods and frame shrinkage in image processing, International Journal of Computer Vision, 92(3), 265-280.
M. Teboulle (1997), Convergence of proximal-like algorithms, SIAM Journal on Optimization, 7(4), 1069-1083.
C. R. Vogel and M. E.Oman (1996), Iterative methods for total variation denoising, SIAM Journal on Scientific Computing, 17(1), 227-238.
J. Wu and G. Yu (2014), On the convergence and O(1/N) complexity of a class of nonlinear proximal point algorithms for monotonic variational inequalities, Statistics, Optimization and Information Computing, 2(2), 105-113.
G. Yu, L. Qi and Y. Dai (2009), On nonmonotone Chambolle gradient projection algorithms for total variation image restoration, Journal of Mathematical Imaging and Vision, 35(2), 143-154.
X. Zhang, M. Burger and S. Osher (2011), A unified primal-dual algorithm framework based on Bregman iteration, Journal of Scientific Computing, 46(1), 20-46.
M. Zhu, S. J. Wright and T. F. Chan (2010), Duality-based algorithms for total-variation-regularized image restoration, Computational Optimization and Applications, 47(3), 377-400.
M. Zhu and T. F. Chan (2008), An efficient primal-dual hybrid gradient algorithm for total variation image restoration, UCLA CAM Report, 08-34.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
