\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author: Yuchao Tang

    * Corresponding author: Yuchao Tang 
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
  • 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.

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

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Test image. (a) The original image; (b) The noise image

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

    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

    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

    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} $
    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$ \% $
    $ \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$ \% $
    $ \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
    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 $
    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
  • [1] M. A. AlghamdiA. AlotaibiP. 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. AlotaibiP. 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. BeckerJ. 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. BoydN. ParikhE. ChuB. 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. ChenL. ShenY. 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. FangB. HeH. 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. GoncalvesM. 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. LiuD. 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. MicchelliL. ShenY. 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. RaguetJ. 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. SidkyJ. 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. TangG. 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. TangC. X. ZhuM. 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. WangA. C. BovikH. 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.
  • 加载中

Figures(4)

Tables(4)

SHARE

Article Metrics

HTML views(742) PDF downloads(463) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return