American Institute of Mathematical Sciences

Advanced
February  2011, 5(1): 237-261. doi: 10.3934/ipi.2011.5.237

Augmented Lagrangian method for total variation restoration with non-quadratic fidelity

Chunlin Wu 1, , Juyong Zhang 2, and  Xue-Cheng Tai 3,

1. 

Division of Mathematical Sciences, School of Physical & Mathematical Sciences, Nanyang Technological University, Singapore
2. 

Division of Computer Communications, School of Computer Engineering, Nanyang Technological University, Singapore
3. 

University of Bergen, University of Bergen Bergen, Norway

Received  December 2009 Revised  September 2010 Published  February 2011

Recently augmented Lagrangian method has been successfully applied to image restoration. We extend the method to total variation (TV) restoration models with non-quadratic fidelities. We will first introduce the method and present an iterative algorithm for TV restoration with a quite general fidelity. In each iteration, three sub-problems need to be solved, two of which can be very efficiently solved via Fast Fourier Transform (FFT) implementation or closed form solution. In general the third sub-problem need iterative solvers. We then apply our method to TV restoration with $L^1$ and Kullback-Leibler (KL) fidelities, two common and important data terms for deblurring images corrupted by impulsive noise and Poisson noise, respectively. For these typical fidelities, we show that the third sub-problem also has closed form solution and thus can be efficiently solved. In addition, convergence analysis of these algorithms are given. Numerical experiments demonstrate the efficiency of our method.
Keywords: impulsive noise, Poisson noise, Augmented Lagrangian method, TV-KL, convergence., TV-$L^1$, total variation.
Mathematics Subject Classification: 80M30, 80M50, 68U1.
Citation: Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237
References:
[1]

IEEE Trans. Signal Process., 40 (1992), 1548-1562. doi: 10.1109/78.139258.  Google Scholar

[2]

International Statistical Review, 72 (2004), 209-237. doi: 10.1111/j.1751-5823.2004.tb00234.x.  Google Scholar

[3]

IEEE Trans. Image Process., 7 (1998), 304-309. doi: 10.1109/83.661180.  Google Scholar

[4]

Academic Press, 2000. Google Scholar

[5]

Inverse Problems and Imaging, 2 (2008), 455-484. doi: 10.3934/ipi.2008.2.455.  Google Scholar

[6]

LNCS, 5567 (2009), 235-246. Google Scholar

[7]

J. Numer. Math., 17 (2009), 3-26. doi: 10.1515/JNUM.2009.002.  Google Scholar

[8]

IEEE Trans. Inform. Theory, 52 (2006), 489-509. doi: 10.1109/TIT.2005.862083.  Google Scholar

[9]

Ph.D thesis, UCLA, 2001. Google Scholar

[10]

Numer. Math., 76 (1997), 167-188. doi: 10.1007/s002110050258.  Google Scholar

[11]

J. Math. Imaging Vision, 20 (2004), 89-97. doi: 10.1023/B:JMIV.0000011321.19549.88.  Google Scholar

[12]

IEEE Trans. Image Process., 14 (2005), 1479-1485. doi: 10.1109/TIP.2005.852196.  Google Scholar

[13]

Int. J. Comput. Math., 84 (2007), 1183-1198. doi: 10.1080/00207160701450390.  Google Scholar

[14]

SIAM J. Sci. Comput., 20 (1999), 1964-1977. doi: 10.1137/S1064827596299767.  Google Scholar

[15]

SIAM J. Sci. Comput., 22 (2000), 503-516. doi: 10.1137/S1064827598344169.  Google Scholar

[16]

J. Visual Commun. Image Repres., 12 (2001), 422-435. doi: 10.1006/jvci.2001.0491.  Google Scholar

[17]

SIAM J. Appl. Math., 65 (2005), 1817-1837. doi: 10.1137/040604297.  Google Scholar

[18]

SIAM J. Sci. Comput., 20 (1998), pp. 33-61. doi: 10.1137/S1064827596304010.  Google Scholar

[19]

IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., 48 (2001), 784-789. Google Scholar

[20]

SIAM J. Imaging Sciences, 2 (2009), 1168-1189. doi: 10.1137/090758490.  Google Scholar

[21]

IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.  Google Scholar

[22]

SIAM, 1999.  Google Scholar

[23]

