Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing


Authors: Deren Han, Xiaoming Yuan and Wenxing Zhang
Journal: Math. Comp. 83 (2014), 2263-2291
MSC (2010): Primary 90C06, 90C25, 94A08
DOI: https://doi.org/10.1090/S0025-5718-2014-02829-9
Published electronically: April 1, 2014
MathSciNet review: 3223332
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper considers the convex minimization problem with linear constraints and a separable objective function which is the sum of many individual functions without coupled variables. An algorithm is developed by splitting the augmented Lagrangian function in a parallel way. The new algorithm differs substantially from existing splitting methods in alternating style which require solving the decomposed subproblems sequentially, while it remains the main superiority of existing splitting methods in that the resulting subproblems could be simple enough to have closed-form solutions for such an application whose functions in the objective are simple. We show applicability and encouraging efficiency of the new algorithm by some applications in image processing.


References [Enhancements On Off] (What's this?)

  • [1] Manya V. Afonso, José M. Bioucas-Dias, and Mário A. T. Figueiredo, Fast image recovery using variable splitting and constrained optimization, IEEE Trans. Image Process. 19 (2010), no. 9, 2345-2356. MR 2798930 (2011k:94012), https://doi.org/10.1109/TIP.2010.2047910
  • [2] Manya V. Afonso, José M. Bioucas-Dias, and Mário A. T. Figueiredo, An augmented Lagrangian approach to the constrained optimization formulation of imaging inverse problems, IEEE Trans. Image Process. 20 (2011), no. 3, 681-695. MR 2799178, https://doi.org/10.1109/TIP.2010.2076294
  • [3] Hédy Attouch, Luis M. Briceño-Arias, and Patrick L. Combettes, A parallel splitting method for coupled monotone inclusions, SIAM J. Control Optim. 48 (2009/10), no. 5, 3246-3270. MR 2599918 (2011c:90121), https://doi.org/10.1137/090754297
  • [4] Johnathan M. Bardsley, Sarah Knepper, and James Nagy, Structured linear algebra problems in adaptive optics imaging, Adv. Comput. Math. 35 (2011), no. 2-4, 103-117. MR 2827082, https://doi.org/10.1007/s10444-011-9172-9
  • [5] Stephen Becker, Jérôme Bobin, and Emmanuel J. Candès, NESTA: a fast and accurate first-order method for sparse recovery, SIAM J. Imaging Sci. 4 (2011), no. 1, 1-39. MR 2765668 (2011m:90087), https://doi.org/10.1137/090756855
  • [6] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and distributed computation: Numerical methods, Prentice-Hall, Englewood Cliffs, New Jersey, NJ, 1989.
  • [7] E. Blum and W. Oettli, Mathematische Optimierung, Springer-Verlag, Berlin, 1975. Grundlagen und Verfahren; Mit einem Anhang ``Bibliographie zur Nichtlinearer Programmierung''; Ökonometrie und Unternehmensforschung, No. XX. MR 0418921 (54 #6956)
  • [8] N. Bose and K. Boo, High-resolution image reconstruction with multisensors, Int. J. Imag. Syst. Tech., 9 (1998), pp. 294-304.
  • [9] 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 (2010), pp. 1-122.
  • [10] Jian-Feng Cai, Raymond H. Chan, and Mila Nikolova, Two-phase approach for deblurring images corrupted by impulse plus Gaussian noise, Inverse Probl. Imaging 2 (2008), no. 2, 187-204. MR 2395140 (2009c:94002), https://doi.org/10.3934/ipi.2008.2.187
  • [11] Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for compressed sensing, Math. Comp. 78 (2009), no. 267, 1515-1536. MR 2501061 (2010e:65086), https://doi.org/10.1090/S0025-5718-08-02189-3
  • [12] Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for frame-based image deblurring, SIAM J. Imaging Sci. 2 (2009), no. 1, 226-252. MR 2486529 (2010h:94041), https://doi.org/10.1137/080733371
  • [13] Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright, Robust principal component analysis?, J. ACM 58 (2011), no. 3, Art. 11, 37. MR 2811000 (2012f:65064), https://doi.org/10.1145/1970392.1970395
  • [14] Antonin Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vision 20 (2004), no. 1-2, 89-97. Special issue on mathematics and image analysis. MR 2049783 (2005m:49058), https://doi.org/10.1023/B:JMIV.0000011320.81911.38
  • [15] Tony F. Chan and Selim Esedoglu, Aspects of total variation regularized $ L^1$ function approximation, SIAM J. Appl. Math. 65 (2005), no. 5, 1817-1837. MR 2177726 (2006k:94003), https://doi.org/10.1137/040604297
  • [16] Venkat Chandrasekaran, Sujay Sanghavi, Pablo A. Parrilo, and Alan S. Willsky, Rank-sparsity incoherence for matrix decomposition, SIAM J. Optim. 21 (2011), no. 2, 572-596. MR 2817479 (2012m:90128), https://doi.org/10.1137/090761793
  • [17] Gong Chen and Marc Teboulle, A proximal-based decomposition method for convex minimization problems, Math. Programming 64 (1994), no. 1, Ser. A, 81-101. MR 1274173 (95e:90069), https://doi.org/10.1007/BF01582566
  • [18] Patrick L. Combettes and Valérie R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul. 4 (2005), no. 4, 1168-1200 (electronic). MR 2203849 (2007g:94016), https://doi.org/10.1137/050626090
  • [19] J. Duchi, S. Gould, and D. Koller, Projected subgradient methods for learning sparse Gaussian, Conference on Uncertainty in Artificial Intelligence (UAI 2008), 2008.
  • [20] Jonathan Eckstein and B. F. Svaiter, General projective splitting methods for sums of maximal monotone operators, SIAM J. Control Optim. 48 (2009), no. 2, 787-811. MR 2486094 (2009k:47143), https://doi.org/10.1137/070698816
  • [21] F. Facchinei and J. S. Pang, Finite-dimensional variational inequalities and complementarity problems, Volumes I and II, Berlin, Springer Verlag, 2003.
  • [22] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl., 2 (1976), pp. 17-40.
  • [23] R. Glowinski and A. Marrocco, Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité, d'une classe de problèmes de Dirichlet non linéaires, Rev. Française Automat. Informat. Recherche Opérationnelle RAIRO Analyse Numérique 9 (1975), no. R-2, 41-76 (French, with Loose English summary). MR 0388811 (52 #9645)
  • [24] D. Goldfarb and S. Q. Ma, and K. Scheinberg, Fast alternating linearization methods for minimizing the sum of two convex functions, Math. Program., (2012). DOI 10.1007/s10107-012-0530-2.xx
  • [25] Donald Goldfarb and Shiqian Ma, Fast multiple-splitting algorithms for convex optimization, SIAM J. Optim. 22 (2012), no. 2, 533-556. MR 2968865, https://doi.org/10.1137/090780705
  • [26] Tom Goldstein and Stanley Osher, The split Bregman method for $ L1$-regularized problems, SIAM J. Imaging Sci. 2 (2009), no. 2, 323-343. MR 2496060 (2010e:65087), https://doi.org/10.1137/080725891
  • [27] Deren Han and Xiaoming Yuan, A note on the alternating direction method of multipliers, J. Optim. Theory Appl. 155 (2012), no. 1, 227-238. MR 2983116, https://doi.org/10.1007/s10957-012-0003-z
  • [28] Per Christian Hansen, James G. Nagy, and Dianne P. O'Leary, Deblurring images, Fundamentals of Algorithms, vol. 3, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006. Matrices, spectra, and filtering. MR 2271138 (2008d:94007)
  • [29] Bing-Sheng He, Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities, Comput. Optim. Appl. 42 (2009), no. 2, 195-212. MR 2471396 (2010b:90152), https://doi.org/10.1007/s10589-007-9109-x
  • [30] B. S. He, X. L. Fu, and Z. K. Jiang, Proximal-point algorithm using a linear proximal term, J. Optim. Theory Appl. 141 (2009), no. 2, 299-319. MR 2500836 (2010i:90128), https://doi.org/10.1007/s10957-008-9493-0
  • [31] B. S. He, M. Tao, M. H. Xu, and X. M. Yuan, Alternating directions based contraction method for linearly constrained separable convex programming problems, Optimization, 62 (2013), no. 4, 573-596. MR 3056148
  • [32] B. S. He, M. Tao, and X. M. Yuan, A splitting method for separable convex programming, IMA J. Num. Anal., to appear.
  • [33] Bingsheng He, Min Tao, and Xiaoming Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim. 22 (2012), no. 2, 313-340. MR 2968856, https://doi.org/10.1137/110822347
  • [34] Magnus R. Hestenes, Multiplier and gradient methods, J. Optimization Theory Appl. 4 (1969), 303-320. MR 0271809 (42 #6690)
  • [35] M. Y. Hong and Z. Q. Luo, On the linear convergence of the alternating direction method of multipliers, manuscript, 2012.
  • [36] B. Huang, S. Q. Ma and D. Goldfarb, Accelerated linearized Bregman method, Under review in SIAM J. Imaging Sci., 2011.
  • [37] Y. M. Huang, M.K. Ng, and Y. W. Wen, Fast image restoration methods for impulse and Gaussian noise removal, IEEE Signal Process. Lett., 16 (2009), pp. 457-460.
  • [38] H. Hwang and A. Haddad, Adaptive median filters: new algorithms and results, IEEE Trans. Image Process., 4 (1995), pp. 499-502.
  • [39] Z. K. Jiang and X. M. Yuan, New parallel descent-like method for solving a class of variational inequalities, J. Optim. Theory Appl. 145 (2010), no. 2, 311-323. MR 2630080 (2011j:49011), https://doi.org/10.1007/s10957-009-9619-z
  • [40] R. M. Larsen, PROPACK-Software for large and sparse SVD calculations, Available from http://sun.stanford.edu/srmunk/PROPACK/.
  • [41] B. Martinet, Régularisation d'inéquations variationnelles par approximations successives, Rev. Française Informat. Recherche Opérationnelle 4 (1970), no. Ser. R-3, 154-158 (French). MR 0298899 (45 #7948)
  • [42] Michael K. Ng, Pierre Weiss, and Xiaoming Yuan, Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods, SIAM J. Sci. Comput. 32 (2010), no. 5, 2710-2736. MR 2684734 (2011i:65065), https://doi.org/10.1137/090774823
  • [43] Mila Nikolova, A variational approach to remove outliers and impulse noise, J. Math. Imaging Vision 20 (2004), no. 1-2, 99-120. Special issue on mathematics and image analysis. MR 2049784 (2005b:94006), https://doi.org/10.1023/B:JMIV.0000011920.58935.9c
  • [44] Stanley Osher, Yu Mao, Bin Dong, and Wotao Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci. 8 (2010), no. 1, 93-111. MR 2655902 (2011c:90098)
  • [45] Y. G. Peng, A. Ganesh, J. Wright, W. L. Xu, and Y. Ma, Robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Trans. Pattern Anal. Mach. Intel. 34 (2012), 2233-2246.
  • [46] M. J. D. Powell, A method for nonlinear constraints in minimization problems, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 283-298. MR 0272403 (42 #7284)
  • [47] W. K. Pratt, Digital Image Processing: PIKS Inside, 3rd Edition, John Wiley $ \&$ Sons, Inc, 2001.
  • [48] Z. W. Qin, D. Goldfarb and S. Q. Ma, An alternating direction method for total variation denoising, manuscript, 2011.
  • [49] R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683 (43 #445)
  • [50] L. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D., 60 (1992), pp. 259-268.
  • [51] S. Setzer, G. Steidl, and T. Tebuber, Deblurring Poissonian images by split Bregman techniques, J. Vis. Commun. Image R., 21 (2010), pp. 193-199.
  • [52] Jonathan E. Spingarn, Partial inverse of a monotone operator, Appl. Math. Optim. 10 (1983), no. 3, 247-265. MR 722489 (85b:47059), https://doi.org/10.1007/BF01448388
  • [53] Min Tao and Xiaoming Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim. 21 (2011), no. 1, 57-81. MR 2765489 (2011m:90089), https://doi.org/10.1137/100781894
  • [54] Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight, Sparsity and smoothness via the fused lasso, J. R. Stat. Soc. Ser. B Stat. Methodol. 67 (2005), no. 1, 91-108. MR 2136641, https://doi.org/10.1111/j.1467-9868.2005.00490.x
  • [55] Ewout van den Berg and Michael P. Friedlander, Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput. 31 (2008/09), no. 2, 890-912. MR 2466141 (2010b:90086), https://doi.org/10.1137/080714488
  • [56] Yilun Wang, Junfeng Yang, Wotao Yin, and Yin Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci. 1 (2008), no. 3, 248-272. MR 2486032 (2010e:68198), https://doi.org/10.1137/080724265
  • [57] Pierre Weiss, Laure Blanc-Féraud, and Gilles Aubert, Efficient schemes for total variation minimization under constraints in image processing, SIAM J. Sci. Comput. 31 (2009), no. 3, 2047-2080. MR 2516143 (2010f:65117), https://doi.org/10.1137/070696143
  • [58] Wotao Yin, Analysis and generalizations of the linearized Bregman model, SIAM J. Imaging Sci. 3 (2010), no. 4, 856-877. MR 2735964 (2011j:68172), https://doi.org/10.1137/090760350
  • [59] Xiaoqun Zhang, Martin Burger, Xavier Bresson, and Stanley Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM J. Imaging Sci. 3 (2010), no. 3, 253-276. MR 2679428 (2011m:65135), https://doi.org/10.1137/090746379
  • [60] Xiaoqun Zhang, Martin Burger, and Stanley Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput. 46 (2011), no. 1, 20-46. MR 2753250 (2012f:90120), https://doi.org/10.1007/s10915-010-9408-8

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C06, 90C25, 94A08

Retrieve articles in all journals with MSC (2010): 90C06, 90C25, 94A08


Additional Information

Deren Han
Affiliation: School of Mathematical Science, Nanjing Normal University, Nanjing 210023, People’s Republic of China
Email: handeren@njnu.edu.cn

Xiaoming Yuan
Affiliation: Corresponding author. Department of Mathematics, Hong Kong Baptist University, Kowloon, Hong Kong, People’s Republic of China
Email: xmyuan@hkbu.edu.hk

Wenxing Zhang
Affiliation: School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, People’s Republic of China
Email: wenxing84@gmail.com

DOI: https://doi.org/10.1090/S0025-5718-2014-02829-9
Keywords: Augmented Lagrangian method, convex programming, splitting method, parallel, image processing.
Received by editor(s): February 16, 2012
Received by editor(s) in revised form: December 1, 2012
Published electronically: April 1, 2014
Additional Notes: The first author was supported by NSFC Grants 11071122, 11171159, and 20103207110002 from MOE of China.
The second author was supported by the General Research Fund from Hong Kong Research Grants Council: HKBU203311.
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society