×

A nonconvex model with minimax concave penalty for image restoration. (English) Zbl 1419.94014

A nonconvex model is proposed for image restoration with a minimax concave penalty (MCP) that enjoys good performance for sparse signal recovery. The existence of the global minimizer of the model is proven using the approach that can be applied to a class of nonconvex penalized models which do not necessarily have coercive penalties. Then the model is solved by using the alternating direction method of multipliers algorithm similar to that by R. T. Rockafellar [Math. Oper. Res. 1, 97–116 (1976; Zbl 0402.90076)]. Under a mild condition the global subsequential convergence of the algorithm is established with properly chosen parameters. Numerical experiments demonstrate that the MCP model outperforms the TV model in terms of efficiency and accuracy.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization

Citations:

Zbl 0402.90076

Software:

PDCO; tvreg
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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) · Zbl 1214.65036
[2] Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1-2), 459-494 (2014) · Zbl 1297.90125
[3] Boyd, S.: Alternating direction method of multipliers. Talk at NIPS Workshop on Optimization and Machine Learning (2011)
[4] 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) · Zbl 1172.94309
[5] Cai, J.-F., Osher, S., Shen, Z.: Split Bregman methods and frame based image restoration. Multiscale Model. Simul. 8(2), 337-369 (2009) · Zbl 1189.94014
[6] 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) · Zbl 1283.52011
[7] 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) · Zbl 1098.94009
[8] Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1), 89-97 (2004) · Zbl 1366.94048
[9] 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) · Zbl 1209.94004
[10] 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) · Zbl 1046.42026
[11] Chan, R.H., Ng, M.K.: Conjugate gradient methods for Toeplitz systems. SIAM Rev. 38(3), 427-482 (1996) · Zbl 0863.65013
[12] Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM Rev. 43(1), 129-159 (2001) · Zbl 0979.94010
[13] Chouzenoux, E., Jezierska, A., Pesquet, J.-C., Talbot, H.: A majorize – minimize subspace approach for \[\ell_2\] ℓ \[2-\ell_0\] ℓ0 image regularization. SIAM J. Imaging Sci. 6(1), 563-591 (2013) · Zbl 1281.65030
[14] Daubechies, I., Han, B., Ron, A., Shen, Z.: Framelets: MRA-based constructions of wavelet frames. Appl. Comput. Harmon. Anal. 14(1), 1-46 (2003) · Zbl 1035.42031
[15] 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) · Zbl 1379.65036
[16] Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289-1306 (2006) · Zbl 1288.94016
[17] 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) · Zbl 0765.90073
[18] Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split Bregman. CAM Rep. 9, 31 (2009)
[19] 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)] · Zbl 1073.62547
[20] Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348-1360 (2001) · Zbl 1073.62547
[21] Fan, J., Peng, H.: Nonconcave penalized likelihood with a diverging number of parameters. Ann. Stat. 32(3), 928-961 (2004). [MR 2065194 (2005g:62047)] · Zbl 1092.62031
[22] Frank, L.L.E., Friedman, J.H.: A statistical view of some chemometrics regression tools. Technometrics 35(2), 109-135 (1993) · Zbl 0775.62288
[23] 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)
[24] Fu, W.J.: Penalized regressions: the bridge versus the lasso. J. Comput. Graph. Stat. 7(3), 397-416 (1998)
[25] Gabay, D.: Chapter ix applications of the method of multipliers to variational inequalities. Stud. Math. Appl. 15, 299-331 (1983)
[26] 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) · Zbl 0352.65034
[27] Getreuer, P.: Rudin-Osher-Fatemi total variation denoising using split Bregman. Image Process. On Line 2, 74-95 (2012)
[28] 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) · Zbl 0368.65053
[29] Goldstein, T., Osher, S.: The split Bregman method for L1-regularized problems. SIAM J. Imaging Sci. 2(2), 323-343 (2009) · Zbl 1177.65088
[30] 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) · Zbl 1356.49061
[31] 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] Lions, P.-L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964-979 (1979) · Zbl 0426.65050
[33] 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) · Zbl 1322.94019
[34] Mallat, S.G.: Multifrequency channel decompositions of images and wavelet models. IEEE Trans. Acoust. Speech Signal Process. 37(12), 2091-2110 (1989)
[35] Mordukhovich, B.S., Shao, Y.: On nonconvex subdifferential calculus in banach spaces1. J. Convex Anal. 2(1/2), 211-227 (1995) · Zbl 0838.49013
[36] Moreau, J.-J.: Fonctions convexes duales et points proximaux dans un espace hilbertien. CR Acad. Sci. Paris Ser. A Math. 255, 2897-2899 (1962) · Zbl 0118.10502
[37] Moreau, J.-J.: Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. Fr. 93(2), 273-299 (1965) · Zbl 0136.12101
[38] 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) · Zbl 1091.94007
[39] Nikolova, M.: Analytical bounds on the minimizers of (nonconvex) regularized least-squares. Inv. Probl. Imaging 1(4), 1-677 (2007)
[40] 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) · Zbl 1207.94017
[41] Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97-116 (1976) · Zbl 0402.90076
[42] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis, vol. 317. Springer, Berlin (2009) · Zbl 0888.49001
[43] Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Phys. D Nonlinear Phenom. 60(1-4), 259-268 (1992) · Zbl 0780.49028
[44] Setzer, S., Steidl, G., Teuber, T.: Deblurring Poissonian images by split Bregman techniques. J. Vis. Commun. Image Represent. 21(3), 193-199 (2010)
[45] 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) · Zbl 1190.90117
[46] 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) · Zbl 0895.90152
[47] 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) · Zbl 0913.65054
[48] Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B 58, 267-288 (1996) · Zbl 0850.62538
[49] 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) · Zbl 1364.90278
[50] Zhang, C.-H.: Nearly unbiased variable selection under minimax concave penalty. Ann. Stat. 38(2), 894-942 (2010) · Zbl 1183.62120
[51] 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) · Zbl 1142.62044
[52] Zhang, T.: Analysis of multi-stage convex relaxation for sparse regularization. J. Mach. Learn. Res. 11(2), 1081-1107 (2010) · Zbl 1242.68262
[53] Zou, H., Li, R.: One-step sparse estimates in nonconcave penalized likelihood models. Ann. Stat. 36(4), 1509 (2008) · Zbl 1142.62027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.