IEEE Trans. Image Process., 10 (2001), 242-251. doi: 10.1109/83.902289.  Google Scholar

[24]

E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman,, UCLA CAM Report, (): 09.   Google Scholar

[25]

in "IEEE Workshop on Statistical Signal Processing," Cardiff, (2009), 733-736. doi: 10.1109/SSP.2009.5278459.  Google Scholar

[26]

SIAM J. Sci. Comput., 27 (2006), 1881-1902. doi: 10.1137/040615079.  Google Scholar

[27]

SIAM, Philadelphia, 1989.  Google Scholar

[28]

SIAM J. Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891.  Google Scholar

[29]

J. Optim. Theory and Appl., 4 (1969), 303-320. doi: 10.1007/BF00927673.  Google Scholar

[30]

Computing, 76 (2006), 109-133. doi: 10.1007/s00607-005-0119-1.  Google Scholar

[31]

SIAM J. Optim., 13 (2002), 865-888. doi: 10.1137/S1052623401383558.  Google Scholar

[32]

SIAM Multi. Model. Simul., 7 (2008), 774-795. doi: 10.1137/070703533.  Google Scholar

[33]

IEEE Trans. Image Process., 4 (1995), 499-502. doi: 10.1109/83.370679.  Google Scholar

[34]

in "Proc. International Symposium on Biomedical Imaging (ISBI'04)," Arlington, (2004), 788-791. Google Scholar

[35]

Statist. Sinica, 9 (1999), 119-135.  Google Scholar

[36]

J. Math. Imaging Vision, 27 (2007), 257-263. doi: 10.1007/s10851-007-0652-y.  Google Scholar

[37]

Commun. Math. Sci., 7 (2009), 741-753.  Google Scholar

[38]

IEEE Trans. Image Process., 12 (2003), 1579-1590. doi: 10.1109/TIP.2003.819229.  Google Scholar

[39]

Int'l J. Computer Vision, 2005. Google Scholar

[40]

in "Geometric Properties from Incomplete Data," Springer, (2006), 335-352. doi: 10.1007/1-4020-3858-8_18.  Google Scholar

[41]

IEEE Trans. Image Process., 15 (2006), 1506-1516. doi: 10.1109/TIP.2005.871129.  Google Scholar

[42]

SIAM J. Num. Anal., 40 (2002), 965-994. doi: 10.1137/S0036142901389165.  Google Scholar

[43]

J. Math. Imaging Vision, 20 (2004), 99-120. doi: 10.1023/B:JMIV.0000011920.58935.9c.  Google Scholar

[44]

IEEE Trans. Nucl. Sci., 46 (1999), 2202-2210. doi: 10.1109/23.819305.  Google Scholar

[45]

IEEE Trans. Image Process., 12 (2003), 85-92. doi: 10.1109/TIP.2002.804278.  Google Scholar

[46]

in "Optimization"(ed. R. Fletcher), Academic Press, (1972), 283-298.  Google Scholar

[47]

Mathematical Programming, 5 (1973), 354-373. doi: 10.1007/BF01580138.  Google Scholar

[48]

Physica D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[49]

IEEE Trans. Image Process., 5 (1996), 1582-1586. doi: 10.1109/83.541429.  Google Scholar

[50]

Computing, 60 (1998), 1-27. doi: 10.1007/BF02684327.  Google Scholar

[51]

LNCS, 5567 (2009), 464-476. Google Scholar

[52]

J. Visual Commun. Image Repres., accepted (2009). Google Scholar

[53]

IEEE Trans. Medical Imaging, 1 (1982), 113-122. doi: 10.1109/TMI.1982.4307558.  Google Scholar

[54]

LNCS, 5567 (2009), 502-513. Google Scholar

[55]

IEEE Trans. Inf. Theor., 45 (1999), 846-852. doi: 10.1109/18.761328.  Google Scholar

[56]

SIAM J. Imaging Sciences, 1 (2008), 248-272. doi: 10.1137/080724265.  Google Scholar

[57]

SIAM J. Imaging Sciences, 3 (2010), 300-339. doi: 10.1137/090767558.  Google Scholar

[58]

SIAM J. Imaging Sciences, 2 (2009), 569-592. doi: 10.1137/080730421.  Google Scholar

[59]

SIAM J. Sci. Comput., 31 (2009), 2842-2865. doi: 10.1137/080732894.  Google Scholar

[60]

