Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications

Yixuan Yang; Yuchao Tang; Meng Wen; Tieyong Zeng

doi:10.3934/ipi.2021014

Article Contents

2021, Volume 15, Issue 4: 787-825. Doi: 10.3934/ipi.2021014

This issue Previous Article Synthetic-Aperture Radar image based positioning in GPS-denied environments using Deep Cosine Similarity Neural Networks Next Article

Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications

1.
Department of Mathematics, Nanchang University, Nanchang 330031, China
2.
School of Science, Xi'an Polytechnic University, Xi'an, 710048, China
3.
Department of Mathematics, The Chinese University of Hong Kong, Shatin, Hong Kong, China

^* Corresponding author: Yuchao Tang
^* Corresponding author: Yuchao Tang

Received: December 31, 2019

Revised: November 30, 2020

Early access: February 2021

Published: August 2021

The second author is supported by the National Natural Science Foundation of China (12061045, 11661056), the China Postdoctoral Science Foundation (2015M571989) and the Jiangxi Province Postdoctoral Science Foundation (2015KY51). The third author is supported by the National Natural Science Foundation of China (12001416)

Abstract Full Text(HTML) Figure(4) / Table(4) Related Papers Cited by

Abstract

This paper is concerned with the monotone inclusion involving the sum of a finite number of maximally monotone operators and the parallel sum of two maximally monotone operators with bounded linear operators. To solve this monotone inclusion, we first transform it into the formulation of the sum of three maximally monotone operators in a proper product space. Then we derive two efficient iterative algorithms, which combine the partial inverse method with the preconditioned Douglas-Rachford splitting algorithm and the preconditioned proximal point algorithm. Furthermore, we develop an iterative algorithm, which relies on the preconditioned Douglas-Rachford splitting algorithm without using the partial inverse method. We carefully analyze the theoretical convergence of the proposed algorithms. Finally, in order to demonstrate the effectiveness and efficiency of these algorithms, we conduct numerical experiments on a novel image denoising model for salt-and-pepper noise removal. Numerical results show the good performance of the proposed algorithms.

Keywords:

Mathematics Subject Classification: Primary: 90C25, 90C46; Secondary: 47A52.

Citation:

Full Text(HTML)

Figure 1. Test image. (a) The original image; (b) The noise image

Download: Full-size image PowerPoint slide

Figure 2. Original images. (a) "Barbara"; (b) "Building"

Download: Full-size image PowerPoint slide

Figure 3. Noisy and restored "Barbara" images. The first column is the noise images of "Barbara" with the noise level from $ 10 \% $ to $ 90 \% $; The second column is the results of the PADMM; The third column is the results of the PDCP; The forth column is the results of the proposed Algorithm 2

Download: Full-size image PowerPoint slide

Figure 4. Noisy and restored "Building" images. The first column is the noise images of "Building" with the noise level from $ 10 \% $ to $ 90 \% $; The second column is the results of the PADMM; The third column is the results of the PDCP; The forth column is the results of the proposed Algorithm 2

Download: Full-size image PowerPoint slide

Table 1. Numerical results of Algorithm 1, Algorithm 2 and Algorithm 3 for different selection of regularization parameters in terms of SNR, SSIM and the number of iterations (Iter)

