Global optimality analysis and solution of the $ \ell_0 $ total variation signal denoising model

Shanshan Pan; Qianqian Dai; Huangyue Chen; Shanshan Pan; Qianqian Dai; Huangyue Chen

doi:10.3934/mbe.2023299

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 4: 6932-6946. doi: 10.3934/mbe.2023299

Previous Article Next Article

Research article

Global optimality analysis and solution of the $ \ell_0 $ total variation signal denoising model

1.
School of Science, Guangxi University of Science and Technology, Liuzhou 545006, China
2.
Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

Received: 05 December 2022 Revised: 19 January 2023 Accepted: 03 February 2023 Published: 08 February 2023

The total variation regularizer is diffusely emerged in statistics, image and signal processing to obtain piecewise constant estimator. The $ \ell_0 $ total variation (L0TV) regularized signal denoising model is a nonconvex and discontinuous optimization problem, and it is very difficult to find its global optimal solution. In this paper, we present the global optimality analysis of L0TV signal denoising model, and design an efficient algorithm to pursuit its solution. Firstly, we equivalently rewrite the L0TV denoising model as a partial regularized (PL0R) minimization problem by aid of the structured difference operator. Subsequently, we define a P-stationary point of PL0R, and show that it is a global optimal solution. These theoretical results allow us to find the global optimal solution of the L0TV model. Therefore, an efficient Newton-type algorithm is proposed for the PL0R problem. The algorithm has a considerably low computational complexity in each iteration. Finally, experimental results demonstrate the excellent performance of our approach in comparison with several state-of-the-art methods.
- total variation,
- signal denoising,
- partial $ \ell_0 $ regularized model,
- Global optimization,
- Newton-type algorithm
Citation: Shanshan Pan, Qianqian Dai, Huangyue Chen. Global optimality analysis and solution of the $ \ell_0 $ total variation signal denoising model[J]. Mathematical Biosciences and Engineering, 2023, 20(4): 6932-6946. doi: 10.3934/mbe.2023299

Related Papers:

Abstract

The total variation regularizer is diffusely emerged in statistics, image and signal processing to obtain piecewise constant estimator. The $ \ell_0 $ total variation (L0TV) regularized signal denoising model is a nonconvex and discontinuous optimization problem, and it is very difficult to find its global optimal solution. In this paper, we present the global optimality analysis of L0TV signal denoising model, and design an efficient algorithm to pursuit its solution. Firstly, we equivalently rewrite the L0TV denoising model as a partial regularized (PL0R) minimization problem by aid of the structured difference operator. Subsequently, we define a P-stationary point of PL0R, and show that it is a global optimal solution. These theoretical results allow us to find the global optimal solution of the L0TV model. Therefore, an efficient Newton-type algorithm is proposed for the PL0R problem. The algorithm has a considerably low computational complexity in each iteration. Finally, experimental results demonstrate the excellent performance of our approach in comparison with several state-of-the-art methods.

References

