×

Modulus-based iterative methods for constrained \(\ell_p\)-\(\ell_q\) minimization. (English) Zbl 1451.65072

Summary: The need to solve discrete ill-posed problems arises in many areas of science and engineering. Solutions of these problems, if they exist, are very sensitive to perturbations in the available data. Regularization replaces the original problem by a nearby regularized problem, whose solution is less sensitive to the error in the data. The regularized problem contains a fidelity term and a regularization term. Recently, the use of a \(p\)-norm to measure the fidelity term and a \(q\)-norm to measure the regularization term has received considerable attention. The balance between these terms is determined by a regularization parameter. In many applications, such as in image restoration, the desired solution is known to live in a convex set, such as the nonnegative orthant. It is natural to require the computed solution of the regularized problem to satisfy the same constraint(s). This paper shows that this procedure induces a regularization method and describes a modulus-based iterative method for computing a constrained approximate solution of a smoothed version of the regularized problem. Convergence of the iterative method is shown, and numerical examples that illustrate the performance of the proposed method are presented.

MSC:

65K05 Numerical mathematical programming methods
65F22 Ill-posedness and regularization problems in numerical linear algebra
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Engl H W, Hanke M and Neubauer A 1996 Regularization of Inverse Problems (Dordrecht: Kluwer) · Zbl 0859.65054 · doi:10.1007/978-94-009-1740-8
[2] Hansen P C 1994 Regularization tools: a Matlab package for analysis and solution of discrete ill-posed problems Numer. Algorithms6 1-35 · Zbl 0789.65029 · doi:10.1007/bf02149761
[3] Hansen P C 1998 Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion (Philadelphia, PA: SIAM) · Zbl 0890.65037 · doi:10.1137/1.9780898719697
[4] Estatico C, Gratton S, Lenti F and Titley-Peloquin D 2017 A conjugate gradient like method for p-norm minimization in functional spaces Numer. Math.137 895-922 · Zbl 1379.65029 · doi:10.1007/s00211-017-0893-7
[5] 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 · doi:10.1007/s10543-016-0643-8
[6] Lanza A, Morigi S, Reichel L and Sgallari F 2015 A generalized Krylov subspace method for ℓp-ℓq minimization SIAM J. Sci. Comput.37 S30-50 · Zbl 1343.65077 · doi:10.1137/140967982
[7] Cai J-F, Osher S and Shen Z 2009 Linearized Bregman iterations for frame-based image deblurring SIAM J. Imaging Sci.2 226-52 · Zbl 1175.94010 · doi:10.1137/080733371
[8] Lanza A, Morigi S and Sgallari F 2016 Constrained TVp-ℓ2 model for image restoration J. Sci. Comput.68 64-91 · Zbl 1344.65025 · doi:10.1007/s10915-015-0129-x
[9] 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 · doi:10.1137/080716542
[10] Xie Z and Hu J 2013 Reweighted ℓ1-minimization for sparse solutions to underdetermined linear systems 2013 6th Int. Congress on Image and Signal Processing (CISP)vol 3 pp 1660-4 · doi:10.1109/CISP.2013.6743943
[11] Candès E J, Romberg J and Tao T 2006 Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information IEEE Trans. Inf. Theory52 489-509 · Zbl 1231.94017 · doi:10.1109/tit.2005.862083
[12] Donoho D L 2006 Compressed sensing IEEE Trans. Inf. Theory52 1289-306 · Zbl 1288.94016 · doi:10.1109/tit.2006.871582
[13] Liu Z, Wei Z and Sun W 2014 An iteratively approximated gradient projection algorithm for sparse signal reconstruction Appl. Math. Comput.228 454-62 · Zbl 1364.94141 · doi:10.1016/j.amc.2013.10.063
[14] Tou J T and Gonzalez R C 1974 Pattern Recognition Principles (Boston, MA: Addison-Wesley) · Zbl 0299.68058
[15] Lai M-J, Xu Y and Yin W 2013 Improved iteratively reweighted least squares for unconstrained smoothed ℓq minimization SIAM J. Numer. Anal.51 927-57 · Zbl 1268.49038 · doi:10.1137/110840364
[16] Bai Z-Z 2010 Modulus-based matrix splitting iteration methods for linear complementarity problems Numer. Linear Algebr. Appl.17 917-33 · Zbl 1240.65181 · doi:10.1002/nla.680
[17] Buccini A and Reichel L 2019 An ℓ2-ℓq regularization method for large discrete ill-posed problems J. Sci. Comput.78 1526-49 · Zbl 1502.65017 · doi:10.1007/s10915-018-0816-5
[18] Bredies K and Lorenz D A 2009 Regularization with non-convex separable constraints Inverse Problems25 085011 · Zbl 1180.65068 · doi:10.1088/0266-5611/25/8/085011
[19] 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 · doi:10.1002/cpa.20042
[20] Grasmair M 2010 Non-convex sparse regularisation J. Math. Anal. Appl.365 19-28 · Zbl 1186.65067 · doi:10.1016/j.jmaa.2009.09.055
[21] Hofmann B, Kaltenbacher B, Poeschl C and Scherzer O 2007 A convergence rates result for tikhonov regularization in banach spaces with non-smooth operators Inverse Problems23 987-1010 · Zbl 1131.65046 · doi:10.1088/0266-5611/23/3/009
[22] Zheng N, Hayami K and Yin J-F 2016 Modulus-type inner outer iteration methods for nonnegative constrained least squares problems SIAM J. Matrix Anal. Appl.37 1250-78 · Zbl 1348.65069 · doi:10.1137/141002220
[23] Bai Z-Z, Buccini A, Hayami K, Reichel L, Yin J-F and Zheng N 2017 Modulus-based iterative methods for constrained Tikhonov regularization J. Comput. Appl. Math.319 1-13 · Zbl 1360.65112 · doi:10.1016/j.cam.2016.12.023
[24] Cottle R, Pang J-S and Venkateswaran V 1989 Sufficient matrices and the linear complementarity problem Linear Algebr. Appl.114 231-49 · Zbl 0674.90092 · doi:10.1016/0024-3795(89)90463-1
[25] Daniel J W, Gragg W B, Kaufman L and Stewart G W 1976 Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization Math. Comput.30 772-95 · Zbl 0345.65021 · doi:10.2307/2005398
[26] Baglama J and Reichel L 2005 Augmented implicitly restarted Lanczos bidiagonalization methods SIAM J. Sci. Comput.27 19-42 · Zbl 1087.65039 · doi:10.1137/04060593x
[27] Hansen P C, Nagy J G and O’Leary D P 2006 Deblurring Images: Matrices, Spectra, and Filtering (Philadelphia, PA: SIAM) · Zbl 1112.68127 · doi:10.1137/1.9780898718874
[28] Mairal J 2015 Incremental majorization-minimization optimization with application to large-scale machine learning SIAM J. Optim.25 829-55 · Zbl 1320.90047 · doi:10.1137/140957639
[29] Cai J-F, Osher S and Shen Z 2009 Split Bregman methods and frame based image restoration Multiscale Model. Simul.8 337-69 · Zbl 1189.94014 · doi:10.1137/090753504
[30] Huang J, Donatelli M and Chan R H 2013 Nonstationary iterated thresholding algorithms for images deblurring Inverse Problems Imaging7 717-36 · Zbl 1318.94015 · doi:10.3934/ipi.2013.7.717
[31] Cai Y, Donatelli M, Bianchi D and Huang T-Z 2016 Regularization preconditioners for frame-based image deblurring with reduced boundary artifacts SIAM J. Sci. Comput.38 B164-89 · Zbl 1382.94010 · doi:10.1137/140976261
[32] Buccini A and Reichel L 2020 An ℓp-ℓq minimization method with cross-validation for the restoration of impulse noise contaminated images J. Comput. Appl. Math.375 112824 · Zbl 1524.94008 · doi:10.1016/j.cam.2020.112824
[33] Wang Z, Bovik A C, Sheikh H R and Simoncelli E P 2004 Image quality assessment: from error visibility to structural similarity IEEE Trans. Image Process.13 600-12 · doi:10.1109/tip.2003.819861
[34] Buzug T M 2011 Computed tomography Springer Handbook of Medical Technology ed R Kramme, K-P Hoffmann and R S Pozos (Berlin: Springer) pp 311-42 · doi:10.1007/978-3-540-74658-4_16
[35] Gazzola S, Hansen P C and Nagy J G 2019 IR tools: a MATLAB package of iterative regularization methods and large-scale test problems Numer. Algorithms81 773-811 · Zbl 1415.65003 · doi:10.1007/s11075-018-0570-7
[36] Hämäläinen K, Harhanen L, Kallonen A, Kujanpää A, Niemi E and Siltanen S 2015 Tomographic x-ray data of a walnut (arXiv:1502.04064)
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.