Accelerated GNHSS iterative method for weighted Toeplitz regularized least-squares problems from image restoration. (English) Zbl 1413.65056
Summary: For fast solving weighted Toeplitz least-squares problems from image restoration, we establish an accelerated GNHSS (AGNHSS) method based on the Hermitian and skew-Hermitian splitting. The convergence of the new iteration method is established theoretically and its quasi-optimal iteration parameters are discussed. It is seen that the AGNHSS method converges faster when proper parameters are chosen. In particular, the convergence conditions of the AGNHSS method, the optimal parameters and some comparisons between AGNHSS and NSHSS are given when it is used for solving the linear image restoration problems. Meanwhile, the spectral properties of the preconditioned matrix are investigated. Experimental results further demonstrate that the new method is effective and confirm that our theoretical results are correct.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 15B05 | Toeplitz, Cauchy, and related matrices |
| 65F50 | Computational methods for sparse matrices |
| 65N20 | Numerical methods for ill-posed problems for boundary value problems involving PDEs |
Keywords:
HSS iteration method; preconditioning; image restoration; least squares problems; weighted Toeplitz matricesSoftware:
RestoreToolsReferences:
| [1] | Aghazadeh N, Bastani M (2015) Generalized Hermitian and skew-Hermitian splitting iterative method for image restoration. Appl Math Model 39:6126-6138 · Zbl 1443.94003 · doi:10.1016/j.apm.2015.01.042 |
| [2] | Aminikhah H, Yousefi M (2018) A special generalized HSS method for discrete ill-posed problems. Comp Appl Math 37:1507-1523 · Zbl 1405.65041 · doi:10.1007/s40314-016-0408-7 |
| [3] | Andrews H, Hunt B (1977) Digital image restoration. Prentice-Hall, Englewood Cliffs |
| [4] | Bai Z-Z (2006) Structured preconditioners for nonsingular matrices of block two-by-two structures. Math Comput 75:791-815 · Zbl 1091.65041 · doi:10.1090/S0025-5718-05-01801-6 |
| [5] | Bai Z-Z (2009) Optimal parameters in the HSS-like methods for saddle-point problems. Numer Linear Algebra Appl 16:447-479 · Zbl 1224.65081 · doi:10.1002/nla.626 |
| [6] | Bai Z-Z (2015) Motivations and realizations of Krylov subspace methods for large sparse linear systems. J Comput Appl Math 283:71-78 · Zbl 1311.65032 · doi:10.1016/j.cam.2015.01.025 |
| [7] | Bai Z-Z, Golub GH (2007) Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems. IMA J Numer Anal 27:1-23 · Zbl 1134.65022 · doi:10.1093/imanum/drl017 |
| [8] | Bai ZZ, Golub GH, Lu LZ, Yin J-F (2005) Block triangular and skew-Hermitian splitting methods for positive-definite linear systems. SIAM J Sci Comput 26:844-863 · Zbl 1079.65028 · doi:10.1137/S1064827503428114 |
| [9] | Bai Z-Z, Golub GH, Ng MK (2003) Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J Matrix Anal Appl 24:603-626 · Zbl 1036.65032 · doi:10.1137/S0895479801395458 |
| [10] | Bai Z-Z, Golub GH, Ng MK (2008) On inexact Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. Linear Algebra Appl 428:413-440 · Zbl 1135.65016 · doi:10.1016/j.laa.2007.02.018 |
| [11] | Bai ZZ, Golub GH, Pan J-Y (2004) Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems. Numer Math 98:1-32 · Zbl 1056.65025 · doi:10.1007/s00211-004-0521-1 |
| [12] | Bai Z-Z, Ng MK (2005) On inexact preconditioners for nonsymmetric matrices. SIAM J Sci Comput 26:1710-1724 · Zbl 1077.65043 · doi:10.1137/040604091 |
| [13] | Bai ZZ, Ng MK, Wang Z-Q (2009) Constraint preconditioners for symmetric indefinite matrices. SIAM J Matrix Anal Appl 31:410-433 · Zbl 1195.65033 · doi:10.1137/080720243 |
| [14] | Bai ZZ, Parlett BN, Wang Z-Q (2005) On generalized successive overrelaxation methods for augmented linear systems. Numer Math 102:1-38 · Zbl 1083.65034 · doi:10.1007/s00211-005-0643-0 |
| [15] | Bai ZZ, Wang ZQ (2008) On parameterized inexact Uzawa methods for generalized saddle point problems. Linear Algebra Appl 428:2900-2932 · Zbl 1144.65020 · doi:10.1016/j.laa.2008.01.018 |
| [16] | Benzi M, Gander M, Golub GH (2003) Optimization of the Hermitian and skew-Hermitian splitting iteration for saddle-point problems. BIT Numer Math 43:881-900 · Zbl 1052.65015 · doi:10.1023/B:BITN.0000014548.26616.65 |
| [17] | Benzi M, Golub GH (2004) A preconditioner for generalized saddle point problems. SIAM J Matrix Anal Appl 26:20-41 · Zbl 1082.65034 · doi:10.1137/S0895479802417106 |
| [18] | Benzi M, Ng MK (2006) Preconditioned iterative methods for weighted toeplitz least squares problems. SIAM J Matrix Anal Appl 27:1106-1124 · Zbl 1102.65050 · doi:10.1137/040616048 |
| [19] | Berman A, Plemmons RJ (1994) Nonnegative matrices in the mathematical sciences. SIAM, Philadelphia · Zbl 0815.15016 · doi:10.1137/1.9781611971262 |
| [20] | Cao AH (2002) A note on constraint preconditioning for nonsymmetric indefinite matrices. SIAM J Matrix Anal Appl 24:121-125 · Zbl 1018.65060 · doi:10.1137/S0895479801391424 |
| [21] | Chen F, Jiang YL (2008) A generalization of the inexact parameterized Uzawa methods for saddle point problems. Appl Math Comput 206:765-771 · Zbl 1159.65034 |
| [22] | Cheng GH, Rao X, Lv XG (2015) The comparisons of two special Hermitian and skew-Hermitian splitting methods for image restoration. Appl Math Model 39:1275-1280 · Zbl 1423.94005 · doi:10.1016/j.apm.2014.08.002 |
| [23] | Fessler JA, Booth SD (1999) Conjugate-gradient preconditioning methods for shift-variant PET image reconstruction. IEEE Trans Image Process 8:688-699 · Zbl 1099.94502 · doi:10.1109/83.760336 |
| [24] | Fischer B, Ramage R, Silvester D, Wathen A (1998) Minimum residual methods for augmented systems. BIT Numer Math 38:527-543 · Zbl 0914.65026 · doi:10.1007/BF02510258 |
| [25] | Hansen PC, Nagy JG, O’Leary DP (2006) Deblurring images: matrices spectra and filtering. SIAM, Philadelphia · Zbl 1112.68127 · doi:10.1137/1.9780898718874 |
| [26] | Jain A (1989) Fundamentals of digital image processing. Prentice-Hall, Englewood Cliffs · Zbl 0744.68134 |
| [27] | Kailath T, Sayed AH (1995) Displacement structure: theory and applications. SIAM Rev 37:297-386 · Zbl 0839.65028 · doi:10.1137/1037082 |
| [28] | Kamm J, Nagy JG (1998) Kronecker product and SVD approximations in image restoration. Linear Algebra Appl 284:177-192 · Zbl 0936.65052 · doi:10.1016/S0024-3795(98)10024-1 |
| [29] | Katsaggelos A (1991) Digital image restoration. Springer Ser. Inform. Sci, vol. 23. Springer-Verlag, New York |
| [30] | Li W, Liu YP, Peng XF (2012) The generalized HSS method for solving singular linear systems. J Comput Appl Math 236:2338-2353 · Zbl 1242.65061 · doi:10.1016/j.cam.2011.11.020 |
| [31] | Liao LD, Zhang GF (2017) New variant of the HSS iteration method for weighted Toeplitz regularized least-squares problems from image restoration. Comput Math Appl 73:2482-2499 · Zbl 1421.94009 · doi:10.1016/j.camwa.2017.03.027 |
| [32] | Lv XG, Huang TZ, Xu ZB, Zhao XL (2013) A special Hermitian and skew-Hermitian splitting method for image restoration. Appl Math Model 37:1069-1082 · Zbl 1351.94006 · doi:10.1016/j.apm.2012.03.019 |
| [33] | Nagy J, Palmer K, Perrone L (2002) RestoreTools: an object oriented Matlab package for image restoration. http://www.mathcs.emory.edu/ nagy/RestoreTools |
| [34] | Ng MK (2004) Iterative methods for toeplitz systems. Oxford University Press, Oxford, UK · Zbl 1059.65031 |
| [35] | Ng MK, Pan JY (2014) Weighted Toeplitz regularized least squares computation for image restoration. SIAM J Sci Comput 36:94-121 · Zbl 1307.65046 · doi:10.1137/120888776 |
| [36] | Perrone L (2006) Kronecker product approximations for image restoration with anti-reflective boundary conditions. Numer Linear Algebra Appl 13:1-22 · Zbl 1174.94309 · doi:10.1002/nla.458 |
| [37] | Rozlnonk M, Simoncini V (2002) Krylov subspace methods for saddle point problems with indefinite preconditioning. SIAM J Matrix Anal Appl 24:368-391 · Zbl 1021.65016 · doi:10.1137/S0895479800375540 |
| [38] | Saad Y (2003) Iterative methods for sparse linear systems. SIAM, Philadelphia · Zbl 1002.65042 · doi:10.1137/1.9780898718003 |
| [39] | Saad Y, Schultz MH (1986) GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J Sci Statist Comput 7:856-869 · Zbl 0599.65018 · doi:10.1137/0907058 |
| [40] | Simoncini V (2004) Block triangular preconditioners for symmetric saddle-point problems. Appl Numer Math 49:63-80 · Zbl 1053.65033 · doi:10.1016/j.apnum.2003.11.012 |
| [41] | Sturler ED, Liesen J (2005) Block-diagonal and constraint preconditioners for nonsymmetric indefinite linear systems. SIAM J Sci Comput 26:1598-1619 · Zbl 1078.65027 · doi:10.1137/S1064827502411006 |
| [42] | Yang AL, An J, Wu YJ (2010) A generalized preconditioned HSS method for non-Hermitian positive definite linear systems. Appl Math Comput 216:1715-1722 · Zbl 1198.65065 |
| [43] | Zak MK, Toutounian F (2016) A shifted nested splitting iterative method with applications to ill-posed problems and image restoration. Comput Math Appl 72:213-223 · Zbl 1443.65048 |
| [44] | Zulehner W (2002) Analysis of iterative methods for saddle point problems: a unified approach. Math Comp 71:479-505 · Zbl 0996.65038 · doi:10.1090/S0025-5718-01-01324-2 |
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.