[1]	R. Tibshirani, M. Saunders, S. Rosset, J. Zhu, K. Knight, Sparsity and smoothness via the fused lasso, J. R. Stat. Soc. Ser. B. Stat. Methodol., 67 (2005), 91–108. https://doi.org/10.1111/j.1467-9868.2005.00490.x doi: 10.1111/j.1467-9868.2005.00490.x
[2]	A. Guntuboyina, D. Lieu, S. Chatterjee, B. Sen, Adaptive risk bounds in univariate total variation denoising and trend filtering, Ann. Statist., 48 (2020), 205–229. https://doi.org/10.1214/18-AOS1799 doi: 10.1214/18-AOS1799
[3]	B. Fang, A. Guntuboyina, B. Sen, Multivariate extensions of isotonic regression and total variation denoising via entire monotonicity and hardy-krause variation, Ann. Statist., 49 (2021), 769–792. https://doi.org/10.1214/20-AOS1977 doi: 10.1214/20-AOS1977
[4]	L. Rudin, S. Osher, E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), 259–268. https://doi.org/10.1016/0167-2789(92)90242-F doi: 10.1016/0167-2789(92)90242-F
[5]	I. W. Selesnick, A. Parekh, I. Bayram, Convex 1-d total variation denoising with non-convex regularization. IEEE Signal Process. Lett., 22 (2015), 141–144. https://doi.org/10.1109/LSP.2014.2349356
[6]	G. Yuan, B. Ghanem, $\ell_0$ tv: A sparse optimization method for impulse noise image restoration, IEEE Trans. Pattern Anal. Mach. Intell., 41 (2019), 352–364. https://doi.org/10.1109/TPAMI.2017.2783936 doi: 10.1109/TPAMI.2017.2783936
[7]	J. J. Liu, R. J. Ma, X. Y. Zeng, W. Q. Liu, An efficient non-convex total variation approach for image deblurring and denoising, Appl. Math. Comput., 397 (2021), 125977. https://doi.org/10.1016/j.amc.2021.125977 doi: 10.1016/j.amc.2021.125977
[8]	L. Condat, A direct algorithm for 1-d total variation denoising, IEEE Signal Process. Lett., 20 (2013), 1054–1057. https://doi.org/10.1109/LSP.2013.2278339 doi: 10.1109/LSP.2013.2278339
[9]	L. Dumbge, A. Kovac. Extensions of smoothing via taut strings, Electron. J. Stat., 3 (2009), 41–75. https://doi.org/10.1214/08-EJS216 doi: 10.1214/08-EJS216
[10]	J. Q. Fan, R. Z. Li, Variable selection via nonconcave penalized likelihood and its oracle properties, J. Amer. Statist. Assoc., 96 (2001), 1348–1360. https://doi.org/10.1198/016214501753382273 doi: 10.1198/016214501753382273
[11]	Z. B. Xu, H. Zhang, Y. Wang, X. Y. Chang, Y. Liang, $\ell_{1/2}$ regularization, Sci. China Inf. Sci., 53 (2010), 1159–1169. https://doi.org/10.1007/s11432-010-0090-0 doi: 10.1007/s11432-010-0090-0
[12]	C. H. Zhang, Nearly unbiased variable selection under minimax concave penalty. Ann. Stat., 38 (2010), 894–945. https://doi.org/10.1214/09-AOS729
[13]	T. Zhang, Analysis of multi-stage convex relaxation for sparse regularization, J. Mach. Learn. Res., 11 (20104), 1081–1107.
[14]	H. Q. Du, Y. L. Liu, Minmax-concave total variation denoising. Signal, Image and Video Process., 12 (2018), 1027–1034. https://doi.org/10.1007/s11760-018-1248-2
[15]	I. W. Selesnick, Total variation denoising via the moreau envelope, IEEE Signal Process. Lett., 24 (2017), 216–220. https://doi.org/10.1109/LSP.2017.2647948 doi: 10.1109/LSP.2017.2647948
[16]	I. W. Selesnick, A. Lanza, S. Morigi, F. Sgallari, Non-convex total variation regularization for convex denoising of signals, J. Math. Imaging Vision, 62 (2020), 825–841. https://doi.org/10.1007/s10851-019-00937-5 doi: 10.1007/s10851-019-00937-5
[17]	M. Storath, A. Weinmann, L. Demaret, Jump-sparse and sparse recovery using potts functionals. IEEE Trans. Signal Process., 62 (2014), 3654–3666. https://doi.org/10.1109/TSP.2014.2329263
[18]	J. Frecon, N. Pustelnik, N. Dobigeon, H. Wendt, P. Abry, Bayesian selection for the l2-potts model regularization parameter: 1d piecewise constant signal denoising, IEEE Trans. Signal Process., 65 (2017), 5215–5224. https://doi.org/10.1109/TSP.2017.2715000 doi: 10.1109/TSP.2017.2715000
[19]	R. B. Potts, Some generalized order-disorder transformations, Math. Proc. Cambridge Philos. Soc., 48 (1952), 106–109. https://doi.org/10.1017/S0305004100027419 doi: 10.1017/S0305004100027419
[20]	T. Blumensath, M. E. Davies, Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14 (2008), 629–654. https://doi.org/10.1007/s00041-008-9035-z doi: 10.1007/s00041-008-9035-z
[21]	Z. S. Lu, Iterative hard thresholding methods for $\ell_0$ regularized convex cone programming, Math. Program., 147 (2014), 125–154. https://doi.org/10.1007/s10107-013-0714-4 doi: 10.1007/s10107-013-0714-4
[22]	Z. S. Lu, Y. Zhang, Sparse approximation via penalty decomposition methods, SIAM J. Optim., 23 (2013), 2448–2478. https://doi.org/10.1137/100808071 doi: 10.1137/100808071
[23]	W. Y. Cheng, Z. Chen, Q. J. Hu, An active set barzilar-borwein algorithm for $\ell_0$ regularized optimization, J. Global Optim., 76 (2020), 769–791. https://doi.org/10.1007/s10898-019-00830-w doi: 10.1007/s10898-019-00830-w
[24]	S. L. Zhou, L. L. Pan, N. H. Xiu, Newton method for $\ell_0$ regularized optimization, Numer. Algor., 88 (2021), 1541–1570. https://doi.org/10.1007/s11075-021-01085-x doi: 10.1007/s11075-021-01085-x
[25]	A. Beck, N. Hallak, Proximal mapping for symmetric penalty and sparsity, SIAM J. Optim., 28 (2018), 496–527. https://doi.org/10.1137/17M1116544 doi: 10.1137/17M1116544
[26]	R. T. Rockafellar, R. J-B. Wets, Variational Analysis, Springer, Berlin, 1997. https://doi.org/10.1007/978-3-642-02431-3
[27]	M. Storath, A. Weinmann, Fast partitioning of vector-valued images, SIAM J. Imag. Sci., 7 (2014), 1826–1852. https://doi.org/10.1137/130950367 doi: 10.1137/130950367

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)