A Splitting Primal-dual Proximity Algorithm for Solving Composite Optimization Problems

Yu Chao TANG^{1}, Chuan Xi ZHU^{1}, Meng WEN^{2,3}, Ji Gen PENG^{2,3}

1. Department of Mathematics, Nanchang University, Nanchang 330031, P. R. China; 2. School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an 710049, P. R. China; 3. Beijing Center for Mathematics and Information Interdisciplinary Sciences, Beijing 100048, P. R. China

Abstract Our work considers the optimization of the sum of a non-smooth convex function and a finite family of composite convex functions, each one of which is composed of a convex function and a bounded linear operator. This type of problem is associated with many interesting challenges encountered in the image restoration and image reconstruction fields. We developed a splitting primal-dual proximity algorithm to solve this problem. Furthermore, we propose a preconditioned method, of which the iterative parameters are obtained without the need to know some particular operator norm in advance. Theoretical convergence theorems are presented. We then apply the proposed methods to solve a total variation regularization model, in which the L2 data error function is added to the L1 data error function. The main advantageous feature of this model is its capability to combine different loss functions. The numerical results obtained for computed tomography (CT) image reconstruction demonstrated the ability of the proposed algorithm to reconstruct an image with few and sparse projection views while maintaining the image quality.

Fund:Supported by the NSFC (Grant Nos. 11201216, 11401293, 11461046 and 11661056), the National Basic Research Program of China (Grant No. 2013CB329404) and the NSF of Jiangxi Province (Grant Nos. 20151BAB211010 and 20142BAB211016)

Boyd, S., Parikh, N., Chu, E., et al.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3, 1–122 (2010)

[2]

Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imag. Vis., 40, 120–145 (2011)

[3]

Chen, P. J., Huang, J. G., Zhang, X. Q.: A primal-dual fixed point algorithm based on proximity operator for convex set constrained separable problem. J. Nanjing Normal University (Natural Science Edition), 36, 1–5 (2013)

[4]

Chen, P. J., Huang, J. G., Zhang, X. Q.: A primal-dual fixed point algorithm for convex separable minimization with applications to image restoration. Inverse Prob., 29, 025011 (33pp) (2013)

[5]

Combettes, P. L., Pesquet, J. C.: A Douglas–Rachford splitting approach to nonsmooth conve variational signal recovery. IEEE J. Sel. Top. Sign. Proces., 1, 564–574 (2007)

[6]

Combettes, P. L., Pesquet, J. C.: Fixed-point algorithm for inverse problems in science and engineering. Proximal Splitting Methods in Signal Processing, Bauschke, H., Burachik, R., Combettes, P., Elser, V., Luke, D., and Wolkowicz, H.: Eds. Springer-Verlag, New York, 2010, 185–212

[7]

Combettes, P. L., Pesquet, J. C.: Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators. Set-Valued Var. Anal., 20, 307–330 (2012)

[8]

Condat, L.: A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl., 158, 460–479 (2013)

[9]

Goldstein, T., Osher, S.: The split Bregman method for l1-regularized problems. SIAM J. Imaging Sci., 2, 323–343 (2009)

[10]

Hansen, P., Saxild-Hansen, M.: AIR tools—a MATLAB package of algebraic iterative reconstruction methods. J. Comput. Appl. Math., 236, 2167–2178 (2012)

[11]

He, B., Yuan, X.: Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective. SIAM J. Imaging Sci., 5, 119–149 (2012)

[12]

Moreau, J.: Fonctions convexes duales et points proximaux dans un espace Hilbertien. C. R. Acad. Sci., Paris Ser. A Math., 255, 2897–2899 (1962)

[13]

Popov, L. D.: A modification of the Arrow–Hurwitz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28, 845–848 (1980)

[14]

Pock, T., Chambolle, A.: Diagonal preconditioning for first order primal-dual algorithms in convex optimization. IEEE International Conference on Computer Vision (ICCV), IEEE, 1762–1769 (2011)

[15]

Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Phys. D, 60, 259–268 (1992)

[16]

Setzer, S.: Split Bregman algorithms, Douglas–Rachford splitting and frame shrinkage. Scale Space and Variational Methods in Computer Vision, Tai, X., Morken, K., Lysaker, M., Lie, K.: Eds. Springer-Verlag, 5567, 464–476 (2009)

[17]

Setzer, S., Steidl, G., Teuber, T.: Deblurring Poissonian images by split Bregman techniques. J. Vis. Comm. Image Rep., 21, 193–199 (2010)

[18]

Setzer, S.: Operator splittings, Bregman methods and frame shrinkage in image processing. Int. J. Comput. Vis., 92, 265–280 (2011)

[19]

Sidky, E., Jørgensen, J., Pan, X.: Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle–Pock algorithm. Phys. Med. Biol., 57, 3065–3091 (2012)

[20]

Tang, Y.: A primal dual fixed point algorithm for constrained optimization problems with applications to image reconstruction. Proc. SPIE 9413, Medical Imaging 2015: Image Processing, 94131W, 1–9 (2015)

[21]

Tang, Y., Cai, Y., Wang, X., et al.: A primal dual proximal point method of Chambolle–Pock algorithm for total variation image reconstruction. 2013 IEEE International Conference on Medical Imaging Physics and Engineering (ICMIPE), IEEE, 6–10 (2013)

[22]

Tang, Y., Peng, J., Yue, S., et al.: A primal dual proximal point method of Chambolle–Pock algorithms for l1-tv minimization problems in image reconstruction. 2012 5-th International Conference on Biomedical Engineering and Informatics (BMEI), IEEE, 12–16 (2012)

[23]

Zhang, X., Burger, M., Osher, S.: A unified primal-dual framework based on Bregman iteration. J. Sci. Comput., 46, 20–46 (2011)