Matrix forms of iterative algorithms to solve large-scale discrete ill-posed problems with an application to image restoration. (English) Zbl 1468.65036
Summary: Iterative methods to solve linear large-scale discrete problems are well known in the literature. When the linear system is ill-posed and contaminated by noise, some kind of regularization must be applied in order to achieve a feasible solution. In the first part of this paper, we revisit briefly some known methods to solve large-scale ill-posed discrete linear problems which are easy to implement and have low computational cost, formulating them in a unified manner and also proposing simple modifications in order to improve their performances. Matrix forms of iterative algorithms can be formulated depending on certain conditions on the blurring process, and have the advantage of avoiding the formation and storage in memory of the matrix that represents the blurring process, which is generally of very large dimension. As an original contribution, in the final part of this paper we present the matrix forms of the iterative algorithms revisited and test them in the problem of restoration of an image degraded by blurring and noise.
MSC:
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
| 65F10 | Iterative numerical methods for linear systems |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
Keywords:
discrete ill-posed linear problems; iterative algorithms; Tikhonov regularization; Krylov subspaces; image restorationReferences:
| [1] | Ascher, U., van den Doel, K., Huang, H., Svaiter, B.: On fast integration to steady state and earlier times. Math. Model. Numer. Anal. 43, 689-708 (2009) · Zbl 1169.65329 · doi:10.1051/m2an/2009025 |
| [2] | Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141-148 (1988). https://doi.org/10.1093/imanum/8.1.141 · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141 |
| [3] | Bauer, F., Lukas, M.A.: Comparing parameter choice methods for regularization of ill-posed problems. Math. Comput. Simul. 81, 1795-1841 (2011). https://doi.org/10.1016/j.matcom.2011.01.016 · Zbl 1220.65063 · doi:10.1016/j.matcom.2011.01.016 |
| [4] | Bhaya, A., Bliman, P.-A., Pazos, F.: Control-theoretic design of iterative methods for symmetric linear systems of equations. In: Proceedings of the 48th IEEE Conference on Decision and Control, Shanghai, China (2009). https://doi.org/10.1109/CDC.2009.5399581 · Zbl 1375.65050 |
| [5] | Calvetti, D., Reichel, L., Zhang, Q.: Iterative Solution Methods for Large Linear Discrete Ill-Posed Problems, vol. 1, pp. 313-367. Birkhäuser, Boston (1999). https://doi.org/10.1007/978-1-4612-0571-5_7 · Zbl 0979.93033 · doi:10.1007/978-1-4612-0571-5_7 |
| [6] | Engl, H., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Kluwer Academic Publishers, London (1996) · Zbl 0859.65054 · doi:10.1007/978-94-009-1740-8 |
| [7] | Wang, Y.-F., Xiao, T.-Y.: Fast realization algorithms for determining regularization parameters in linear inverse problems. Inverse Probl. 17, 281-291 (2001). https://doi.org/10.1088/0266-5611/17/2/308 · Zbl 0989.65062 · doi:10.1088/0266-5611/17/2/308 |
| [8] | Frommer, A., Maass, P.: Fast CG-based methods for Tikhonov-Phillips regularization. SIAM J. Sci. Comput. 20, 1831-1850 (1999) · Zbl 0943.65068 · doi:10.1137/S1064827596313310 |
| [9] | Gazzola, S., Novati, P., Russo, M.R.: On Krylov projection methods and Tikhonov regularization. Electron. Trans. Numer. Anal. 44, 83-123 (2015) · Zbl 1312.65065 |
| [10] | Golub, G., Heath, M., Wahba, G.: Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics 21, 215-223 (1979). https://doi.org/10.1080/00401706.1979.10489751 · Zbl 0461.62059 · doi:10.1080/00401706.1979.10489751 |
| [11] | Golub, G., Van Loan, C.: Matrix Computation. The Johns Hopkins University Press, Baltimore (1989) · Zbl 0733.65016 |
| [12] | Golub, G., von Matt, U.: Quadratically constrained least squares and quadratic problems. Numer. Math. 59, 561-580 (1991). https://doi.org/10.1007/BF01385796 · Zbl 0745.65029 · doi:10.1007/BF01385796 |
| [13] | Golub, G.; Matt, U.; Golub, GH (ed.); Lui, SH (ed.); Luk, F. (ed.); Plemmons, R. (ed.), Tikhonov regularization for large scale problems, 3-26 (1997), New York · Zbl 0927.65058 |
| [14] | Greenbaum, A.: Iterative Methods for Solving Linear Systems. SIAM, Philadelphia (1997) · Zbl 0883.65022 · doi:10.1137/1.9781611970937 |
| [15] | Güler, O.: Fundations of Optimization. Graduate Texts in Mathematics. Springer, Berlin (2010) · Zbl 1220.90001 |
| [16] | Hanke, M.; Colton, D. (ed.); Engl, HW (ed.); Louis, AK (ed.); McLaughlin, JR (ed.); Rundell, W. (ed.), Iterative regularization techniques in image reconstruction, 35-52 (2000), Vienna · Zbl 0972.65123 · doi:10.1007/978-3-7091-6296-5_3 |
| [17] | Hanke, M., Nagy, J.G.: Restoration of atmospherically blurred images by symmetric indefinite conjugate gradient techniques. Inverse Probl. 12, 157-173 (1996). https://doi.org/10.1088/0266-5611/12/2/004 · Zbl 0859.65141 · doi:10.1088/0266-5611/12/2/004 |
| [18] | Hansen, P.C.: The L-curve and its use in the numerical treatment of inverse problems. In: Johnston, P. (ed.) Computational Inverse Problems in Electrocardiology, Advances in Computational Bioengineering. IMM, Department of Mathematical Modelling, Technical University of Denmark (2000) |
| [19] | Hansen, P.C.: Regularization tools: a MATLAB package for analysis and solution of discrete ill-posed problems. Numer. Algorithms 46, 189-194 (2007). https://doi.org/10.1007/s11075-007-9136-9 · Zbl 1128.65029 · doi:10.1007/s11075-007-9136-9 |
| [20] | Hansen, P.C., Nagy, J., O’Leary, D.P.: Deblurring Images. Matrices, Spectra and Filtering, Fundamentals of Algorithms. SIAM, Philadelphia (2006) · Zbl 1112.68127 · doi:10.1137/1.9780898718874 |
| [21] | Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49, 409-436 (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044 |
| [22] | Hochstenbach, M.E., Reichel, L., Rodriguez, G.: Regularization parameter determination for discrete ill-posed problems. J. Comput. Appl. Math. 273, 132-149 (2015). https://doi.org/10.1016/j.cam.2014.06.004 · Zbl 1295.65046 · doi:10.1016/j.cam.2014.06.004 |
| [23] | Jain, A.: Fundamentals of Digital Image Processing. Prentice-Hall, Englewood Cliffs, NJ (1989) · Zbl 0744.68134 |
| [24] | Jensen, T.K., Hansen, P.C.: Iterative regularization with minimum-residual methods. BIT Numer. Math. 47, 103-120 (2007). https://doi.org/10.1007/s10543-006-0109-5 · Zbl 1113.65037 · doi:10.1007/s10543-006-0109-5 |
| [25] | Kilmer, M., O’Leary, D.P.: Choosing regularization parameters in iterative methods for ill-posed problems. SIAM J. Matrix Anal. Appl. 22, 1204-1221 (2001). https://doi.org/10.1137/S0895479899345960 · Zbl 0983.65056 · doi:10.1137/S0895479899345960 |
| [26] | Kunisch, K., Zou, J.: Iterative choices of regularization parameters in linear inverse problems. Inverse Probl. 14, 1247-1264 (1998). https://doi.org/10.1088/0266-5611/14/5/010 · Zbl 0917.65053 · doi:10.1088/0266-5611/14/5/010 |
| [27] | Morozov, V.A.: Regularization Methods for Ill-Posed Problems. CRC Press, Albany, NY (1993) · Zbl 0848.65046 |
| [28] | Nagy, J.G., Palmer, K.M.: Steepest descent, CG and iterative regularization of ill posed problems. BIT Numer. Math. 43, 1003-1017 (2003). https://doi.org/10.1023/B:BITN.0000014546.51341.53 · Zbl 1045.65034 · doi:10.1023/B:BITN.0000014546.51341.53 |
| [29] | Nagy, J.G., Palmer, K.M.: Quasi-Newton methods for image restoration. In: Proceedings of SPIE—The International Society for Optical Engineering, vol. 5559, pp. 412-422 (2004). https://doi.org/10.1117/12.561060 |
| [30] | Nagy, J.G., O’Leary, D.P.: Fast iterative image restoration with a spatially-varying PSF. In: Luk, F.T. (ed.) Proceedings of SPIE—The International Society for Optical Engineering, vol. 3162, pp. 388-399. San Diego, CA, USA (1997). https://doi.org/10.1117/12.279513 |
| [31] | Nagy, J.G., O’Leary, D.P.: Restoring images degraded by spatially variant blur. SIAM J. Sci. Comput. 19, 1063-1082 (1998). https://doi.org/10.1137/S106482759528507X · Zbl 0919.65091 · doi:10.1137/S106482759528507X |
| [32] | Novati, P., Russo, M.R.: Adaptive Arnoldi-Tikhonov regularization for image restoration. Numer. Algorithms 65, 745-757 (2014). https://doi.org/10.1007/s11075-013-9712-0 · Zbl 1298.65071 · doi:10.1007/s11075-013-9712-0 |
| [33] | Paige, C.C., Saunders, M.A.: LSQR: sparse linear equations and least squares problems. ACM Trans. Math. Softw. 8, 195-209 (1982). https://doi.org/10.1145/355993.356000 · Zbl 0478.65016 · doi:10.1145/355993.356000 |
| [34] | Pazos, F., Bhaya, A.: Matrix forms of gradient descent algorithms applied to restoration of blurred images. Int. J. Signal Process. Image Process. Pattern Recognit. 7, 17-28 (2014). https://doi.org/10.14257/ijsip.2014.7.6.02 · doi:10.14257/ijsip.2014.7.6.02 |
| [35] | Pazos, F., Bhaya, A.: Adaptive choice of the Tikhonov regularization parameter to solve ill-posed linear algebraic equations via Liapunov optimizing control. J. Comput. Appl. Math. 279, 123-132 (2015). https://doi.org/10.1016/j.cam.2014.10.022 · Zbl 1306.65194 · doi:10.1016/j.cam.2014.10.022 |
| [36] | Regińska, T.: A regularization parameter in discrete ill-posed problems. SIAM J. Sci. Comput. 17, 740-749 (1996). https://doi.org/10.1137/S1064827593252672 · Zbl 0865.65023 · doi:10.1137/S1064827593252672 |
| [37] | Reichel, L., Rodriguez, G.: Old and new parameter choice rules for discrete ill-posed problems. Numer. Algorithms 63, 65-87 (2013). https://doi.org/10.1007/s11075-012-9612-8 · Zbl 1267.65045 · doi:10.1007/s11075-012-9612-8 |
| [38] | Reichel, L., Shyshkov, A.: A new zero-finder for Tikhonov regularization. BIT Numer. Math. 48, 627-643 (2008). https://doi.org/10.1007/s10543-008-0179-7 · Zbl 1161.65029 · doi:10.1007/s10543-008-0179-7 |
| [39] | Tikhonov, A.N., Arsenin, V.Y.: Solutions of Ill-Posed Problems. Winston & Sons, Washignton, DC (1977) · Zbl 0354.65028 |
| [40] | Xie, J., Zou, J.: An improved model function method for choosing regularization parameters in linear inverse problems. Inverse Probl. 18, 631-643 (2002). https://doi.org/10.1088/0266-5611/18/3/307 · Zbl 1012.65050 · doi:10.1088/0266-5611/18/3/307 |
| [41] | You, Y.-L., Kaveh, M.: Regularization and image restoration using differential equations. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), vol. 5, pp. 285-288 (1993). https://doi.org/10.1109/ICASSP.1993.319803 |
| [42] | Zhang, D., Huang, T.-Z.: Generalized Tikhonov regularization method for large-scale linear inverse problems. J. Comput. Anal. Appl. 15, 1317-1331 (2013) · Zbl 1273.65066 |
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.