LNCS, 3752 (2005), 73-84. Google Scholar

[61]

Multi. Model. Simul., 6 (2007), 190-211. doi: 10.1137/060663027.  Google Scholar

[62]

SIAM J. Imaging Sciences, 1 (2008), 143-168. doi: 10.1137/070703983.  Google Scholar

[63]

SIAM J. Imaging Sciences, 3 (2010), 856-877. doi: 10.1137/090760350.  Google Scholar

[64]

IEEE Trans. Image Process., 9 (2000), 1723-1730. doi: 10.1109/83.869184.  Google Scholar

[65]

Inverse Problems, 25 (2009).  Google Scholar

[66]

M. Zhu and T. F. Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration,, UCLA CAM Report, (): 08.   Google Scholar

[67]

Comput. Optim. Appl., (2008). Available from: http://www.springerlink.com/content/l2k84n130x6l4332/. Google Scholar

show all references

References:
[1]

IEEE Trans. Signal Process., 40 (1992), 1548-1562. doi: 10.1109/78.139258.  Google Scholar

[2]

International Statistical Review, 72 (2004), 209-237. doi: 10.1111/j.1751-5823.2004.tb00234.x.  Google Scholar

[3]

IEEE Trans. Image Process., 7 (1998), 304-309. doi: 10.1109/83.661180.  Google Scholar

[4]

Academic Press, 2000. Google Scholar

[5]

Inverse Problems and Imaging, 2 (2008), 455-484. doi: 10.3934/ipi.2008.2.455.  Google Scholar

[6]

LNCS, 5567 (2009), 235-246. Google Scholar

[7]

J. Numer. Math., 17 (2009), 3-26. doi: 10.1515/JNUM.2009.002.  Google Scholar

[8]

IEEE Trans. Inform. Theory, 52 (2006), 489-509. doi: 10.1109/TIT.2005.862083.  Google Scholar

[9]

Ph.D thesis, UCLA, 2001. Google Scholar

[10]

Numer. Math., 76 (1997), 167-188. doi: 10.1007/s002110050258.  Google Scholar

[11]

J. Math. Imaging Vision, 20 (2004), 89-97. doi: 10.1023/B:JMIV.0000011321.19549.88.  Google Scholar

[12]

IEEE Trans. Image Process., 14 (2005), 1479-1485. doi: 10.1109/TIP.2005.852196.  Google Scholar

[13]

Int. J. Comput. Math., 84 (2007), 1183-1198. doi: 10.1080/00207160701450390.  Google Scholar

[14]

SIAM J. Sci. Comput., 20 (1999), 1964-1977. doi: 10.1137/S1064827596299767.  Google Scholar

[15]

SIAM J. Sci. Comput., 22 (2000), 503-516. doi: 10.1137/S1064827598344169.  Google Scholar

[16]

J. Visual Commun. Image Repres., 12 (2001), 422-435. doi: 10.1006/jvci.2001.0491.  Google Scholar

[17]

SIAM J. Appl. Math., 65 (2005), 1817-1837. doi: 10.1137/040604297.  Google Scholar

[18]

SIAM J. Sci. Comput., 20 (1998), pp. 33-61. doi: 10.1137/S1064827596304010.  Google Scholar

[19]

IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., 48 (2001), 784-789. Google Scholar

[20]

SIAM J. Imaging Sciences, 2 (2009), 1168-1189. doi: 10.1137/090758490.  Google Scholar

[21]

IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.  Google Scholar

[22]

SIAM, 1999.  Google Scholar

[23]

IEEE Trans. Image Process., 10 (2001), 242-251. doi: 10.1109/83.902289.  Google Scholar

[24]

E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman,, UCLA CAM Report, (): 09.   Google Scholar

[25]

in "IEEE Workshop on Statistical Signal Processing," Cardiff, (2009), 733-736. doi: 10.1109/SSP.2009.5278459.  Google Scholar

[26]

SIAM J. Sci. Comput., 27 (2006), 1881-1902. doi: 10.1137/040615079.  Google Scholar

[27]

SIAM, Philadelphia, 1989.  Google Scholar

[28]

SIAM J. Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891.  Google Scholar

[29]

J. Optim. Theory and Appl., 4 (1969), 303-320. doi: 10.1007/BF00927673.  Google Scholar

[30]

Computing, 76 (2006), 109-133. doi: 10.1007/s00607-005-0119-1.  Google Scholar

