Non-convex total variation regularization for convex denoising of signals. (English) Zbl 1485.94026
Summary: Total variation (TV) signal denoising is a popular nonlinear filtering method to estimate piecewise constant signals corrupted by additive white Gaussian noise. Following a “convex non-convex” strategy, recent papers have introduced non-convex regularizers for signal denoising that preserve the convexity of the cost function to be minimized. In this paper, we propose a non-convex TV regularizer, defined using concepts from convex analysis, that unifies, generalizes, and improves upon these regularizers. In particular, we use the generalized Moreau envelope which, unlike the usual Moreau envelope, incorporates a matrix parameter. We describe a novel approach to set the matrix parameter which is essential for realizing the improvement we demonstrate. Additionally, we describe a new set of algorithms for non-convex TV denoising that elucidate the relationship among them and which build upon fast exact algorithms for classical TV denoising.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 93E11 | Filtering in stochastic control theory |
Keywords:
signal denoising; total variation regularization; forward-backward splitting algorithm; convex non-convex regularizationReferences:
| [1] | Bauschke, HH; Combettes, PL, Convex Analysis and Monotone Operator Theory in Hilbert Spaces (2011), Berlin: Springer, Berlin · Zbl 1218.47001 |
| [2] | Bayram, I., Correction for On the convergence of the iterative shrinkage/thresholding algorithm with a weakly convex penalty, IEEE Trans. Signal Process., 64, 14, 3822-3822 (2016) · Zbl 1414.94057 |
| [3] | 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 |
| [4] | Becker, S.; Combettes, PL, 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] | Blake, A.; Zisserman, A., Visual Reconstruction (1987), Cambridge: MIT Press, Cambridge |
| [6] | 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 |
| [7] | Cai, G.; Selesnick, IW; 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) |
| [8] | Candès, EJ; Wakin, MB; Boyd, S., Enhancing sparsity by reweighted l1 minimization, J. Fourier Anal. Appl., 14, 5, 877-905 (2008) · Zbl 1176.94014 |
| [9] | Carlsson, M.: On convexification/optimization of functionals including an l2-misfit term. arXiv preprint arXiv:1609.09378 (2016) |
| [10] | 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) |
| [11] | Chambolle, A.; Lions, P-L, Image recovery via total variation minimization and related problems, Numerische Mathematik, 76, 167-188 (1997) · Zbl 0874.68299 |
| [12] | Chan, R.; Lanza, A.; Morigi, S.; Sgallari, F., Convex non-convex image segmentation, Numerische Mathematik, 138, 3, 635-680 (2017) · Zbl 1453.65141 |
| [13] | Chan, TF; Osher, S.; Shen, J., The digital TV filter and nonlinear denoising, IEEE Trans. Image Process., 10, 2, 231-241 (2001) · Zbl 1039.68778 |
| [14] | Chartrand, R.: Shrinkage mappings and their induced penalty functions, pp. 1026-1029. In: International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2014) |
| [15] | Chouzenoux, E.; Jezierska, A.; Pesquet, J.; Talbot, H., A majorize-minimize subspace approach for \(\ell_2-\ell_0\) image regularization, SIAM J. Imag. Sci., 6, 1, 563-591 (2013) · Zbl 1281.65030 |
| [16] | Combettes, PL; Pesquet, J-C; Bauschke, HH, Proximal splitting methods in signal processing, Fixed-Point Algorithms for Inverse Problems in Science and Engineering, 185-212 (2011), Berlin: Springer, Berlin · Zbl 1242.90160 |
| [17] | Condat, L., A direct algorithm for 1-D total variation denoising, IEEE Signal Process. Lett., 20, 11, 1054-1057 (2013) |
| [18] | Ding, Y.; Selesnick, IW, Artifact-free wavelet denoising: non-convex sparse regularization, convex optimization, IEEE Signal Process. Lett., 22, 9, 1364-1368 (2015) |
| [19] | Donoho, D., Maleki, A., Shahram, M.: Wavelab 850 (2005). http://www-stat.stanford.edu/ |
| [20] | Du, H.; Liu, Y., Minmax-concave total variation denoising, Signal Image Video Process., 12, 6, 1027-1034 (2018) |
| [21] | Dümbgen, L.; Kovac, A., Extensions of smoothing via taut strings, Electron. J. Stat., 3, 41-75 (2009) · Zbl 1326.62087 |
| [22] | Frecon, J.; Pustelnik, N.; Dobigeon, N.; Wendt, H.; Abry, P., Bayesian selection for the l2-Potts model regularization parameter: 1D piecewise constant signal denoising, IEEE Trans. Signal Process., 65, 19, 5215-5224 (2017) · Zbl 1414.94202 |
| [23] | Friedrich, F.; Kempe, A.; Liebscher, V.; Winkler, G., Complexity penalized M-estimation: fast computation, J. Comput. Graph. Stat., 17, 1, 201-224 (2008) |
| [24] | 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 (2019) · Zbl 1510.65037 |
| [25] | Lanza, A.; Morigi, S.; Selesnick, I.; Sgallari, F., Nonconvex nonsmooth optimization via convex-nonconvex majorization-minimization, Numerische Mathematik, 136, 2, 343-381 (2017) · Zbl 1368.65087 |
| [26] | Lanza, A.; Morigi, S.; Selesnick, I.; Sgallari, F., Sparsity-inducing nonconvex nonseparable regularization for convex image processing, SIAM J. Imag. Sci., 12, 2, 1099-1134 (2019) · Zbl 1524.94023 |
| [27] | Lanza, A.; Morigi, S.; Sgallari, F., Constrained TVp-l2 model for image restoration, J. Sci. Comput., 68, 1, 64-91 (2016) · Zbl 1344.65025 |
| [28] | Lanza, A.; Morigi, S.; Sgallari, F., Convex image denoising via non-convex regularization with parameter selection, J. Math. Imaging Vis., 56, 2, 195-220 (2016) · Zbl 1391.94088 |
| [29] | Little, MA; Jones, NS, Generalized methods and solvers for noise removal from piecewise constant signals: part I - background theory, Proc. R. Soc. A, 467, 3088-3114 (2011) · Zbl 1239.94018 |
| [30] | Malek-Mohammadi, M.; Rojas, CR; 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 |
| [31] | Möllenhoff, T.; Strekalovskiy, E.; Moeller, M.; Cremers, D., The primal-dual hybrid gradient method for semiconvex splittings, SIAM J. Imag. Sci., 8, 2, 827-857 (2015) · Zbl 1328.68278 |
| [32] | Nikolova, M.: Estimation of binary images by minimizing convex criteria. In: Proceedings of IEEE International Conference on Image Processing (ICIP), vol. 2, pp. 108-112 (1998) |
| [33] | Nikolova, M.; Scherzer, O., Energy minimization methods, Handbook of Mathematical Methods in Imaging, Chapter 5, 138-186 (2011), Berlin: Springer, Berlin |
| [34] | Nikolova, M.; Ng, M.; Zhang, S.; Ching, W., Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization, SIAM J. Imag. Sci., 1, 1, 2-25 (2008) · Zbl 1207.94017 |
| [35] | Nikolova, M.; Ng, MK; 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 |
| [36] | Parekh, A.; Selesnick, IW, Convex denoising using non-convex tight frame regularization, IEEE Signal Process. Lett., 22, 10, 1786-1790 (2015) |
| [37] | Parekh, A.; Selesnick, IW, Enhanced low-rank matrix approximation, IEEE Signal Process. Lett., 23, 4, 493-497 (2016) |
| [38] | Parks, TW; Burrus, CS, Digital Filter Design (1987), Hoboken: Wiley, Hoboken · Zbl 0632.93001 |
| [39] | Portilla, J., Mancera, L.: L0-based sparse approximation: two alternative methods and some applications. In: Proceedings of SPIE, vol. 6701 (Wavelets XII), San Diego, CA, USA, (2007) |
| [40] | Rudin, L.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Phys. D, 60, 259-268 (1992) · Zbl 0780.49028 |
| [41] | Selesnick, I., Sparse regularization via convex analysis, IEEE Trans. Signal Process., 65, 17, 4481-4494 (2017) · Zbl 1414.94545 |
| [42] | Selesnick, I., Total variation denoising via the Moreau envelope, IEEE Signal Process. Lett., 24, 2, 216-220 (2017) |
| [43] | Selesnick, IW; Bayram, I., Sparse signal estimation by maximally sparse convex optimization, IEEE Trans. Signal Process., 62, 5, 1078-1092 (2014) · Zbl 1394.94510 |
| [44] | Selesnick, IW; Parekh, A.; Bayram, I., Convex 1-D total variation denoising with non-convex regularization, IEEE Signal Process. Lett., 22, 2, 141-144 (2015) |
| [45] | Setzer, S.; Steidl, G.; Teuber, T., Infimal convolution regularizations with discrete l1-type functionals, Commun. Math. Sci., 9, 3, 797-827 (2011) · Zbl 1269.49063 |
| [46] | Shen, L.; Suter, BW; Tripp, EE, Structured sparsity promoting functions, J. Optim. Theory Appl., 183, 2, 386-421 (2019) · Zbl 1428.90140 |
| [47] | 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 |
| [48] | Sidky, EY; Chartrand, R.; Boone, JM; Xiaochuan, P., Constrained TpV minimization for enhanced exploitation of gradient sparsity: application to CT image reconstruction, IEEE J. Transl. Eng. Health Med., 2, 1-18 (2014) |
| [49] | Soubies, E.; Blanc-Féraud, L.; Aubert, G., A continuous exact \(\ell_0\) penalty (CEL0) for least squares regularized problem, SIAM J. Imag. Sci., 8, 3, 1607-1639 (2015) · Zbl 1325.65086 |
| [50] | Storath, M.; Weinmann, A.; Demaret, L., Jump-sparse and sparse recovery using Potts functionals, IEEE Trans. Signal Process., 62, 14, 3654-3666 (2014) · Zbl 1394.94561 |
| [51] | Strang, G., The discrete cosine transform, SIAM Rev., 41, 1, 135-147 (1999) · Zbl 0939.42021 |
| [52] | Wang, S.; Selesnick, IW; 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) |
| [53] | Zhang, C-H, Nearly unbiased variable selection under minimax concave penalty, Ann. Stat., 38, 2, 894-942 (2010) · Zbl 1183.62120 |
| [54] | 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.
