Convex non-convex variational models. (English) Zbl 07914334
Chen, Ke (ed.) et al., Handbook of mathematical models and algorithms in computer vision and imaging. Mathematical imaging and vision. Springer Reference. Cham: Springer. 3-59 (2023).
Summary: An important class of computational techniques to solve inverse problems in image processing relies on a variational approach: the optimal output is obtained by finding a minimizer of an energy function or “model” composed of two terms, the data-fidelity term, and the regularization term. Much research has focused on models where both terms are convex, which leads to convex optimization problems. However, there is evidence that non-convex regularization can improve significantly the output quality for images characterized by some sparsity property. This fostered recent research toward the investigation of optimization problems with non-convex terms. Non-convex models are notoriously difficult to handle as classical optimization algorithms can get trapped at unwanted local minimizers. To avoid the intrinsic difficulties related to non-convex optimization, the convex non-convex (CNC) strategy has been proposed, which allows the use of non-convex regularization while maintaining convexity of the total cost function. This work focuses on a general class of parameterized non-convex sparsity-inducing separable and non-separable regularizers and their associated CNC variational models. Convexity conditions for the total cost functions and related theoretical properties are discussed, together with suitable algorithms for their minimization based on a general forward-backward (FB) splitting strategy. Experiments on the two classes of considered separable and non-separable CNC variational models show their superior performance than the purely convex counterparts when applied to the discrete inverse problem of restoring sparsity-characterized images corrupted by blur and noise.
For the entire collection see [Zbl 1527.94003].
For the entire collection see [Zbl 1527.94003].
MSC:
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 68U10 | Computing methodologies for image processing |
| 90C25 | Convex programming |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
convex non-convex optimization; sparsity regularization; image restoration; alternating direction method of multipliers; forward backward algorithmReferences:
| [1] | Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011) · Zbl 1218.47001 |
| [2] | Bayram, I.: On the convergence of the iterative shrinkage/thresholding algorithm with a weakly convex penalty. IEEE Trans. Signal Process. 64(6), 1597-1608 (2016) · Zbl 1412.94018 |
| [3] | Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2(1), 183-202 (2009) · Zbl 1175.94009 |
| [4] | Becker, S., Combettes, P.L.: An algorithm for splitting parallel sums of linearly composed monotone operators, with applications to signal recovery. J. Nonlinear Convex Anal. 15(1), 137-159 (2014) · Zbl 1293.47059 |
| [5] | Bello Cruz, J.Y.: On proximal subgradient splitting method for minimizing the sum of two nonsmooth convex functions. Set-Valued Var. Anal 25, 245-263 (2017) · Zbl 1365.65160 |
| [6] | Blake, A., Zisserman, A.: Visual Reconstruction. MIT Press, Cambridge, MA (1987) |
| [7] | Bruckstein, A., Donoho, D., Elad, M.: From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51(1), 34-81 (2009) · Zbl 1178.68619 |
| [8] | Burger, M., Papafitsoros, K., Papoutsellis, E., Schönlieb, C.B.: Infimal convolution regularisation functionals of BV and Lp spaces. J. Math. Imaging Vis. 55(3), 343-369 (2016) · Zbl 1342.49014 |
| [9] | Cai, G., Selesnick, I.W., Wang, S., Dai, W., Zhu, Z.: Sparsity enhanced signal decomposition via generalized minimax-concave penalty for gearbox fault diagnosis. J. Sound Vib. 432, 213-234 (2018) |
| [10] | Candés, E.J., Wakin, M.B., Boyd, S.: Enhancing sparsity by reweighted l1 minimization. J. Fourier Anal. Appl.14(5), 877-905 (2008) · Zbl 1176.94014 |
| [11] | Carlsson, M.: On convexification/optimization of functionals including an l2-misfit term. arXiv preprint arXiv:1609.09378 (2016) |
| [12] | Castella, M., Pesquet, J.C.: Optimization of a Geman-McClure like criterion for sparse signal deconvolution. In: IEEE International Workshop on Computational Advances Multi-sensor Adaptive Processing, pp. 309-312 (2015) |
| [13] | Chambolle, A., Lions, P.L.: Image recovery via total variation minimization and related problems. Numerische Mathematik 76, 167-188 (1997) · Zbl 0874.68299 |
| [14] | Chan, R., Lanza, A., Morigi, S., Sgallari, F.: Convex non-convex image segmentation. Numerische Mathematik 138(3), 635-680 (2017) · Zbl 1453.65141 |
| [15] | Chartrand, R.: Shrinkage mappings and their induced penalty functions. In: International Confer-ence on Acoustics, Speech and Signal Processing (ICASSP), pp. 1026-1029 (2014) |
| [16] | Chen, P.Y., Selesnick, I.W.: Group-sparse signal denoising: non-convex regularization, convex optimization. IEEE Trans. Signal Proc. 62, 3464-3478 (2014) · Zbl 1394.94115 |
| [17] | Chouzenoux, E., Jezierska, A., Pesquet, J., Talbot, H.: A majorize-minimize subspace approach for l2-l0 image regularization. SIAM J. Imag. Sci. 6(1), 563-591 (2013) · Zbl 1281.65030 |
| [18] | Ding, Y., Selesnick, I.W.: Artifact-free wavelet denoising: nonconvex sparse regularization, convex optimization. IEEE Signal Process. Lett. 22(9), 1364-1368 (2015) |
| [19] | Du, H., Liu, Y.: Minmax-concave total variation denoising. Signal Image Video Process. 12(6), 1027-1034 (2018) |
| [20] | Geiger, D., Girosi, F.: Parallel and deterministic algorithms from MRF’s: surface reconstruction. IEEE Trans. Pattern Anal. Mach. Intell. 13(5), 410-412 (1991) |
| [21] | Geman, S., Geman, D.: Stochastic relaxation, Gibbs distribution, and the Bayesian restoration of images. IEEE PAMI 6(6), 721-741 (1984) · Zbl 0573.62030 |
| [22] | Hansen, P.C.: Rank-Deficient and Discrete Ill-Posed Problems. SIAM, Philadelphia (1997) · Zbl 0890.65037 |
| [23] | Hartman, P.: On functions representable as a difference of convex functions. Pac. J. Math. 9(3), 707-713 (1959) · Zbl 0093.06401 |
| [24] | Hastie, T., Tibshirani, R., Wainwright, M.: Statistical Learning with Sparsity: The Lasso and Generalizations. CRC Press, Boca Raton (2015) · Zbl 1319.68003 |
| [25] | Huska, M., Lanza, A., Morigi, S., Sgallari, F.: Convex non-convex segmentation of scalar fields over arbitrary triangulated surfaces. J. Comput. Appl. Math. 349, 438-451 (2019a) · Zbl 1510.65037 |
| [26] | Huska, M., Lanza, A., Morigi, S., Selesnick, I.W.: A convex-nonconvex variational method for the additive decomposition of functions on surfaces. Inverse Problems 35, 124008-124041 (2019b) · Zbl 1468.94016 |
| [27] | Jensen, J.B., Nielsen, M.: A simple genetic algorithm applied to discontinuous regularization. In: Proceedings IEEE workshop on NNSP, Copenhagen (1992) |
| [28] | Lanza, A., Morigi, S., Sgallari, F.: Convex image denoising via non-convex regularization. Scale Space Variat. Methods Comput. Vis. 9087, 666-677 (2015) · Zbl 1444.94015 |
| [29] | Lanza, A., Morigi, S., Sgallari, F.: Convex image denoising via nonconvex regularization with parameter selection. J. Math. Imaging Vis. 56(2), 195-220 (2016a) · Zbl 1391.94088 |
| [30] | Lanza, A., Morigi, S., Sgallari, F.: Constrained TV p -2 model for image restoration. J. Sci. Comput. 68, 64-91 (2016b) · Zbl 1344.65025 |
| [31] | Lanza, A., Morigi, S., Selesnick, I.W., Sgallari, F.: Nonconvex nonsmooth optimization via convex-nonconvex majorization minimization. Numerische Mathematik 136(2), 343-381 (2017) · Zbl 1368.65087 |
| [32] | Lanza, A., Morigi, S., Sgallari, F.: Automatic parameter selection based on residual whiteness for convex non-convex variational restoration. In: Mathematical Methods in Image Processing and and Inverse Problems (eds) Tai XC, Wei S, Liu H. Springer, Singapore, 360, (2021). https://doi. org/10.1007/978-981-16-2701-9 · Zbl 1476.68015 · doi:10.1007/978-981-16-2701-9 |
| [33] | Lanza, A., Morigi, S., Selesnick, I.W., Sgallari, F.: Sparsity-inducing nonconvex nonseparable regularization for convex image processing. SIAM J. Imag. Sci. 12(2), 1099-1134 (2019) · Zbl 1524.94023 |
| [34] | Lanza, A., Pragliola, M., Sgallari, F.: Residual whiteness principle for parameter-free image restoration. Electron. Trans. Numer. Anal. 53, 329-351 (2020) · Zbl 1455.94027 |
| [35] | Lefkimmiatis, S., Ward, J., Unser, M.: Hessian Schatten-Norm regularization for linear inverse problems. IEEE Trans. Image Process. 22, 1873-1888 (2013) · Zbl 1373.94229 |
| [36] | Malek-Mohammadi, M., Rojas, C.R., Wahlberg, B.: A class of nonconvex penalties preserving overall convexity in optimization based mean filtering. IEEE Trans. Signal Process. 64(24), 6650-6664 (2016) · Zbl 1414.94398 |
| [37] | Nikolova, M.: Estimation of binary images by minimizing convex criteria. Proc. IEEE Int. Conf. Image Process. 2, 108-112 (1998) |
| [38] | Nikolova, M.: Energy minimization methods. In: Scherzer, O. (ed.) Handbook of Mathematical Methods in Imaging, Chapter 5, pp. 138-186. Springer, Berlin (2011) |
| [39] | Nikolova, M., Ng, M.K., Tam, C.P.: Fast nonconvex nonsmooth minimization methods for image restoration and reconstruction. IEEE Trans. Image Process. 19(12), 3073-3088 (2010) · Zbl 1371.94277 |
| [40] | Parekh, A., Selesnick, I.W.: Convex denoising using non-convex tight frame regularization. IEEE Signal Process. Lett. 22(10), 1786-1790 (2015) |
| [41] | Parekh, A., Selesnick, I.W.: Enhanced low-rank matrix approximation. IEEE Signal Process. Lett. 23(4), 493-497 (2016) |
| [42] | Park, T.W., Burrus, C.S.: Digital Filter Design. Wiley, New York (1987) · Zbl 0632.93001 |
| [43] | Portilla, J., Mancera, L.: L0-based sparse approximation: two alternative methods and some applications. In: Proceedings of SPIE, San Diego, vol. 6701 (Wavelets XII) (2007) |
| [44] | Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physics D 60(1-4), 259-268 (1992) · Zbl 0780.49028 |
| [45] | Selesnick, I.W.: Sparse regularization via convex analysis. IEEE Trans. Signal Process. 65(17), 4481-4494 (2017a) · Zbl 1414.94545 |
| [46] | Selesnick, I.W.: Total variation denoising via the Moreau envelope. IEEE Signal Process. Lett. 24(2), 216-220 (2017b) |
| [47] | Selesnick, I.W., Bayram, I.: Sparse signal estimation by maximally sparse convex optimization. IEEE Trans. Signal Proc. 62(5), 1078-1092 (2014) · Zbl 1394.94510 |
| [48] | Selesnick, I.W., Parekh, A., Bayram, I.: Convex 1-D total variation denoising with non-convex regularization. IEEE Signal Process. Lett. 22, 141-144 (2015) |
| [49] | Selesnick, I.W., Lanza, A., Morigi, S., Sgallari, F.: Non-convex total variation regularization for convex denoising of signals. J. Math. Imag. Vis. 62, 825-841 (2020) · Zbl 1485.94026 |
| [50] | Setzer, S., Steidl, G., Teuber, T.: Infimal convolution regularizations with discrete l1-type function-als. Commun. Math. Sci. 9(3), 797-827 (2011) · Zbl 1269.49063 |
| [51] | Shen, L., Xu, Y., Zeng, X.: Wavelet inpainting with the l0 sparse regularization. J. Appl. Comp. Harm. Anal. 41(1), 26-53 (2016) · Zbl 1338.65061 |
| [52] | Sidky, E.Y., Chartrand, R., Boone, J.M., Pan, X.: Constrained TpV-minimization for enhanced exploitation of gradient sparsity: application to CT image reconstruction. IEEE J. Trans. Eng. Health Med. 2, 1-18 (2014) |
| [53] | Soubies, E., Blanc-Féraud, L., Aubert, G.: A continuous exact L0 penalty (CEL0) for least squares regularized problem. SIAM J. Imag. Sci.8(3), 1607-1639 (2015) · Zbl 1325.65086 |
| [54] | Tipping, M.E.: Sparse Bayesian learning and the relevance vector machine. J. Mach. Learn. Res. 1, 211-244 (2001) · Zbl 0997.68109 |
| [55] | Tuy, H.: DC optimization: theory, methods and algorithms. In: Handbook of Global Optimization, pp. 149-216. Springer, Boston, (1995) · Zbl 0832.90111 |
| [56] | Wang, S., Selesnick, I.W., Cai, G., Ding, B., Chen, X.: Synthesis versus analysis priors via generalized minimax-concave penalty for sparsity-assisted machinery fault diagnosis. Mech. Syst. Signal Process. 127, 202-233 (2019) |
| [57] | Wipf, D.P., Rao, B.D., Nagarajan, S.: ”Latent variable Bayesian models for promoting sparsity. In: IEEE Trans. Inf. Theory 57(9), 6236-6255 (2011) · Zbl 1365.62103 |
| [58] | Yuille, A.L., Rangarajan, A.: The concave-convex procedure. Neural Comput. 15(4), 915-936 (2003) Zhang, C.-H.: Nearly unbiased variable selection under minimax concave penalty. Ann. Stat. 38(2), 894-942 (2010) |
| [59] | Zou, J., Shen, M., Zhang, Y., Li, H., Liu, G., Ding, S.: Total variation denoising with non-convex regularizers. IEEE Access 7, 4422-4431 (2019) |
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.