Methods	$ \lambda_1 $	$ \lambda_2 $	$ \epsilon = 10^{-2} $			$ \epsilon = 10^{-4} $
Methods	$ \lambda_1 $	$ \lambda_2 $	SNR (dB)	SSIM	Iter	SNR (dB)	SSIM	Iter
Algorithm 1	$ 0 $	0.5	$ 4.4173 $	$ 0.0159 $	$ 149 $	$ 4.4648 $	$ 0.0162 $	$ - $
		$ 1 $	$ 4.4182 $	$ 0.0159 $	$ 147 $	$ 4.4749 $	$ 0.0162 $	$ - $
		$ 20 $	$ 53.0111 $	$ 0.9988 $	$ 738 $	$ 62.4224 $	$ 0.9999 $	$ - $
	$ 0.5 $	$ 0 $	$ 23.8749 $	$ 0.8813 $	$ 29 $	$ 24.3263 $	$ 0.9195 $	$ 110 $
	$ 1 $		$ 30.3788 $	$ 0.9340 $	$ 30 $	$ 34.3648 $	$ 0.9905 $	$ 151 $
	$ 2 $		$ 31.2330 $	$ 0.9331 $	$ 30 $	$ 52.4987 $	$ 0.9996 $	$ 276 $
	$ 0.5 $	$ 0.5 $	$ 27.2958 $	$ 0.9269 $	$ 24 $	$ 30.7593 $	$ 0.9837 $	$ 139 $
	$ 1 $	$ 1 $	$ 29.2181 $	$ 0.9434 $	$ 24 $	$ 47.8240 $	$ 0.9988 $	$ 135 $
	$ 2 $	$ 2 $	$ 29.3063 $	$ 0.9391 $	$ 25 $	$ 79.2541 $	$ 1 $	$ 210 $
Algorithm 2	$ 0 $	0.5	$ 4.5444 $	$ 0.0164 $	$ 24 $	$ 4.4263 $	$ 0.0159 $	$ 45 $
		$ 1 $	$ 4.5044 $	$ 0.0164 $	$ 25 $	$ 4.4260 $	$ 0.0159 $	$ 46 $
		$ 20 $	$ 32.8316 $	$ 0.9507 $	$ 33 $	$ 71.4020 $	$ 1 $	$ 89 $
	$ 0.5 $	$ 0 $	$ 21.2139 $	$ 0.0.7467 $	$ 42 $	$ 22.8320 $	$ 0.9143 $	$ 223 $
	$ 1 $		$ 27.0660 $	$ 0.7962 $	$ 49 $	$ 34.2508 $	$ 0.9903 $	$ 236 $
	$ 2 $		$ 26.9064 $	$ 0.7831 $	$ 50 $	$ 53.0912 $	$ 0.9996 $	$ 272 $
	$ 0.5 $	$ 0.5 $	$ 23.7828 $	$ 0.8072 $	$ 36 $	$ 30.5978 $	$ 0.9808 $	$ 168 $
	$ 1 $	$ 1 $	$ 28.3761 $	$ 0.8454 $	$ 35 $	$ 48.3065 $	$ 0.9990 $	$ 111 $
	$ 2 $	$ 2 $	$ 26.4981 $	$ 0.9092 $	$ 33 $	$ 76.5604 $	$ 1 $	$ 195 $
Algorithm 3	$ 0 $	0.5	$ 4.4169 $	$ 0.0159 $	$ 373 $	$ 4.4219 $	$ 0.0159 $	$ - $
		$ 1 $	$ 4.4246 $	$ 0.0159 $	$ 299 $	$ 4.4235 $	$ 0.0159 $	$ - $
		$ 20 $	$ 39.9637 $	$ 0.9762 $	$ - $	$ 39.9637 $	$ 0.9762 $	$ - $
	$ 0.5 $	$ 0 $	$ 23.1899 $	$ 0.9011 $	$ 61 $	$ 23.3077 $	$ 0.9151 $	$ 448 $
	$ 1 $		$ 32.4599 $	$ 0.9695 $	$ 49 $	$ 34.7962 $	$ 0.9913 $	$ 308 $
	$ 2 $		$ 35.2484 $	$ 0.9751 $	$ 53 $	$ 55.4857 $	$ 0.9998 $	$ 389 $
	$ 0.5 $	$ 0.5 $	$ 29.7816 $	$ 0.9611 $	$ 54 $	$ 30.7667 $	$ 0.9838 $	$ 512 $
	$ 1 $	$ 1 $	$ 35.3009 $	$ 0.9731 $	$ 43 $	$ 48.0544 $	$ 0.9989 $	$ 321 $
	$ 2 $	$ 2 $	$ 35.5435 $	$ 0.9767 $	$ 41 $	$ 85.6388 $	$ 1 $	$ 279 $

