Morozov's discrepancy principle for $ \alpha\ell_1-\beta\ell_2 $ sparsity regularization

Liang Ding; Weimin Han

doi:10.3934/ipi.2022035

Article Contents

2023, Volume 17, Issue 1: 157-179. Doi: 10.3934/ipi.2022035

This issue Previous Article Reconstructing a potential perturbation of the biharmonic operator on transversally anisotropic manifolds Next Article The enclosure method for the detection of variable order in fractional diffusion equations

Morozov's discrepancy principle for $ \alpha\ell_1-\beta\ell_2 $ sparsity regularization

Liang Ding^1, , and
Weimin Han^2,

1.
Department of Mathematics, Northeast Forestry University, Harbin 150040, China
2.
Department of Mathematics, University of Iowa, Iowa City, IA 52242, USA

^* Corresponding author: Liang Ding
^* Corresponding author: Liang Ding

Received: January 2022

Revised: April 2022

Early access: June 24, 2022

Published online: June 24, 2022

Abstract / Introduction Full Text(HTML) Figure(10) Related Papers Cited by

Abstract

In this paper, Morozov's discrepancy principle is considered for the non-convex $ \alpha\ell_1-\beta\ell_2 $ sparsity regularization ($ \alpha>\beta>0 $). It is shown that if $ \tau>1 $ satisfies some conditions, there exists a regularization parameter $ \alpha $ such that $ \delta\leq \|A(x_{\alpha,\beta}^{\delta})-y^{\delta}\|_Y\leq \tau \delta $ holds. Furthermore, it is shown that $ \alpha $ converges to 0 as $ \delta\rightarrow 0 $. In addition, well-posedness and convergence rate results are presented for the regularized solution under Morozov's discrepancy principle. Numerical simulation results are reported to illustrate the efficiency of the proposed approach.

Keywords:

Ill-posed problems,
Morozov's discrepancy principle,
$ \alpha\ell_1-\beta\ell_2 $ regularization,
non-convex regularizer,
sparsity.

Mathematics Subject Classification: Primary: 49J27, 49J52; Secondary: 65J15, 65J20.

Citation:

Full Text(HTML)

Figure 1. (a) $ \alpha $ vs. $ \delta $ where $ \alpha: \|A(x_{\alpha, \beta}^{\delta})-y^{\delta}\|_Y = c(\delta) $; (b) Rerror vs. $ \delta $.

Download: Full-size image PowerPoint slide

Figure 2. (a) $ \alpha $ vs. $ \delta $ where $ \alpha $ is determined by Algorithm 1; (b) Rerror vs. $ \delta $.

Download: Full-size image PowerPoint slide

Figure 3. (a) True image; (b) Observed image; (c) Recovered image with $ \alpha: \|A(x_{\alpha_j, \beta_j}^{\delta})-y^{\delta}\|_Y = c(\delta) $; (d) Recovered image with $ \alpha $ is determined by Algorithm 1.

Download: Full-size image PowerPoint slide

Figure 4. (a) $ \alpha $ vs. $ \delta $ where $ \alpha: \|A(x_{\alpha, \beta}^{\delta})-y^{\delta}\|_Y = c(\delta) $; (b) Rerror vs. $ \delta $.

Download: Full-size image PowerPoint slide

Figure 5. (a) $ \alpha $ vs. $ \delta $ where $ \alpha $ is determined by Algorithm 1; (b) Rerror vs. $ \delta $.

Download: Full-size image PowerPoint slide

Figure 6. (a) True signal; (b) Observed data; (c) Recovered signal with $ \alpha: \|A(x_{\alpha_j, \beta_j}^{\delta})-y^{\delta}\|_Y = c(\delta) $; Rerror = 0.0828; (d) Recovered signal with $ \alpha $ is determined by Algorithm 1; Rerror = 0.0465.

Download: Full-size image PowerPoint slide

