zbMATH — the first resource for mathematics

A note on the minimization of a Tikhonov functional with \(\ell^1\)-penalty. (English) Zbl 07220289
This paper is concerned with the minimization of a Tikhonov functional with an \(\ell^1\) penalty, arising from sparse reconstruction. The authors propose a transformation with \(\ell^2\) penalty and a nonlinear operator. The novelty lies in the fact that the resulting functional is a twice differentiable functional that can now be minimized using efficient second order methods, e.g., Newton’s method. The authors provide a convergence analysis of the scheme and several numerical experiments.
65J20 Numerical solutions of ill-posed problems in abstract spaces; regularization
47A52 Linear operators and ill-posed problems, regularization
Full Text: DOI
[1] Ramlau R and Teschke G 2006 A Tikhonov-based projection iteration for nonlinear ill-posed problems with sparsity constraints Numer. Math.104 177-203 · Zbl 1101.65056
[2] Ramlau R and Zarzer C 2012 On the minimization of a Tikhonov functional with a non-convex sparsity constraint Electron. Trans. Numer. Anal.39 467-505
[3] Scherzer O, Grasmair M, Grossauer H, Haltmeier M and Lenzen F 2009 Variational Methods in Imaging 167 (New York, NY: Springer) · Zbl 1177.68245
[4] Jin B and Maass P 2012 Sparsity regularization for parameter identification problems Inverse Problems28 123001 · Zbl 1280.47063
[5] Ramlau R and Resmerita E 2010 Convergence rates for regularization with sparsity constraints Electron. Trans. Numer. Anal.37 87-104 · Zbl 1206.47016
[6] Resmerita E 2005 Regularization of ill-posed problems in Banach spaces: convergence rates Inverse Problems21 08 · Zbl 1082.65055
[7] Jin B, Maaß P and Scherzer O 2017 Sparsity regularization in inverse problems Inverse Problems33 060301 · Zbl 1369.00102
[8] Weidling F, Sprung B and Hohage T 2020 Optimal convergence rates for Tikhonov regularization in Besov spaces SIAM J. Numer. Anal.58 21-47 · Zbl 07154055
[9] Daubechies I, Defrise M and De Mol C 2004 An iterative thresholding algorithm for linear inverse problems with a sparsity constraint Commun. Pure Appl. Math.57 1413-57 · Zbl 1077.65055
[10] Bredies K and Lorenz D 2008 Linear convergence of iterative soft-thresholding J. Fourier Anal. Appl.14 813-37 · Zbl 1175.65061
[11] Beck A and Teboulle M 2009 A fast iterative shrinkage-thresholding algorithm for linear inverse problems SIAM J. Imaging Sci.2 183-202 · Zbl 1175.94009
[12] Nesterov Y 1983 A method of solving a convex programming problem with convergence rate O(1/k2) Dokl. Akad. Nauk SSSR269 543-7
[13] Attouch H and Peypouquet J 2016 The rate of convergence of Nesterov’s accelerated forward-backward method is actually faster than O(1/k2) SIAM J. Optim.26 1824-34 · Zbl 1346.49048
[14] Candés E, Romberg J and Tao T 2006 Stable signal recovery from incomplete and inaccurate measurements Commun. Pure Appl. Math.59 1207-23 · Zbl 1098.94009
[15] Daubechies I, DeVore R, Fornasier M and Güntürk C 2010 Iteratively reweighted least squares minimization for sparse recovery Commun. Pure Appl. Math.63 1-38 · Zbl 1202.65046
[16] Donoho D and Tanner J 2005 Sparse nonnegative solution of underdetermined linear equations by linear programming Proc. Natl Acad. Sci. USA102 9446-51 · Zbl 1135.90368
[17] Buccini A and Reichel L 2019 An l2 − lp regularization method for large discrete ill-posed problems J. Sci. Comput.78 1526-49 · Zbl 07074397
[18] Huang G, Lanza A, Morigi S, Reichel L and Sgallari F 2017 Majorization-minimization generalized Krylov subspace methods for ℓp − ℓq optimization applied to image restoration BIT Numer. Math.57 351-78 · Zbl 1369.65073
[19] Lanza A, Morigi S, Reichel L and Sgallari F 2015 A generalized Krylov subspace method for ℓp − ℓq minimization SIAM J. Sci. Comput.37 30-50 · Zbl 1343.65077
[20] Ramlau R and Teschke G 2005 Tikhonov replacement functionals for iteratively solving nonlinear operator equations Inverse Problems21 1571-92 · Zbl 1078.47030
[21] Ramlau R and Teschke G 2010 Sparse recovery in inverse problems Theoretical Foundations and Numerical Methods for Sparse Recovery(Radon Series on Computational and Applied Mathematics) vol 9 ed Fornasier M (Berlin: De Gruyter) pp 201-62 · Zbl 1195.94005
[22] Bonesky T, Bredies K, Lorenz D A and Maass P 2007 A generalized conditional gradient method for nonlinear operator equations with sparsity constraints Inverse Problems23 2041-58 · Zbl 1131.65045
[23] Bredies K, Lorenz D A and Maass P 2009 A generalized conditional gradient method and its connection to an iterative shrinkage method Comput. Optim. Appl.42 173-93 · Zbl 1179.90326
[24] Griesse R and Lorenz D A 2008 A semismooth Newton method for Tikhonov functionals with sparsity constraints Inverse Problems24 035007 · Zbl 1152.49030
[25] Zarzer C 2009 On Tikhonov regularization with non-convex sparsity constraints Inverse Problems25 025006 · Zbl 1161.65044
[26] Acar R and Vogel C 1994 Analysis of bounded variation penalty methods for ill-posed problems Inverse Problems10 1217-29 · Zbl 0809.35151
[27] Korolev Y and Lellmann J 2018 Image reconstruction with imperfect forward models and applications in deblurring SIAM J. Imaging Sci.11 197-218 · Zbl 1401.94018
[28] Engl H W and Landl G 1993 Convergence rates for maximum entropy regularization SIAM J. Numer. Anal.30 1509-36 · Zbl 0790.65110
[29] Conway J B 1994 A Course in Functional Analysis(Graduate Texts in Mathematics) (New York, NY: Springer)
[30] Engl H W, Hanke M and Neubauer A 1996 Regularization of Inverse Problems (Dordrecht: Kluwer)
[31] Engl H W and Ramlau R 2015 Regularization of Inverse Problems(Encyclopedia of Applied and Computational Mathematics) ed Engquist B (Berlin: Springer) DOI: 10.1007/978-3-540-70529-1_52
[32] Neubauer A 1989 Tikhonov regularization for nonlinear ill-posed problems: optimal convergence and finite-dimensional approximation Inverse Problem5 541-57 · Zbl 0695.65038
[33] Pöschl C, Resmerita E and Scherzer O 2010 Discretization of variational regularization in Banach spaces Inverse Problems26 105017 · Zbl 1200.47018
[34] Kaltenbacher B, Neubauer A and Scherzer O 2008 Iterative Regularization Methods for Nonlinear Ill-Posed Problems (Berlin: de Gruyter) DOI: 10.1515/9783110208276 · Zbl 1145.65037
[35] Ramlau R 2003 TIGRA—an iterative algorithm for regularizing nonlinear ill-posed problems Inverse Problems19 433 · Zbl 1029.65059
[36] Hanke M 1997 A regularizing Levenberg-Marquardt scheme, with applications to inverse groundwater filtration problems Inverse Problems13 79 · Zbl 0873.65057
[37] Jin Q 2010 On a regularized Levenberg-Marquardt method for solving nonlinear inverse problems Numer. Math.115 229-59 · Zbl 1201.65087
[38] Blaschke B, Neubauer A and Scherzer O 1997 On convergence rates for the iteratively regularized Gauss-Newton method IMA J. Numer. Anal.17 421 · Zbl 0881.65050
[39] Jin Q and Tautenhahn U 2009 On the discrepancy principle for some Newton type methods for solving nonlinear inverse problems Numer. Math.111 509-58 · Zbl 1253.65087
[40] Hinze M, Pinnau R, Ulbrich M and Ulbrich S 2009 Optimization with PDE Constraints vol 23 (New York: Springer) p xii+270 · Zbl 1167.49001
[41] Neubauer A 2017 A new gradient method for ill-posed problems Numer. Funct. Anal. Optim.0 1-26 · Zbl 06866014
[42] Saxenhuber D 2016 Gradient-based reconstruction algorithms for atmospheric tomography in adaptive optics systems for extremely large telescopes PhD Thesis Johannes Kepler University Linz
[43] Natterer F 2001 The Mathematics of Computerized Tomography (Philadelphia, PA: Society for Industrial and Applied Mathematics) DOI: 10.1137/1.9780898719284 · Zbl 0973.92020
[44] Hansen P C and Jorgensen J 2017 Air tools ii: algebraic iterative reconstruction methods, improved implementation Numer. Algorithms79 11 · Zbl 1397.65007
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.