Image ProcessingNo Access

Alternating Primal-Dual Algorithm for Minimizing Multiple-Summed Separable Problems with Application to Image Restoration

Peng Wang

https://orcid.org/0000-0002-6621-2079

School of Computer Science and Technology, Wuhan University of Technology, Wuhan, 430070, P. R. China

School of Mathematics and Computational Science, Wuyi University, Jiangmen 529020, P. R. China

E-mail Address: p_wong@126.com

Search for more papers by this author

and

Shengwu Xiong

School of Computer Science and Technology, Wuhan University of Technology, Wuhan, 430070, P. R. China

E-mail Address: xiongsw@whut.edu.cn

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0218001421540185Cited by:0 (Source: Crossref)

Abstract

In order to discover the difference among dual strategies, we propose an alternating primal-dual algorithm (APDA) that can be considered as a general version for minimizing problem which is multiple-summed separable convex but not necessarily smooth. First, the original multiple-summed problem is transformed into two subproblems. Second, one subproblem is solved in the primal space and the other is solved in the dual space. Finally, the alternating direction method is executed between the primal and the dual part. Furthermore, the classical alternating direction method of multipliers (ADMM) is extended to solve the primal subproblem which is also multiple summed, therefore, the extended ADMM can be seen as a parallel method for the original problem. Thanks to the flexibility of APDA, different dual strategies for image restoration are analyzed. Numerical experiments show that the proposed method performs better than some existing algorithms in terms of both speed and accuracy.

Keywords:

References

1. J. Adler and O. Oktem, Learned primal-dual reconstruction, IEEE Trans. Med. Imag. 37(6) (2018) 1322–1332. Web of Science, Google Scholar
2. M. V. Afonso, J. M. Bioucas-Dias and M. A. Figueiredo, An augmented Lagrangian approach to the constrained optimization formulation of imaging inverse problems, IEEE Trans. Image Process. 20(3) (2011) 681–695. Web of Science, Google Scholar
3. H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces (Springer, 2011). Google Scholar
4. A. Beck and M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process. 18(11) (2009) 2419–2434. Web of Science, Google Scholar
5. R. I. Boţ, E. R. Csetnek and A. Heinrich, A primal-dual splitting algorithm for finding zeros of sums of maximal monotone operators, SIAM J. Optimiz. 23(4) (2013) 2011–2036. Web of Science, Google Scholar
6. S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn. 3(1) (2011) 1–122. Google Scholar
7. A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imag. Vis. 20(1–2) (2004) 89–97. Web of Science, Google Scholar
8. A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imag. Vis. 40(1) (2011) 120–145. Web of Science, Google Scholar
9. R. H. Chan, M. Tao and X. Yuan, Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers, SIAM J. Imag. Sci. 6(1) (2013) 680–697. Web of Science, Google Scholar
10. W. Chen, H. Ji and Y. You, An augmented Lagrangian method for l1-regularized optimization problems with orthogonality constraints, SIAM J. Sci. Comput. 38(4) (2016) B570–B592. Web of Science, Google Scholar
11. P. L. Combettes and J.-C. Pesquet, A proximal decomposition method for solving convex variational inverse problems, Inverse Probl. 24(6) (2008) 065014. Web of Science, Google Scholar
12. L. Condat, A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optimiz. Theory Appl. 158(2) (2013) 460–479. Web of Science, Google Scholar
13. M. Elad and M. Aharon, Image denoising via sparse and redundant representations over learned dictionaries, IEEE Trans. Image Process. 15(12) (2006) 3736–3745. Web of Science, Google Scholar
14. M. Elad, P. Milanfar and R. Rubinstein, Analysis versus synthesis in signal priors, Inverse Probl. 23(3) (2007) 947. Web of Science, Google Scholar
15. M. A. Figueiredo and J. M. Bioucas-Dias, Restoration of Poissonian images using alternating direction optimization, IEEE Trans. Image Process. 19(12) (2010) 3133–3145. Web of Science, Google Scholar
16. D. Goldfarb, S. Ma and K. Scheinberg, Fast alternating linearization methods for minimizing the sum of two convex functions, Math. Program. 141(1–2) (2013) 349–382. Web of Science, Google Scholar
17. B. He and X. Yuan, On the O(1/n) convergence rate of the Douglas–Rachford alternating direction method, SIAM J. Numer. Anal. 50(2) (2012) 700–709. Web of Science, Google Scholar
18. N. Komodakis and J.-C. Pesquet, Playing with duality: An overview of recent primal-dual approaches for solving large-scale optimization problems, IEEE Signal Process. Mag. 32(6) (2015) 31–54. Web of Science, Google Scholar
19. J.-J. Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France 93 (1965) 273–299. Google Scholar
20. A. Padcharoen, P. Kumam and J. Martinez-Moreno, Augmented Lagrangian method for TV- $l_{1}$ $l_{1}$ - $l_{2}$ $l_{2}$ based color image restoration, J. Comput. Appl. Math. 354 (2019) 507–519. Web of Science, Google Scholar
21. N. Parikh and S. Boyd, Proximal algorithms, Found. Trends Optimiz. 1(3) (2014) 127–239. Google Scholar
22. G. Pierra, Decomposition through formalization in a product space, Math. Program. 28(1) (1984) 96–115. Web of Science, Google Scholar
23. L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, Nonlinear Phenom. 60(1) (1992) 259–268. Web of Science, Google Scholar
24. W. Wang, F. Li and M. K. Ng, Structural similarity-based nonlocal variational models for image restoration, IEEE Trans. Image Process. 28(9) (2019) 4260–4272. Web of Science, Google Scholar
25. W. Xia and D. Hatzinakos, An efficient projected subgradient algorithm for blind image deconvolution using an L1-TV cost function, IEEE Int. Conf. Image Processing (ICIP) (Orlando, FL, 2012), pp. 3045–3048, https://doi.org/10.1109/ICIP.2012.6467542. Google Scholar
26. L. Xie, M. Yin, X. Yin, Y. Liu and G. Yin, Low-rank sparse preserving projections for dimensionality reduction, IEEE Trans. Image Process. 27(11) (2018) 5261–5274. Web of Science, Google Scholar
27. J. Xu, Y. Tian, Y. Sun and G. Scutari, Accelerated primal-dual algorithms for distributed smooth convex optimization over networks, Proc. Mach. Learn. Res. 108 (2020) 2381–2391. Google Scholar
28. Y. Yang, J. Sun, H. Li and Z. Xu, ADMM-CSNet: A deep learning approach for image compressive sensing, IEEE Trans. Pattern Anal. Mach. Intell. 42(3) (2020) 521–538. Web of Science, Google Scholar
29. G. Yuan and B. Ghanem, $l_{0}$ $l_{0}$ TV: A sparse optimization method for impulse noise image restoration, IEEE Trans. Pattern Anal. Mach. Intell. 41(2) (2019) 352–364. Web of Science, Google Scholar
30. C. Zeng, C. Wu and R. Jia, Non-Lipschitz models for image restoration with impulse noise removal, SIAM J. Imag. Sci. 12(1) (2019) 420–458. Web of Science, Google Scholar
31. M. Zhu and T. Chan, An efficient primal–dual hybrid gradient algorithm for total variation image restoration, UCLA CAM Report (2008) 8–34. Google Scholar
32. W. Zuo, D. Ren, D. Zhang, S. Gu and L. Zhang, Learning iteration-wise generalized Shrinkage-Thresholding operators for blind deconvolution, IEEE Trans. Image Process. 25(4) (2016) 1751–1764. Web of Science, Google Scholar