Two Modified Schemes for the Primal Dual Fixed Point Method

Abstract

The primal dual fixed point (PDFP) proposed in [7] was designed to solve convex composite optimization problems in imaging and data sciences. The algorithm was shown to have some advantages for simplicity and flexibility for divers applications. In this paper we study two modified schemes in order to accelerate its performance. The first one considered is an inertial variant of PDFP, namely inertial PDFP (iPDFP) and the second one is based on a prediction correction framework proposed in [20], namely Prediction Correction PDFP (PC-PDFP). Convergence analysis on both algorithms are provided. Numerical experiments on sparse signal recovery and CT image reconstruction using TV- L₂ model are present to demonstrate the acceleration of the two proposed algorithms compared to the original PDFP algorithm.

Keywords

Inertial iteration / prediction-correction / primal dual fixed point method / acceleration / composite optimization / image restoration

References

[1] F. Alvarez, Weak convergence of a relaxed and inertial hybrid projection-proximal point algorithm for maximal monotone operators in hilbert space, SIAM Journal on Optimization, 14 (2004), pp. 773-782.

[2] F. Alvarez and H. Attouch, An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Analysis, 9 (2001), pp. 3-11.

[3] O. Banerjee, L. El Ghaoui, and A. d'Aspremont, Model selection through sparse maximum likelihood estimation for multivariate gaussian or binary data, J. Mach. Learn. Res., 9 (2008), pp. 485-516.

[4] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2 (2009), pp. 183-202.

[5] R. I. Bot and E. R. Csetnek, An inertial alternating direction method of multipliers, arXiv preprint arXiv:1404.4582, (2014).

[6] A. Chambolle and T. PocK, A first-order primal-dual algorithm for convex problems withapplications to imaging, Journal of Mathematical Imaging and Vision, 40 (2011), pp. 120-145.

[7] P. Chen, J. Huang, and X. Zhang, A primaldual fixed point algorithm for convex separable minimization with applications to image restoration, Inverse Problems, 29 (2013).

[8] P. Chen, J. Huang, and X. Zhang, A primal-dual fixed point algorithm for multi-block convex minimization, arXiv e-prints, (2016), arXiv:1602.00414, p. arXiv:1602.00414.

[9] P. Chen, J. Huang, and X. Zhang, A primal-dual fixed point algorithm for minimization of the sum of three convex separable functions, Fixed Point Theory and Applications, 2016 (2016), p. 54.

[10] P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Modeling & Simulation, 4 (2005), pp. 1168-1200.

[11] L. Condat, A primaldual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms, Journal of Optimization Theory and Applications, 158 (2013), pp. 460-479.

[12] W. Deng and W. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, Journal of Scientific Computing, 66 (2015), pp. 889-916.

[13] J. Eckstein, Approximate iterations in bregman-function-based proximal algorithms, Mathematical Programming, 83 (1998), pp. 113-123.

[14] E. Esser, X. Zhang, and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM Journal on Imaging Sciences, 3 (2010), pp. 1015-1046.

[15] H. GAO, Fast parallel algorithms for the x-ray transform and its adjoint, Med Phys, 39 (2012), pp. 7110-20.

[16] T. Goldstein and S. Osher, The split bregman method for 11-regularized problems, SIAM Journal on Imaging Sciences, 2 (2009), pp. 323-343.

[17] B. He, L.-Z. Liao, and X. Wang, Proximal-like contraction methods for monotone variational inequalities in a unified framework i: Effective quadruplet and primary methods, Computational Optimization and Applications, 51 (2012), pp. 649-679.

[18] B. He, L.-Z. LiAO, and X. WANG Proximal-like contraction methods for monotone variational inequalities in a unified frameworkii: general methods and numerical experiments, Computational Optimization and Applications, 51 (2012), pp. 681-708.

[19] B. He and X. YUAN, On the o(1/n) convergence rate of the douglasrachford alternating direction method, SIAM Journal on Numerical Analysis, 50 (2012), pp. 700-709.

[20] B. He, X. Yuan, and J. J. Z. Zhang, Comparison of two kinds of prediction-correction methods for monotone variational inequalities, Computational Optimization and Applications, 27 (2004), pp. 247-267.

[21] D. A. Lorenz and T. Pock, An inertial forward-backward algorithm for monotone inclusions, Journal of Mathematical Imaging and Vision, 51 (2015), pp. 311-325.

[22] C. A. Micchelli, L. Shen, and Y. Xu, Proximity algorithms for image models: denoising, Inverse Problems, 27 (2011).

[23] Y.. Nesterov, A method for solving the convex programming problem with convergence rate $\mathcal{O}\left(1/{k}^{2}\right)$, Proceedings of the USSR Academy of Sciences, 269 (1983), pp. 543-547

[24] Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc., 73 (1967), pp. 591-597.

[25] S. Setzer, Split bregman algorithm, douglas-rachford splitting and frame shrinkage, in Scale Space and Variational Methods in Computer Vision, X.-C. Tai, K. Mørken, M. Lysaker, and K.-A. Lie, eds., Berlin, Heidelberg, 2009, Springer Berlin Heidelberg, pp. 464-476.

[26] M. V. Solodov and B. F. Svaiter, Error bounds for proximal point subproblems and associated inexact proximal point algorithms, Mathematical Programming, 88 (2000), pp. 371389.

[27] B. C. V, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Advances in Computational Mathematics, 38 (2013), pp. 667-681.

[28] M. Wen, Y.-C. Tang, and J. Peng, An inertial primal-dual fixed point algorithm for composite optimization problems, 2016.

[29] M. ZHU and T. Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration, UCLA CAM Report, 34 (2008).

[30] Y.-N. ZHU and X. Zhang, Stochastic primal dual fixed point method for composite optimization, Journal of Scientific Computing, 84 (2020), p. 16.