×

zbMATH — the first resource for mathematics

A generalized matrix Krylov subspace method for TV regularization. (English) Zbl 07193286
Summary: This paper presents efficient algorithms to solve both TV/L1 and TV/L2 models of images contaminated by blur and noise. The unconstrained structure of the problems suggests that one can solve a constrained optimization problem by transforming the original unconstrained minimization problem to an equivalent constrained minimization one. An augmented Lagrangian method is developed to handle the constraints when the model is given with matrix variables, and an alternating direction method (ADM) is used to iteratively find solutions of the subproblems. The solutions of some subproblems are belonging to subspaces generated by application of successive orthogonal projections onto a class of generalized matrix Krylov subspaces of increasing dimension. We give some theoretical results and report some numerical experiments to show the effectiveness of the proposed algorithms.
MSC:
65 Numerical analysis
90 Operations research, mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrews, H.; Hunt, B., Digital Image Restoration (1977), Prentice-Hall: Prentice-Hall Engelwood Cliffs
[2] Bertero, M.; Boccacci, P., Introduction to Inverse Problems in Imaging (1998), IOP Publishing: IOP Publishing London
[3] Chalmond, B., Modeling and Inverse Problems in Image Analysis (2003), Springer: Springer New York
[4] Hansen, P. C.; Nagy, J. G.; O’Leary, D. P., Deblurring Images: Matrices, Spectra, and Filtering (2006), SIAM: SIAM Philadelphi
[5] Jain, A. K., Fundamentals of Digital Image Processing (1989), Prentice-Hall: Prentice-Hall Engelwood Cliffs
[6] Goldstein, T.; Osher, S., The split Bregman L1 regularized problems, SIAM J. Imaging Sci., 2, 323-343 (2009)
[7] Guerrero, J.; Raydan, M.; Rojas, M., A hybrid-optimization method for large-scale non-negative full regularization in image restoration, Inverse Probl. Sci. Eng., 21, 741-766 (2013)
[8] Tikhonov, A.; Arsenin, V., Solution of Ill-Posed Problems (1977)
[9] Rudin, L.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Physica D, 60, 259-268 (1992)
[10] Vogel, C. R.; Oman, M. E., Fast, robust total variation-based reconstruction of noisy blurred images, IEEE Trans. Image Process., 7, 813-824 (1998)
[11] Vogel, C. R., Computational Methods for Inverse Problems (2002), SIAM: SIAM Philadelphia, PA
[12] Wright, S. J.; Figueiredo, M. A.T.; Nowak, R. D., Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57, 2479-2493 (2009)
[13] Galatsanos, N. P.; Katsaggelos, A. K.; Chin, R. T.; Hillary, A. D., Least squares restoration of multichannel images, IEEE Trans. Signal Proc., 39, 2222-2236 (1991)
[14] Li, F.; Ng, M. K.; Plemmons, R. J., Coupled segmentation and denoising/deblurring for hyperspectral material identification, Numer. Linear Algebra Appl., 19, 15-17 (2012)
[15] Hestenes, M. R., Multiplier and gradient methods, J. Optim. Theory Appl., 4, 303-320 (1969), and in Computing Methods in Optimization Problems, 2 ( Eds L.A. Zadeh, L.W. Neustadt, and A.V. Balakrishnan) Academic Press, New York, 1969
[16] Powell, M. J.D., (Fletcher, R., A Method for Nonlinear Constraints in Minimization Problems, Optimization (1969), Academic Press: Academic Press London, New York), 283-298
[17] Martinez, M.; Birgin, E. G., Practical augmented Lagrangian methods for constrained optimization, J. SIAM (2014)
[18] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appl., 2, 17-40 (1976)
[19] Li, C., An Efficient Algorithm for Total Variation Regularization with Applications to the Single Pixel Camera and Compressive Sensing (2009), Rice University, available at http://www.caam.rice.edu/optimization/L1/TVAL3/tval3thesis.pdf
[20] Bentbib, A. H.; El Guide, M.; Jbilou, K.; Onunwor, E.; Reichel, L., Solution methods for linear discrete ill-posed problems for color image restoration, BIT, 58, 555-578 (2018)
[21] Bentbib, A. H.; El Guide, M.; Jbilou, K.; Reichel, L., Global Golub-Kahan bidiagonalization applied to large discrete ill-posed problems, J. Comput. Appl. Math., 322, 46-56 (2017)
[22] Bentbib, A. H.; El Guide, M.; Jbilou, K.; Reichel, L., A global Lanczos method for image restoration, J. Comput. Appl. Math., 300, 233-244 (2016)
[23] Glowinski, R., Numerical Methods for Nonlinear Variational Problems (2008), Springer Verlag
[24] He, B.; Liao, L.; Han, D.; Yang, H., A new inexact alternating directions method for monotone variational inequalities, Math. Program., 92, 103-118 (2002)
[25] Facchinei, F.; Pang, J. S., (Finite-Dimensional Variational Inequalities and Complementarity Problems. Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Series in Operations Research (2003), Springer-Verlag: Springer-Verlag Berlin)
[26] Rockafellar, R. T., Convex Analysis (1970), Princeton University Press: Princeton University Press Princeton, NJ
[27] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1-122 (2011)
[28] Wu, C. L.; Zhang, J. Y.; Tai, X. C., Augmented Lagrangian method for total variation restoration with non-quadratic fidelity, Inverse Probl. Imaging, 5, 237-261 (2010)
[29] Lampe, J.; Reichel, L.; Voss, H., Large-scale Tikhonov regularization via reduction by orthogonal projection, Linear Algebra Appl., 436, 2845-2865 (2012)
[30] Bouhamidi, A.; Jbilou, K.; Raydan, M., Convex constrained optimization for large-scale generalized Sylvester equations, Comput. Optim. Appl., 48, 233-253 (2011)
[31] Lanza, A.; Morigi, S.; Reichel, L.; Sgallari, F., A generalized Krylov subspace method for \(\ell_p - \ell_q\) minimization, SIAM J. Sci. Comput., 37, 30-50 (2015)
[32] Jbilou, K.; Messaoudi, A.; Sadok, H., Global FOM and GMRES algorithms for matrix equations, Appl. Numer. Math., 31, 49-63 (1999)
[33] Bouhamidi, A.; Jbilou, K., A note on the numerical approximate solution for generalized Sylvester Matrix equations, Appl. Math. Comput., 206, 687-694 (2008)
[34] Bouyouli, R.; Jbilou, K.; Sadaka, R.; Sadok, H., Convergence properties of some block Krylov subspace methods for multiple linear systems, J. Comput. Appl. Math., 196, 498-511 (2006)
[35] Hansen, P. C., Regularization tools version 4.0 for MATLAB 7.3, Numer. Algorithms, 46, 189-194 (2007)
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.