| Show Table

DownLoad: CSV

Table 2. Regularization parameters $ \lambda_1 $ and $ \lambda_2 $ for the PADMM (76) and Algorithm 2 under different noise levels

Images	10$ \% $		30$ \% $		50$ \% $		70$ \% $		90$ \% $
Images	$ \lambda_{1} $	$ \lambda_{2} $	$ \lambda_{1} $	$ \lambda_{2} $	$ \lambda_{1} $	$ \lambda_{2} $	$ \lambda_{1} $	$ \lambda_{2} $	$ \lambda_{1} $	$ \lambda_{2} $
Barbara	$ 0.3 $	$ 3.4 $	$ 0.4 $	$ 3.3 $	$ 0.5 $	$ 4.3 $	$ 0.6 $	$ 4.6 $	$ 0.7 $	$ 4.0 $
Building	$ 0.3 $	$ 5.8 $	$ 0.4 $	$ 5.6 $	$ 0.4 $	$ 8.4 $	$ 0.4 $	$ 10.2 $	$ 0.4 $	$ 10.5 $

| Show Table

DownLoad: CSV

Table 3. Regularization parameters $ \lambda_1 $ for the PDCP (77) under different noise levels

Images	10$ \% $	30$ \% $	50$ \% $	70$ \% $	90$ \% $
Images	$ \lambda_{1} $	$ \lambda_{1} $	$ \lambda_{1} $	$ \lambda_{1} $	$ \lambda_{1} $
Barbara	$ 0.4 $	$ 0.55 $	$ 0.75 $	$ 0.9 $	$ 1.2 $
Building	$ 0.4 $	$ 0.55 $	$ 0.7 $	$ 0.85 $	$ 1.15 $

| Show Table

DownLoad: CSV

Table 4. Numerical results of the PADMM (76), the PDCP (77) and the proposed Algorithm 2 for different noise levels in terms of SNR (dB), PSNR (dB), SSIM, number of iterations (Iter) and CPU time (in seconds)

Level	Methods	Barbara					Building
Level	Methods	SNR	PSNR	SSIM	Iter	CPU	SNR	PSNR	SSIM	Iter	CPU
10$ \% $	PADMM	$ 23.1733 $	$ 29.5804 $	$ 0.9210 $	$ 890 $	$ 186.60 $	$ 25.7280 $	$ 31.5560 $	$ 0.9418 $	$ 990 $	$ 200.47 $
	PDCP	$ 21.7728 $	$ 28.1799 $	$ 0.9015 $	$ 297 $	$ 21.47 $	$ 21.9205 $	$ 27.7484 $	$ 0.8984 $	$ 262 $	$ 18.86 $
	Algorithm 2	$ 23.1722 $	$ 29.5792 $	$ 0.9210 $	$ 122 $	$ 25.61 $	$ 25.7268 $	$ 31.5547 $	0.9418	$ 110 $	$ 23.91 $
30$ \% $	PADMM	18.9947	$ 25.4018 $	$ 0.7976 $	$ 1232 $	$ 241.68 $	$ 20.0999 $	$ 25.9278 $	$ 0.7996 $	$ 1356 $	$ 260.67 $
	PDCP	$ 18.0216 $	$ 24.4287 $	$ 0.7553 $	$ 686 $	$ 48.35 $	$ 18.1008 $	$ 23.9288 $	$ 0.7109 $	$ 688 $	$ 52.04 $
	Algorithm 2	$ 18.9937 $	$ 25.4008 $	$ 0.7981 $	$ 180 $	$ 37.26 $	$ 20.0902 $	$ 25.9181 $	$ 0.7988 $	$ 159 $	$ 33.12 $