[31]

SIAM J. Optim., 13 (2002), 865-888. doi: 10.1137/S1052623401383558.  Google Scholar

[32]

SIAM Multi. Model. Simul., 7 (2008), 774-795. doi: 10.1137/070703533.  Google Scholar

[33]

IEEE Trans. Image Process., 4 (1995), 499-502. doi: 10.1109/83.370679.  Google Scholar

[34]

in "Proc. International Symposium on Biomedical Imaging (ISBI'04)," Arlington, (2004), 788-791. Google Scholar

[35]

Statist. Sinica, 9 (1999), 119-135.  Google Scholar

[36]

J. Math. Imaging Vision, 27 (2007), 257-263. doi: 10.1007/s10851-007-0652-y.  Google Scholar

[37]

Commun. Math. Sci., 7 (2009), 741-753.  Google Scholar

[38]

IEEE Trans. Image Process., 12 (2003), 1579-1590. doi: 10.1109/TIP.2003.819229.  Google Scholar

[39]

Int'l J. Computer Vision, 2005. Google Scholar

[40]

in "Geometric Properties from Incomplete Data," Springer, (2006), 335-352. doi: 10.1007/1-4020-3858-8_18.  Google Scholar

[41]

IEEE Trans. Image Process., 15 (2006), 1506-1516. doi: 10.1109/TIP.2005.871129.  Google Scholar

[42]

SIAM J. Num. Anal., 40 (2002), 965-994. doi: 10.1137/S0036142901389165.  Google Scholar

[43]

J. Math. Imaging Vision, 20 (2004), 99-120. doi: 10.1023/B:JMIV.0000011920.58935.9c.  Google Scholar

[44]

IEEE Trans. Nucl. Sci., 46 (1999), 2202-2210. doi: 10.1109/23.819305.  Google Scholar

[45]

IEEE Trans. Image Process., 12 (2003), 85-92. doi: 10.1109/TIP.2002.804278.  Google Scholar

[46]

in "Optimization"(ed. R. Fletcher), Academic Press, (1972), 283-298.  Google Scholar

[47]

Mathematical Programming, 5 (1973), 354-373. doi: 10.1007/BF01580138.  Google Scholar

[48]

Physica D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[49]

IEEE Trans. Image Process., 5 (1996), 1582-1586. doi: 10.1109/83.541429.  Google Scholar

[50]

Computing, 60 (1998), 1-27. doi: 10.1007/BF02684327.  Google Scholar

[51]

LNCS, 5567 (2009), 464-476. Google Scholar

[52]

J. Visual Commun. Image Repres., accepted (2009). Google Scholar

[53]

IEEE Trans. Medical Imaging, 1 (1982), 113-122. doi: 10.1109/TMI.1982.4307558.  Google Scholar

[54]

LNCS, 5567 (2009), 502-513. Google Scholar

[55]

IEEE Trans. Inf. Theor., 45 (1999), 846-852. doi: 10.1109/18.761328.  Google Scholar

[56]

SIAM J. Imaging Sciences, 1 (2008), 248-272. doi: 10.1137/080724265.  Google Scholar

[57]

SIAM J. Imaging Sciences, 3 (2010), 300-339. doi: 10.1137/090767558.  Google Scholar

[58]

SIAM J. Imaging Sciences, 2 (2009), 569-592. doi: 10.1137/080730421.  Google Scholar

[59]

SIAM J. Sci. Comput., 31 (2009), 2842-2865. doi: 10.1137/080732894.  Google Scholar

[60]

LNCS, 3752 (2005), 73-84. Google Scholar

[61]

Multi. Model. Simul., 6 (2007), 190-211. doi: 10.1137/060663027.  Google Scholar

[62]

SIAM J. Imaging Sciences, 1 (2008), 143-168. doi: 10.1137/070703983.  Google Scholar

[63]

SIAM J. Imaging Sciences, 3 (2010), 856-877. doi: 10.1137/090760350.  Google Scholar

[64]

IEEE Trans. Image Process., 9 (2000), 1723-1730. doi: 10.1109/83.869184.  Google Scholar

[65]

Inverse Problems, 25 (2009).  Google Scholar

[66]

M. Zhu and T. F. Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration,, UCLA CAM Report, (): 08.   Google Scholar

[67]