Figure 7. $ \delta $, the upper bound $ c(\delta) $ and $ \|A(x_{\alpha,\beta}^{\delta})-y^{\delta}\| $ vs. $ \alpha $.

Download: Full-size image PowerPoint slide

Figure 8. (a) $ \alpha $ vs. $ \delta $ where $ \alpha: \|A(x_{\alpha, \beta}^{\delta})-y^{\delta}\|_Y = c(\delta) $; (b) Rerror vs. $ \delta $.

Download: Full-size image PowerPoint slide

Figure 9. (a) $ \alpha $ vs. $ \delta $ where $ \alpha $ is determined by Algorithm 1; (b) Rerror vs. $ \delta $.

Download: Full-size image PowerPoint slide

Figure 10. (a) True signal; (b) Observed data; (c) Recovered signal with $ \alpha: \|A(x_{\alpha, \beta}^{\delta})-y^{\delta}\|_Y = c(\delta) $ Rerror = 0.0734; (d) Recovered signal with $ \alpha $ is determined by Algorithm 1 Rerror = 0.0137.

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	V. Albani and A. De Cezaro, A connection between uniqueness of minimizers in Tikhonov-type regularization and Morozov-like discrepancy principles, Inverse Problems and Imaging, 13 (2019), 211-229. doi: 10.3934/ipi.2019012.
[2]	S. W. Anzengruber and R. Ramlau, Morozov's discrepancy principle for Tikhonov-type functionals with nonlinear operators, Inverse Problems, 26 (2010), 025001, 17 pp. doi: 10.1088/0266-5611/26/2/025001.
[3]	S. W. Anzengruber and R. Ramlau, Convergence rates for Morozov's discrepancy principle using variational inequalities, Inverse Problems, 27 (2011), 105007, 18 pp. doi: 10.1088/0266-5611/27/10/105007.
[4]	A. Beck and Y. C. Eldar, Sparsity constrained nonlinear optimization: Optimality conditions and algorithms, SIAM Journal on Optimization, 23 (2013), 1480-1509. doi: 10.1137/120869778.
[5]	M. Benning and M. Burger, Modern regularization methods for inverse problems, Acta Numerica, 27 (2018), 1-111. doi: 10.1017/S0962492918000016.
[6]	T. Blumensath, Compressed sensing with nonlinear observations and related nonlinear optimization problems, IEEE Transactions on Information Theory, 59 (2013), 3466-3474. doi: 10.1109/TIT.2013.2245716.
[7]	T. Blumensath and M. E. Davies, Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14 (2008), 629-654. doi: 10.1007/s00041-008-9035-z.
[8]	T. Blumensath and M. E. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27 (2009), 265-274. doi: 10.1016/j.acha.2009.04.002.
[9]	T. Bonesky, Morozov's discrepancy principle and Tikhonov-type functionals, Inverse Problems, 25 (2009), 015015, 11 pp. doi: 10.1088/0266-5611/25/1/015015.
[10]	K. Bredies and D. A. Lorenz, Iterated hard shrinkage for minimization problems with sparsity constraints, SIAM J. Sci. Comput., 30 (2008), 657-683. doi: 10.1137/060663556.
[11]	K. Bredies and D. A. Lorenz, Regularization with non-convex separable constraints, Inverse Problems, 25 (2009), 085011, 14 pp. doi: 10.1088/0266-5611/25/8/085011.
[12]	K. Bredies, D. A. Lorenz and P. Maass, A generalized conditional gradient method and its connection to an iterative shrinkage method, Comput. Optim. Appl., 42 (2009), 173-193. doi: 10.1007/s10589-007-9083-3.
[13]	S. P. Chepuri and G. Leus, Sparsity-promoting sensor selection for non-linear measurement models, IEEE Trans. Signal Process., 63 (2015), 684-698. doi: 10.1109/TSP.2014.2379662.
[14]	I. Daubechies, M. Defrise and C. De Mol, Sparsity-enforcing regularisation and ISTA revisited, Inverse Problems, 32 (2016), 104001, 15 pp. doi: 10.1088/0266-5611/32/10/104001.
[15]	L. Ding and W. Han, $\alpha\ell_{1}-\beta\ell_{2}$ regularization for sparse recovery, Inverse Problems, 35 (2019), 125009, 26 pp. doi: 10.1088/1361-6420/ab34b5.
[16]	L. Ding and W. Han, A projected gradient method for $\alpha\ell_{1}-\beta\ell_{2}$ sparsity regularization, Inverse Problems, 36 (2020), 125012, 30 pp. doi: 10.1088/1361-6420/abc857.
[17]	L. Ding and W. Han, $\alpha\ell_{1}-\beta\ell_{2}$ sparsity regularization for nonlinear ill-posed problems, preprint, 2020, arXiv: 2007.11377v1.
[18]	H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Mathematics and its Applications vol 375: Dordrecht: Kluwer, 1996.
[19]	E. Esser, Y. Lou and J. Xin, A method for finding structured sparse solutions to non-negative least squares problems with applications, SIAM J. Imaging Sci., 6 (2013), 2010-2046. doi: 10.1137/13090540X.
[20]	M. Fornasier, eds, Theoretical Foundations and Numerical Methods for Sparse Recovery, De Gruyter, 2010. doi: 10.1515/9783110226157.93.
[21]	M. Fornasier and H. Rauhut, Iterative thresholding algorithms, Applied and Computational Harmonic Analysis, 25 (2008), 187-208. doi: 10.1016/j.acha.2007.10.005.
[22]	A. Frommer and P. Maass, Fast CG-based methods for Tikhonov-Phillips regularization, SIAM J. Sci. Comp., 20 (1999), 1831-1850. doi: 10.1137/S1064827596313310.
[23]	M. Grasmair, Well-posedness and convergence rates for sparse regularization with sublinear $\ell^q$ penalty term, Inverse Problems and Imaging, 3 (2009), 383-387. doi: 10.3934/ipi.2009.3.383.
[24]	M. Grasmair, M. Haltmeier and O. Scherzer, Sparse regularization with $\ell^q$ penalty term, Inverse Problems, 24 (2008), 055020, 13 pp. doi: 10.1088/0266-5611/24/5/055020.
[25]	M. Hanke, A. Neubauer and O. Scherzer, A convergence analysis of the Landweber iteration for nonlinear ill-posed problems, Numer. Math., 72 (1995), 21-37. doi: 10.1007/s002110050158.
[26]	P. C. Hansen, Regularization Tools version 4.0 for Matlab 7.3, Numerical Algorithms, 46 (2007), 189-194. doi: 10.1007/s11075-007-9136-9.
[27]	X.-L. Huang, L. Shi and M. Yan, Nonconvex sorted $\ell_1$ minimization for sparse approximation, J. Oper. Res. Soc. China, 3 (2015), 207-229. doi: 10.1007/s40305-014-0069-4.
[28]	B. Jin, D. A. Lorenz and S. Schiffer, Elastic-net regularization: Error estimates and active set methods, Inverse Problems, 25 (2009), 115022, 26 pp. doi: 10.1088/0266-5611/25/11/115022.
[29]	B. Jin and P. Maass, Sparsity regularization for parameter identification problems, Inverse Problems, 28 (2012), 123001, 70 pp. doi: 10.1088/0266-5611/28/12/123001.
[30]	B. Jin, P. Maass and O. Scherzer, Sparsity regularization in inverse problems, Inverse Problems, 33 (2017), 060301, 4 pp. doi: 10.1088/1361-6420/33/6/060301.
[31]	B. Jin, Y. Zhao and J. Zou, Iterative parameter choice by discrepancy principle, IMA J. Numer. Anal., 32 (2012), 1714-1732. doi: 10.1093/imanum/drr051.
[32]	B. Kaltenbacher, A. Neubauer and O. Scherzer, Iterative Regularization Methods for Nonlinear Ill-posed Problems, De Gruyter, 2012.
[33]	D. Lazzaro, E. L. Piccolomini and F. Zama, A nonconvex penalization algorithm with automatic choice of the regularization parameter in sparse imaging, Inverse Problems, 35 (2019), 084002, 17 pp. doi: 10.1088/1361-6420/ab1c6b.
[34]	P. Li, W. Chen, H. Ge and M. K. Ng, $\ell_1$-$\alpha\ell_2$ minimization methods for signal and image reconstruction with impulsive noise removal, Inverse Problems, 36 (2020), 055009, 30 pp. doi: 10.1088/1361-6420/ab750c.
[35]	Y. Lou and M. Yan, Fast L1-L2 minimization via a proximal operator, J. Sci. Comput., 74 (2018), 767-785. doi: 10.1007/s10915-017-0463-2.
[36]	A. K. Louis, Inverse und Schlecht Gestellte Probleme, Teubner: Stuttgart. 1989. doi: 10.1007/978-3-322-84808-6.
[37]	P. Maass, S. V. Pereverzev, R. Ramlau and S. G. Solodky, An adaptive discretization scheme for Tikhonov-regularization with a posteriori parameter selection, Numerische Mathematik, 87 (2001), 485-502. doi: 10.1007/PL00005421.
[38]	L. B. Montefusco, D. Lazzaro and S. Papi, A fast algorithm for nonconvex approaches to sparse recovery problems, Signal Proc., 93 (2013), 2636-2647.
[39]	V. A. Morozov, On the solution of functional equations by the method of regularization, Soviet Math. Dokl., 7 (1966), 414-417.
[40]	R. Ramlau, Morozov's discrepancy principle for Tikhonov regularization of nonlinear operators, Numer. Funct. Anal. Optim., 23 (2002), 147-172. doi: 10.1081/NFA-120003676.
[41]	O. Scherzer, M. Grasmair, H. Grossauer, M. Haltmeier and F. Lenzen, Variational Methods in Imaging, Applied Mathematical Sciences, Vol.167, Newyork: Springer, 2009.
[42]	T. Scherzer, B. Kaltenbacher, B. Hofmann and K. Kazimierski, Regularization Methods in Banach Spaces, De Gruyter, 2012. doi: 10.1515/9783110255720.
[43]	A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-Posed Problems, Winston Wiley: New York, 1977.
[44]	A. N. Tikhonov, A. S. Leonov and A. G. Yagola, Nonlinear Ill-Posed Problems, London: Chapman & Hall, 1998. doi: 10.1007/978-94-017-5167-4.
[45]	W. Wang, S. Lu, B. Hofmann and J. Cheng, Tikhonov regularization with $\ell_0$-term complementing a convex penalty: $\ell_1$-convergence under sparsity constraints, J. Inverse Ill-Posed Probl., 27 (2019), 575-590. doi: 10.1515/jiip-2019-0008.
[46]	W. Wang, S. Lu, H. Mao and J. Cheng, Multi-parameter Tikhonov regularization with the $\ell_0$ sparsity constrain, Inverse Problems, 29 (2013), 065018, 18 pp. doi: 10.1088/0266-5611/29/6/065018.
[47]	L. Yan, Y. Shin and D. Xiu, Sparse approximation using $\ell_1$-$\ell_2$ minimization and its application to stochastic collocation, SIAM J. Sci. Comput., 39 (2017), A214–A239. doi: 10.1137/15M103947X.
[48]	S. Yang, M. Wang, P. Li, L. Jin, B. Wu and L. Jiao, Compressive hyperspectral imaging via sparse tensor and nonlinear compressed sensing, IEEE Transactions on Geoscience and Remote Sensing, 53 (2015), 5943-5957.
[49]	P. Yin, Y. Lou, Q. He and J. Xin, Minimization of $\ell_{1-2}$ for compressed sensing, SIAM J. Sci. Comput., 37 (2015), A536–A563. doi: 10.1137/140952363.