50$ \% $	PADMM	$ 17.2073 $	$ 23.6144 $	$ 0.6889 $	$ 2804 $	$ 557.60 $	$ 17.6625 $	$ 23.4905 $	$ 0.6647 $	$ 2001 $	$ 397.35 $
	PDCP	$ 17.0137 $	$ 23.4205 $	$ 0.6700 $	$ 904 $	$ 64.98 $	$ 15.9925 $	$ 21.8204 $	$ 0.5546 $	$ 861 $	$ 59.20 $
	Algorithm 2	$ 17.2135 $	$ 23.6206 $	$ 0.6905 $	$ 210 $	$ 43.40 $	$ 17.6619 $	$ 23.4898 $	$ 0.6646 $	$ 169 $	$ 34.49 $
70$ \% $	PADMM	$ 15.8733 $	$ 22.2804 $	$ 0.5972 $	$ 2001 $	$ 789.97 $	$ 15.6335 $	$ 21.4615 $	$ 0.5067 $	$ 2001 $	$ 529.72 $
70$ \% $	PDCP	$ 15.6142 $	$ 22.0213 $	$ 0.5852 $	$ 1322 $	$ 93.27 $	$ 13.8911 $	$ 19.7190 $	$ 0.3736 $	$ 1360 $	$ 94.47 $
	Algorithm 2	$ 15.8856 $	$ 22.2927 $	$ 0.6000 $	$ 234 $	$ 47.93 $	$ 15.6387 $	$ 21.4666 $	$ 0.5070 $	$ 196 $	$ 41.08 $
90$ \% $	PADMM	$ 12.4587 $	$ 18.8658 $	$ 0.4401 $	$ 2001 $	$ 856.01 $	$ 12.4100 $	$ 18.2379 $	$ 0.2730 $	$ 2001 $	$ 569.67 $
	PDCP	$ 12.4733 $	$ 18.8804 $	$ 0.4617 $	$ 2278 $	$ 172.28 $	$ 11.7455 $	$ 17.5735 $	$ 0.2278 $	$ 1987 $	$ 134.76 $
	Algorithm 2	$ 12.4789 $	$ 18.8860 $	$ 0.4441 $	$ 362 $	$ 79.30 $	$ 12.4224 $	$ 18.2503 $	$ 0.2735 $	$ 332 $	$ 72.85 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	M. A. Alghamdi, A. Alotaibi, P. L. Combettes and N. Shahzad, A primal-dual method of partial inverses for composite inclusions, Optim. Lett., 8 (2014), 2271-2284. doi: 10.1007/s11590-014-0734-x.
