Skip to main content
Erschienen in: Journal of Scientific Computing 2/2019

20.08.2018

A Nonconvex Model with Minimax Concave Penalty for Image Restoration

verfasst von: Juntao You, Yuling Jiao, Xiliang Lu, Tieyong Zeng

Erschienen in: Journal of Scientific Computing | Ausgabe 2/2019

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A natural image u is often sparse under a given transformation W, one can use \(L_0\) norm of Wu as a regularisation term in image reconstructions. Since minimizing the \(L_0\) norm is a NP hard problem, the \(L_1\) norm is widely used as an replacement. However, recent studies show that nonconvex penalties, e.g., MCP, enjoy better performance for sparse signal recovery. In this paper, we propose a nonconvex model for image restoration with a minimax concave penalty (MCP). First we establish the existence of a global minimizer for the nonconvex model. Then we solve this model by using the alternating direction method of multipliers algorithm. The convergence of the proposed algorithm is analysed with properly chosen parameters. Numerical experiments show that the MCP model outperforms TV model in terms of efficiency and accuracy.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka–Łojasiewicz inequality. Math. Oper. Res. 35(2), 438–457 (2010)MathSciNetMATHCrossRef Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka–Łojasiewicz inequality. Math. Oper. Res. 35(2), 438–457 (2010)MathSciNetMATHCrossRef
2.
Zurück zum Zitat Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1–2), 459–494 (2014)MathSciNetMATHCrossRef Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1–2), 459–494 (2014)MathSciNetMATHCrossRef
3.
Zurück zum Zitat Boyd, S.: Alternating direction method of multipliers. Talk at NIPS Workshop on Optimization and Machine Learning (2011) Boyd, S.: Alternating direction method of multipliers. Talk at NIPS Workshop on Optimization and Machine Learning (2011)
4.
Zurück zum Zitat Cai, J., Chan, R.H., Shen, L., Shen, Z.: Convergence analysis of tight framelet approach for missing data recovery. Adv. Comput. Math. 31(1), 87–113 (2009)MathSciNetMATHCrossRef Cai, J., Chan, R.H., Shen, L., Shen, Z.: Convergence analysis of tight framelet approach for missing data recovery. Adv. Comput. Math. 31(1), 87–113 (2009)MathSciNetMATHCrossRef
5.
Zurück zum Zitat Cai, J.-F., Osher, S., Shen, Z.: Split Bregman methods and frame based image restoration. Multiscale Model. Simul. 8(2), 337–369 (2009)MathSciNetMATHCrossRef Cai, J.-F., Osher, S., Shen, Z.: Split Bregman methods and frame based image restoration. Multiscale Model. Simul. 8(2), 337–369 (2009)MathSciNetMATHCrossRef
6.
Zurück zum Zitat Cai, X., Chan, R., Zeng, T.: A two-stage image segmentation method using a convex variant of the Mumford–Shah model and thresholding. SIAM J. Imaging Sci. 6(1), 368–390 (2013)MathSciNetMATHCrossRef Cai, X., Chan, R., Zeng, T.: A two-stage image segmentation method using a convex variant of the Mumford–Shah model and thresholding. SIAM J. Imaging Sci. 6(1), 368–390 (2013)MathSciNetMATHCrossRef
7.
Zurück zum Zitat Candes, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207–1223 (2006)MathSciNetMATHCrossRef Candes, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207–1223 (2006)MathSciNetMATHCrossRef
8.
Zurück zum Zitat Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1), 89–97 (2004)MathSciNetMATH Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1), 89–97 (2004)MathSciNetMATH
9.
Zurück zum Zitat Chambolle, A., Caselles, V., Cremers, D., Novaga, M., Pock, T.: An introduction to total variation for image analysis. Theor. Found. Numer. Methods Sparse Recovery 9(263–340), 227 (2010)MathSciNetMATH Chambolle, A., Caselles, V., Cremers, D., Novaga, M., Pock, T.: An introduction to total variation for image analysis. Theor. Found. Numer. Methods Sparse Recovery 9(263–340), 227 (2010)MathSciNetMATH
10.
Zurück zum Zitat Chan, R.H., Riemenschneider, S.D., Shen, L., Shen, Z.: Tight frame: an efficient way for high-resolution image reconstruction. Appl. Comput. Harmon. Anal. 17(1), 91–115 (2004)MathSciNetMATHCrossRef Chan, R.H., Riemenschneider, S.D., Shen, L., Shen, Z.: Tight frame: an efficient way for high-resolution image reconstruction. Appl. Comput. Harmon. Anal. 17(1), 91–115 (2004)MathSciNetMATHCrossRef
12.
13.
Zurück zum Zitat Chouzenoux, E., Jezierska, A., Pesquet, J.-C., Talbot, H.: A majorize–minimize subspace approach for \(\ell _2\)–\(\ell _0\) image regularization. SIAM J. Imaging Sci. 6(1), 563–591 (2013)MathSciNetMATHCrossRef Chouzenoux, E., Jezierska, A., Pesquet, J.-C., Talbot, H.: A majorize–minimize subspace approach for \(\ell _2\)\(\ell _0\) image regularization. SIAM J. Imaging Sci. 6(1), 563–591 (2013)MathSciNetMATHCrossRef
14.
Zurück zum Zitat Daubechies, I., Han, B., Ron, A., Shen, Z.: Framelets: MRA-based constructions of wavelet frames. Appl. Comput. Harmon. Anal. 14(1), 1–46 (2003)MathSciNetMATHCrossRef Daubechies, I., Han, B., Ron, A., Shen, Z.: Framelets: MRA-based constructions of wavelet frames. Appl. Comput. Harmon. Anal. 14(1), 1–46 (2003)MathSciNetMATHCrossRef
15.
Zurück zum Zitat Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889–916 (2016)MathSciNetMATHCrossRef Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889–916 (2016)MathSciNetMATHCrossRef
17.
Zurück zum Zitat Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1), 293–318 (1992)MathSciNetMATHCrossRef Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1), 293–318 (1992)MathSciNetMATHCrossRef
18.
Zurück zum Zitat Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split Bregman. CAM Rep. 9, 31 (2009) Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split Bregman. CAM Rep. 9, 31 (2009)
19.
Zurück zum Zitat Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348–1360 (2001). [MR 1946581 (2003k:62160)]MathSciNetMATHCrossRef Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348–1360 (2001). [MR 1946581 (2003k:62160)]MathSciNetMATHCrossRef
20.
Zurück zum Zitat Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348–1360 (2001)MathSciNetMATHCrossRef Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348–1360 (2001)MathSciNetMATHCrossRef
21.
Zurück zum Zitat Fan, J., Peng, H.: Nonconcave penalized likelihood with a diverging number of parameters. Ann. Stat. 32(3), 928–961 (2004). [MR 2065194 (2005g:62047)]MathSciNetMATHCrossRef Fan, J., Peng, H.: Nonconcave penalized likelihood with a diverging number of parameters. Ann. Stat. 32(3), 928–961 (2004). [MR 2065194 (2005g:62047)]MathSciNetMATHCrossRef
22.
Zurück zum Zitat Frank, L.L.E., Friedman, J.H.: A statistical view of some chemometrics regression tools. Technometrics 35(2), 109–135 (1993)MATHCrossRef Frank, L.L.E., Friedman, J.H.: A statistical view of some chemometrics regression tools. Technometrics 35(2), 109–135 (1993)MATHCrossRef
23.
Zurück zum Zitat Fu, S.J., Zhang, C.M., Tai, X.C.: Image denoising and deblurring: non-convex regularization, inverse diffusion and shock filter. Sci. China Inf. Sci. 54(6), 1184–1198 (2011)MathSciNetCrossRef Fu, S.J., Zhang, C.M., Tai, X.C.: Image denoising and deblurring: non-convex regularization, inverse diffusion and shock filter. Sci. China Inf. Sci. 54(6), 1184–1198 (2011)MathSciNetCrossRef
24.
Zurück zum Zitat Fu, W.J.: Penalized regressions: the bridge versus the lasso. J. Comput. Graph. Stat. 7(3), 397–416 (1998)MathSciNet Fu, W.J.: Penalized regressions: the bridge versus the lasso. J. Comput. Graph. Stat. 7(3), 397–416 (1998)MathSciNet
25.
Zurück zum Zitat Gabay, D.: Chapter ix applications of the method of multipliers to variational inequalities. Stud. Math. Appl. 15, 299–331 (1983)CrossRef Gabay, D.: Chapter ix applications of the method of multipliers to variational inequalities. Stud. Math. Appl. 15, 299–331 (1983)CrossRef
26.
Zurück zum Zitat Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1), 17–40 (1976)MATHCrossRef Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1), 17–40 (1976)MATHCrossRef
27.
Zurück zum Zitat Getreuer, P.: Rudin–Osher–Fatemi total variation denoising using split Bregman. Image Process. On Line 2, 74–95 (2012)CrossRef Getreuer, P.: Rudin–Osher–Fatemi total variation denoising using split Bregman. Image Process. On Line 2, 74–95 (2012)CrossRef
28.
Zurück zum Zitat Glowinski, R., Marroco, A.: 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. Revue française d’automatique, informatique, recherche opérationnelle. Anal. Numér. 9(2), 41–76 (1975)MathSciNetMATH Glowinski, R., Marroco, A.: 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. Revue française d’automatique, informatique, recherche opérationnelle. Anal. Numér. 9(2), 41–76 (1975)MathSciNetMATH
29.
30.
Zurück zum Zitat Hong, M., Luo, Z.-Q., Razaviyayn, M.: Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J. Optim. 26(1), 337–364 (2016)MathSciNetMATHCrossRef Hong, M., Luo, Z.-Q., Razaviyayn, M.: Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J. Optim. 26(1), 337–364 (2016)MathSciNetMATHCrossRef
31.
Zurück zum Zitat Jiao, Y., Jin, B., Lu, X., Ren, W.: A primal dual active set algorithm for a class of nonconvex sparsity optimization. arXiv preprint arXiv:1310.1147 (2013) Jiao, Y., Jin, B., Lu, X., Ren, W.: A primal dual active set algorithm for a class of nonconvex sparsity optimization. arXiv preprint arXiv:​1310.​1147 (2013)
32.
Zurück zum Zitat Lions, P.-L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979)MathSciNetMATHCrossRef Lions, P.-L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979)MathSciNetMATHCrossRef
33.
Zurück zum Zitat Lou, Y., Zeng, T., Osher, S., Xin, J.: A weighted difference of anisotropic and isotropic total variation model for image processing. SIAM J. Imaging Sci. 8(3), 1798–1823 (2015)MathSciNetMATHCrossRef Lou, Y., Zeng, T., Osher, S., Xin, J.: A weighted difference of anisotropic and isotropic total variation model for image processing. SIAM J. Imaging Sci. 8(3), 1798–1823 (2015)MathSciNetMATHCrossRef
34.
Zurück zum Zitat Mallat, S.G.: Multifrequency channel decompositions of images and wavelet models. IEEE Trans. Acoust. Speech Signal Process. 37(12), 2091–2110 (1989)CrossRef Mallat, S.G.: Multifrequency channel decompositions of images and wavelet models. IEEE Trans. Acoust. Speech Signal Process. 37(12), 2091–2110 (1989)CrossRef
35.
Zurück zum Zitat Mordukhovich, B.S., Shao, Y.: On nonconvex subdifferential calculus in banach spaces1. J. Convex Anal. 2(1/2), 211–227 (1995)MathSciNetMATH Mordukhovich, B.S., Shao, Y.: On nonconvex subdifferential calculus in banach spaces1. J. Convex Anal. 2(1/2), 211–227 (1995)MathSciNetMATH
36.
Zurück zum Zitat Moreau, J.-J.: Fonctions convexes duales et points proximaux dans un espace hilbertien. CR Acad. Sci. Paris Ser. A Math. 255, 2897–2899 (1962)MathSciNetMATH Moreau, J.-J.: Fonctions convexes duales et points proximaux dans un espace hilbertien. CR Acad. Sci. Paris Ser. A Math. 255, 2897–2899 (1962)MathSciNetMATH
37.
Zurück zum Zitat Moreau, J.-J.: Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. Fr. 93(2), 273–299 (1965)MATHCrossRef Moreau, J.-J.: Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. Fr. 93(2), 273–299 (1965)MATHCrossRef
38.
Zurück zum Zitat Nikolova, M.: Analysis of the recovery of edges in images and signals by minimizing nonconvex regularized least-squares. Multiscale Model. Simul. 4(3), 960–991 (2005)MathSciNetMATHCrossRef Nikolova, M.: Analysis of the recovery of edges in images and signals by minimizing nonconvex regularized least-squares. Multiscale Model. Simul. 4(3), 960–991 (2005)MathSciNetMATHCrossRef
39.
Zurück zum Zitat Nikolova, M.: Analytical bounds on the minimizers of (nonconvex) regularized least-squares. Inv. Probl. Imaging 1(4), 1–677 (2007) Nikolova, M.: Analytical bounds on the minimizers of (nonconvex) regularized least-squares. Inv. Probl. Imaging 1(4), 1–677 (2007)
40.
Zurück zum Zitat Nikolova, M., Ng, M.K., Zhang, S., Ching, W.-K.: Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization. SIAM J. Imaging Sci. 1(1), 2–25 (2008)MathSciNetMATHCrossRef Nikolova, M., Ng, M.K., Zhang, S., Ching, W.-K.: Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization. SIAM J. Imaging Sci. 1(1), 2–25 (2008)MathSciNetMATHCrossRef
41.
Zurück zum Zitat Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97–116 (1976)MathSciNetMATHCrossRef Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97–116 (1976)MathSciNetMATHCrossRef
42.
Zurück zum Zitat Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis, vol. 317. Springer, Berlin (2009)MATH Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis, vol. 317. Springer, Berlin (2009)MATH
43.
Zurück zum Zitat Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Phys. D Nonlinear Phenom. 60(1–4), 259–268 (1992)MathSciNetMATHCrossRef Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Phys. D Nonlinear Phenom. 60(1–4), 259–268 (1992)MathSciNetMATHCrossRef
44.
Zurück zum Zitat Setzer, S., Steidl, G., Teuber, T.: Deblurring Poissonian images by split Bregman techniques. J. Vis. Commun. Image Represent. 21(3), 193–199 (2010)CrossRef Setzer, S., Steidl, G., Teuber, T.: Deblurring Poissonian images by split Bregman techniques. J. Vis. Commun. Image Represent. 21(3), 193–199 (2010)CrossRef
45.
Zurück zum Zitat Sun, D., Sun, J., Zhang, L.: The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming. Math. Program. 114(2), 349–391 (2008)MathSciNetMATHCrossRef Sun, D., Sun, J., Zhang, L.: The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming. Math. Program. 114(2), 349–391 (2008)MathSciNetMATHCrossRef
46.
Zurück zum Zitat Tao, P.D., An, L.T.H.: Convex analysis approach to DC programming: theory, algorithms and applications. Acta Math. Vietnam. 22(1), 289–355 (1997)MathSciNetMATH Tao, P.D., An, L.T.H.: Convex analysis approach to DC programming: theory, algorithms and applications. Acta Math. Vietnam. 22(1), 289–355 (1997)MathSciNetMATH
47.
Zurück zum Zitat Tao, P.D., An, L.T.H.: A DC optimization algorithm for solving the trust-region subproblem. SIAM J. Optim. 8(2), 476–505 (1998)MathSciNetMATHCrossRef Tao, P.D., An, L.T.H.: A DC optimization algorithm for solving the trust-region subproblem. SIAM J. Optim. 8(2), 476–505 (1998)MathSciNetMATHCrossRef
48.
Zurück zum Zitat Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B 58, 267–288 (1996)MathSciNetMATH Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B 58, 267–288 (1996)MathSciNetMATH
49.
Zurück zum Zitat Yang, L., Pong, T., Chen, X.: Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction. SIAM J. Imaging Sci. 10(1), 74–110 (2017)MathSciNetMATHCrossRef Yang, L., Pong, T., Chen, X.: Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction. SIAM J. Imaging Sci. 10(1), 74–110 (2017)MathSciNetMATHCrossRef
50.
51.
Zurück zum Zitat Zhang, C.-H., Huang, J.: The sparsity and bias of the LASSO selection in high-dimensional linear regression. Ann. Stat. 36(4), 1567–1594 (2008)MathSciNetMATHCrossRef Zhang, C.-H., Huang, J.: The sparsity and bias of the LASSO selection in high-dimensional linear regression. Ann. Stat. 36(4), 1567–1594 (2008)MathSciNetMATHCrossRef
52.
Zurück zum Zitat Zhang, T.: Analysis of multi-stage convex relaxation for sparse regularization. J. Mach. Learn. Res. 11(2), 1081–1107 (2010)MathSciNetMATH Zhang, T.: Analysis of multi-stage convex relaxation for sparse regularization. J. Mach. Learn. Res. 11(2), 1081–1107 (2010)MathSciNetMATH
53.
Metadaten
Titel
A Nonconvex Model with Minimax Concave Penalty for Image Restoration
verfasst von
Juntao You
Yuling Jiao
Xiliang Lu
Tieyong Zeng
Publikationsdatum
20.08.2018
Verlag
Springer US
Erschienen in
Journal of Scientific Computing / Ausgabe 2/2019
Print ISSN: 0885-7474
Elektronische ISSN: 1573-7691
DOI
https://doi.org/10.1007/s10915-018-0801-z

Weitere Artikel der Ausgabe 2/2019

Journal of Scientific Computing 2/2019 Zur Ausgabe