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

Han, Deren; Yuan, Xiaoming; Zhang, Wenxing

doi:10.1090/S0025-5718-2014-02829-9

An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing
HTML articles powered by AMS MathViewer

by Deren Han, Xiaoming Yuan and Wenxing Zhang;

Math. Comp. 83 (2014), 2263-2291

DOI: https://doi.org/10.1090/S0025-5718-2014-02829-9

Published electronically: April 1, 2014

PDF | Request permission

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

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, DOI 10.1109/TIP.2010.2047910
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, DOI 10.1109/TIP.2010.2076294
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, DOI 10.1137/090754297
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, DOI 10.1007/s10444-011-9172-9
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, DOI 10.1137/090756855
D. P. Bertsekas and J. N. Tsitsiklis, Parallel and distributed computation: Numerical methods, Prentice-Hall, Englewood Cliffs, New Jersey, NJ, 1989.
E. Blum and W. Oettli, Mathematische Optimierung, Ökonometrie und Unternehmensforschung, Band XX, Springer-Verlag, Berlin-New York, 1975. Grundlagen und Verfahren; Mit einem Anhang “Bibliographie zur Nichtlinearer Programmierung”. MR 418921
N. Bose and K. Boo, High-resolution image reconstruction with multisensors, Int. J. Imag. Syst. Tech., 9 (1998), pp. 294–304.
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.
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, DOI 10.3934/ipi.2008.2.187
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for compressed sensing, Math. Comp. 78 (2009), no. 267, 1515–1536. MR 2501061, DOI 10.1090/S0025-5718-08-02189-3
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, DOI 10.1137/080733371
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, DOI 10.1145/1970392.1970395
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, DOI 10.1023/B:JMIV.0000011320.81911.38
Tony F. Chan and Selim Esedoḡlu, Aspects of total variation regularized $L^1$ function approximation, SIAM J. Appl. Math. 65 (2005), no. 5, 1817–1837. MR 2177726, DOI 10.1137/040604297
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, DOI 10.1137/090761793
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, DOI 10.1007/BF01582566
Patrick L. Combettes and Valérie R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul. 4 (2005), no. 4, 1168–1200. MR 2203849, DOI 10.1137/050626090
J. Duchi, S. Gould, and D. Koller, Projected subgradient methods for learning sparse Gaussian, Conference on Uncertainty in Artificial Intelligence (UAI 2008), 2008.
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, DOI 10.1137/070698816
F. Facchinei and J. S. Pang, Finite-dimensional variational inequalities and complementarity problems, Volumes I and II, Berlin, Springer Verlag, 2003.
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.
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 Sér. Rouge Anal. Numér. 9 (1975), no. R-2, 41–76 (French, with English summary). MR 388811
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
Donald Goldfarb and Shiqian Ma, Fast multiple-splitting algorithms for convex optimization, SIAM J. Optim. 22 (2012), no. 2, 533–556. MR 2968865, DOI 10.1137/090780705
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, DOI 10.1137/080725891
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, DOI 10.1007/s10957-012-0003-z
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, DOI 10.1137/1.9780898718874
Bing-Sheng He, Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities, Comput. Optim. Appl. 42 (2009), no. 2, 195–212. MR 2471396, DOI 10.1007/s10589-007-9109-x
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, DOI 10.1007/s10957-008-9493-0
Bingsheng He, Min Tao, Minghua Xu, and Xiaoming Yuan, An alternating direction-based contraction method for linearly constrained separable convex programming problems, Optimization 62 (2013), no. 4, 573–596. MR 3056148, DOI 10.1080/02331934.2011.611885
B. S. He, M. Tao, and X. M. Yuan, A splitting method for separable convex programming, IMA J. Num. Anal., to appear.
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, DOI 10.1137/110822347
Magnus R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl. 4 (1969), 303–320. MR 271809, DOI 10.1007/BF00927673
M. Y. Hong and Z. Q. Luo, On the linear convergence of the alternating direction method of multipliers, manuscript, 2012.
B. Huang, S. Q. Ma and D. Goldfarb, Accelerated linearized Bregman method, Under review in SIAM J. Imaging Sci., 2011.
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.
H. Hwang and A. Haddad, Adaptive median filters: new algorithms and results, IEEE Trans. Image Process., 4 (1995), pp. 499–502.
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, DOI 10.1007/s10957-009-9619-z
R. M. Larsen, PROPACK-Software for large and sparse SVD calculations, Available from http://sun.stanford.edu/srmunk/PROPACK/.
B. Martinet, Régularisation d’inéquations variationnelles par approximations successives, Rev. Française Informat. Recherche Opérationnelle 4 (1970), no. Sér, Sér. R-3, 154–158 (French). MR 298899
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, DOI 10.1137/090774823
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, DOI 10.1023/B:JMIV.0000011920.58935.9c
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
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.
M. J. D. Powell, A method for nonlinear constraints in minimization problems, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London-New York, 1969, pp. 283–298. MR 272403
W. K. Pratt, Digital Image Processing: PIKS Inside, 3rd Edition, John Wiley $\&$ Sons, Inc, 2001.
Z. W. Qin, D. Goldfarb and S. Q. Ma, An alternating direction method for total variation denoising, manuscript, 2011.
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970. MR 274683
L. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D., 60 (1992), pp. 259–268.
S. Setzer, G. Steidl, and T. Tebuber, Deblurring Poissonian images by split Bregman techniques, J. Vis. Commun. Image R., 21 (2010), pp. 193–199.
Jonathan E. Spingarn, Partial inverse of a monotone operator, Appl. Math. Optim. 10 (1983), no. 3, 247–265. MR 722489, DOI 10.1007/BF01448388
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, DOI 10.1137/100781894
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, DOI 10.1111/j.1467-9868.2005.00490.x
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, DOI 10.1137/080714488
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, DOI 10.1137/080724265
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, DOI 10.1137/070696143
Wotao Yin, Analysis and generalizations of the linearized Bregman model, SIAM J. Imaging Sci. 3 (2010), no. 4, 856–877. MR 2735964, DOI 10.1137/090760350
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, DOI 10.1137/090746379
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, DOI 10.1007/s10915-010-9408-8