[2]	A. Alliney, A property of the minimum vectors of a regularization functional defined by means of the absolute norm, IEEE Trans. Signal Process., 45 (1997), 913-917. doi: 10.1109/78.564179.
[3]	A. Alotaibi, P. L. Combettes and N. Shahzad, Solving coupled composite monotone inclusions by successive fejér approximations of their Kukn-Tucker set, SIAM J. Optim., 24 (2014), 2076-2095. doi: 10.1137/130950616.
[4]	H. Attouch and M. Soueycatt, Augmented lagrangian and proximal alternating direction methods of multipliers in hilbert spaces, applications to games, pde's and control, Pacific. J. Optim., 5 (2008), 17-37.
[5]	H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2$^nd$ edition, Springer, Cham, 2017. doi: 10.1007/978-3-319-48311-5.
[6]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202. doi: 10.1137/080716542.
[7]	A. Beck and M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process., 18 (2009), 2419-2434. doi: 10.1109/TIP.2009.2028250.
[8]	S. Becker, J. Bobin and E. J. Candès, NESTA: A fast and accurate first-order method for sparse recovery, SIAM J. Imaging Sci., 4 (2011), 1-39. doi: 10.1137/090756855.
[9]	S. R. Becker and P. L. Combettes, An algorithm for splitting parallel sums of linearly composed monotone operatos with applications to signal recovery, J. Nonlinear Convex Anal., 15 (2014), 137-159.
[10]	R. I. Boţ, E. R. Csetnek and A. Heinrich, A primal-dual splitting for finding zeros of sums of maximal monotone operators, SIAM J. Optim., 23 (2013), 2011-2036. doi: 10.1137/12088255X.
[11]	R. I. Boţ and C. Hendrich, Solving monotone inclusions involving parallel sums of linearly composed maximally monotone operators, Inverse Probl. Imaging, 10 (2016), 617-640. doi: 10.3934/ipi.2016014.
[12]	R. I. Boţ and C. Hendrich, Convergence analysis for a primal-dual monotone+skew splitting algorithm with applications to total variation minimization, J. Math. Imaging Vis., 49 (2014), 551-568. doi: 10.1007/s10851-013-0486-8.
[13]	R. I. Boţ and C. Hendrich, A Dougla-Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel -sum type monotone operators, SIAM J. Optim., 23 (2013), 2541-2565. doi: 10.1137/120901106.
[14]	S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distrituted optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2010), 1-122.
[15]	L. M. Briceño-Arias and P. L. Combettes, A monotone+skew splitting model for composite monotone inclusions in duality, SIAM J. Optim., 21 (2011), 1230-1250. doi: 10.1137/10081602X.
[16]	L. M. Briceño-Arias, Forward-Douglas-Rachford splitting and forward-partial inverse method for solving monotone inclusions, Optim., 64 (2015), 1239-1261. doi: 10.1080/02331934.2013.855210.
[17]	L. M. Briceño-Arias, Foward-partial inverse forward splitting for solving monotone inclusions, J. Optim. Theory Appl., 166 (2015), 391-413. doi: 10.1007/s10957-015-0703-2.
[18]	A. Cegielski, Iterative Methods for Fixed Point Problems in Hilbert Spaces, Springer-Verlag, Berlin Heidelberg, 2012.
[19]	A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.
[20]	A. Chambolle and T. Pock, An introduction to continuous optimization for imaging, Acta Numer., 25 (2016), 161-319. doi: 10.1017/S096249291600009X.
[21]	F. Chen, L. Shen, Y. Xu and X. Zeng, The moreau envelope approach for the l1/TV image denoising model, Inverse Probl. Imaging, 8 (2014), 53-77. doi: 10.3934/ipi.2014.8.53.
[22]	P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4 (2005), 1168-1200. doi: 10.1137/050626090.
[23]	P. L. Combettes and J.-C. Pesquet, A Douglas-Rachford splitting approach to nonsmooth conve variational signal recovery, IEEE J. Sel. Top. Signal Process, 1 (2007), 564-574. doi: 10.1109/JSTSP.2007.910264.
[24]	P. L. Combettes and J.-C. Pesquet, Primal-dual splitting algorithm for solving inclusions with mixtures of composite, lipschitzian, and parallel-sum type monotone operators, Set-Valued Var. Anal., 20 (2012), 307-330. doi: 10.1007/s11228-011-0191-y.
[25]	P. L. Combettes and B. C. Vũ, Variable metric forward-backward splitting with applications to monotone inclusions in duality, Optim., 63 (2014), 1289-1318. doi: 10.1080/02331934.2012.733883.
[26]	P. L. Combettes and J. Eckstein, Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions, Math. Program., 168 (2018), 645-672. doi: 10.1007/s10107-016-1044-0.
[27]	P. L. Combettes, Systems of structured monotone inclusions: Duality, algorithms, and applications, SIAM J. Optim., 23 (2013), 2420-2447. doi: 10.1137/130904160.
[28]	P. L. Combettes, Iterative construction of the resolvent of a sum of maximal monotone operators, J. Convex Anal., 16 (2009), 727-748.
[29]	L. Condat, A primal-dual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl., 158 (2013), 460-479. doi: 10.1007/s10957-012-0245-9.
[30]	E. X. Fang, B. He, H. Liu and X. Yuan, Generalized alternating direction method of multipliers: new theoretical insights and applications, Math. Program. Comput., 7 (2015), 149-187. doi: 10.1007/s12532-015-0078-2.
[31]	M. L. N. Goncalves, M. M. Alves and J. G. Melo, Pointwise and ergodic convergence rates of variable metric proximal alternating direction method of multipliers, J. Optim. Theory Appl., 177 (2018), 448-478. doi: 10.1007/s10957-018-1232-6.
[32]	P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), 964-979. doi: 10.1137/0716071.
[33]	Y.-J. Liu, D. Sun and K.-C. Toh, An implementable proximal point algorithmic framework for nuclear norm minimization, Math. Program., 133 (2012), 399-436. doi: 10.1007/s10107-010-0437-8.
[34]	C. A. Micchelli, L. Shen, Y. Xu and X. Zeng, Proximity algorithms for the l1/TV image denoising model, Adv. Comput. Math., 38 (2013), 401-426. doi: 10.1007/s10444-011-9243-y.
[35]	C. A. Micchelli, L. Shen and Y. Xu, Proximity algorithms for image models: Denoising, Inverse Probl., 27 (2011), 045009, 30 pp. doi: 10.1088/0266-5611/27/4/045009.
[36]	M. Nikolova, A variational approach to remove outliers and impulse noise, J. Math. Imaging Vis., 20 (2004), 99-120.
[37]	H. Raguet, J. Fadili and G. Peyré, A generalized forward-backward splitting, SIAM J. Imaging Sci., 6 (2013), 1199-1226. doi: 10.1137/120872802.
[38]	H. Raguet and L. Landrieu, Preconditioning of a generalized forward-backward splitting and application to optimization on graphs, SIAM J. Imaging Sci., 8 (2015), 2706-2739. doi: 10.1137/15M1018253.
[39]	H. Raguet, A note on the forward-Douglas-Rachford splitting for monotone inclusion and convex optimization, Optim. Lett., 13 (2019), 717-740. doi: 10.1007/s11590-018-1272-8.
[40]	R. Shefi and M. Teboulle, Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM J. Optim., 24 (2014), 269-297. doi: 10.1137/130910774.
[41]	E. Y. Sidky, J. H. Jørgensen and X. Pan, Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle-Pock algorithm, Phys. Med. Biol., 57 (2012), 3065-3091. doi: 10.1088/0031-9155/57/10/3065.
[42]	J. E. Spingarn, Partial inverse of a monotone operator, Appl. Math. Optim., 10 (1983), 247-265. doi: 10.1007/BF01448388.
[43]	J. E. Spingarn, Applications of the method of partial inverses to convex programming: Decomposition, Math. Programming, 32 (1985), 199-223. doi: 10.1007/BF01586091.
[44]	Y. C. Tang, G. R. Wu and C. X. Zhu, An inner-outer iteration method for solving convex optimization problems involving the sum of three convex functions (in chinese), Sci. Sic. Math., 49 (2019), 831-858. doi: 10.1360/SCM-2017-0313.
[45]	Y. C. Tang, C. X. Zhu, M. Wen and J. G. Peng, A splitting primal-dual proximity algorithm for solving composite optimization problems, Acta. Math. Sin.-English Ser., 33 (2017), 868-886. doi: 10.1007/s10114-016-5625-x.
[46]	P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim., 38 (2000), 431-446. doi: 10.1137/S0363012998338806.
[47]	B. C. Vũ, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comput. Math., 38 (2013), 667-681. doi: 10.1007/s10444-011-9254-8.
[48]	Z. Wang, A. C. Bovik, H. R. Sheikh and E. P. Simoncelli, Image quality assessment: From error visibility to structural similarity, IEEE Trans. Image Process., 13 (2004), 600-612. doi: 10.1109/TIP.2003.819861.
[49]	C. Zong, Y. Tang and Y. J. Cho, Convergence analysis of an inexact three-operator splitting algorithm, Symmetry, 10 (2018), 563. doi: 10.3390/sym10110563.