Comput. Optim. Appl., (2008). Available from: http://www.springerlink.com/content/l2k84n130x6l4332/. Google Scholar

[1]

Yoon Mo Jung, Taeuk Jeong, Sangwoon Yun. Non-convex TV denoising corrupted by impulse noise. Inverse Problems & Imaging, 2017, 11 (4) : 689-702. doi: 10.3934/ipi.2017032
[2]

Feishe Chen, Lixin Shen, Yuesheng Xu, Xueying Zeng. The Moreau envelope approach for the L1/TV image denoising model. Inverse Problems & Imaging, 2014, 8 (1) : 53-77. doi: 10.3934/ipi.2014.8.53
[3]

Jia Li, Zuowei Shen, Rujie Yin, Xiaoqun Zhang. A reweighted $l^2$ method for image restoration with Poisson and mixed Poisson-Gaussian noise. Inverse Problems & Imaging, 2015, 9 (3) : 875-894. doi: 10.3934/ipi.2015.9.875
[4]

Michael Hintermüller, Monserrat Rincon-Camacho. An adaptive finite element method in $L^2$-TV-based image denoising. Inverse Problems & Imaging, 2014, 8 (3) : 685-711. doi: 10.3934/ipi.2014.8.685
[5]

Johnathan M. Bardsley. An efficient computational method for total variation-penalized Poisson likelihood estimation. Inverse Problems & Imaging, 2008, 2 (2) : 167-185. doi: 10.3934/ipi.2008.2.167
[6]

Liyan Ma, Lionel Moisan, Jian Yu, Tieyong Zeng. A stable method solving the total variation dictionary model with $L^\infty$ constraints. Inverse Problems & Imaging, 2014, 8 (2) : 507-535. doi: 10.3934/ipi.2014.8.507
[7]

Xi-Hong Yan. A new convergence proof of augmented Lagrangian-based method with full Jacobian decomposition for structured variational inequalities. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 45-54. doi: 10.3934/naco.2016.6.45
[8]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319
[9]

Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems & Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022
[10]

Denis R. Akhmetov, Renato Spigler. $L^1$-estimates for the higher-order derivatives of solutions to parabolic equations subject to initial values of bounded total variation. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1051-1074. doi: 10.3934/cpaa.2007.6.1051
[11]

Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems & Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591
[12]

Xueqin Li, Chao Tang, Tianmin Huang. Poisson $S^2$-almost automorphy for stochastic processes and its applications to SPDEs driven by Lévy noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (8) : 3309-3345. doi: 10.3934/dcdsb.2018282
[13]

C.M. Elliott, S. A. Smitheman. Analysis of the TV regularization and $H^{-1}$ fidelity model for decomposing animage into cartoon plus texture. Communications on Pure & Applied Analysis, 2007, 6 (4) : 917-936. doi: 10.3934/cpaa.2007.6.917
[14]

Mujibur Rahman Chowdhury, Jun Zhang, Jing Qin, Yifei Lou. Poisson image denoising based on fractional-order total variation. Inverse Problems & Imaging, 2020, 14 (1) : 77-96. doi: 10.3934/ipi.2019064
[15]

Jianhong (Jackie) Shen, Sung Ha Kang. Quantum TV and applications in image processing. Inverse Problems & Imaging, 2007, 1 (3) : 557-575. doi: 10.3934/ipi.2007.1.557
[16]

Yun Chen, Jiasheng Huang, Si Li, Yao Lu, Yuesheng Xu. A content-adaptive unstructured grid based integral equation method with the TV regularization for SPECT reconstruction. Inverse Problems & Imaging, 2020, 14 (1) : 27-52. doi: 10.3934/ipi.2019062
[17]

Mingchao Zhao, You-Wei Wen, Michael Ng, Hongwei Li. A nonlocal low rank model for poisson noise removal. Inverse Problems & Imaging, 2021, 15 (3) : 519-537. doi: 10.3934/ipi.2021003
[18]

Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2267-2281. doi: 10.3934/jimo.2019053
[19]

Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136
[20]

Wei Zhu, Xue-Cheng Tai, Tony Chan. Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Problems & Imaging, 2013, 7 (4) : 1409-1432. doi: 10.3934/ipi.2013.7.1409

2019 Impact Factor: 1.373

Tools

Metrics

  • PDF downloads (271)
  • HTML views (0)
  • Cited by (76)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences