DETERIORATED HSS-LIKE METHODS FOR THE WEIGHTED TOEPLITZ LEAST SQUARES PROBLEM FROM IMAGE RESTORATION

Min-Li Zeng

doi:10.11948/20200372

2021 Volume 11 Issue 4

Article Contents

Article navigation > Journal of Applied Analysis & Computation > 2021 > 11(4): 2131-2150

Next Article Previous Article

Min-Li Zeng. DETERIORATED HSS-LIKE METHODS FOR THE WEIGHTED TOEPLITZ LEAST SQUARES PROBLEM FROM IMAGE RESTORATION[J]. Journal of Applied Analysis & Computation, 2021, 11(4): 2131-2150. doi: 10.11948/20200372

Citation:

Min-Li Zeng. DETERIORATED HSS-LIKE METHODS FOR THE WEIGHTED TOEPLITZ LEAST SQUARES PROBLEM FROM IMAGE RESTORATION[J]. Journal of Applied Analysis & Computation, 2021, 11(4): 2131-2150. doi: 10.11948/20200372

DETERIORATED HSS-LIKE METHODS FOR THE WEIGHTED TOEPLITZ LEAST SQUARES PROBLEM FROM IMAGE RESTORATION

Min-Li Zeng^1,2, ,

1.
School of Mathematics and Finance, Putian University, Fujian 351100, China
2.
Key Laboratory of Financial Mathematics (Putian University), Fujian Province Universities, Fujian 351100, China

Corresponding author: Email: ptzengminli@gmail.com (M. Zeng)
Fund Project: The work was supported by the National Natural Science Foundation of China (No. 11901324), the Natural Science Foundation of Fujian Province (No. 2020J01906) and the Program for Innovative Research Team in Science and Technology in Fujian Province University (No. 2018-39)

Abstract

Abstract

In this paper, we construct a deteriorated HSS-like (DHSS-like) iteration method for a class of large and sparse block two-by-two linear systems from image restoration. The detailed spectral properties and the quasi-optimal iteration parameters are investigated in detail. Because the DHSS-like iteration method naturally leads to a DHSS-like preconditioner, then we can use the circulant matrix to replace the Toeplitz matrix in the DHSS-like preconditioner approximately to obtain a circulant matrix-based DHSS-like (CDHSS-like) preconditioner. It is pointed out that the workload of the new preconditioned method is about $ O(n\log n) $. Theoretically analysis shows that the eigenvalues of the CDHSS-like preconditioned matrix are clustered around 1. Implementations in linear systems from the image restoration problems are made to verify the correctness of the theoretical results and the efficiency of both the CDHSS-like iteration method and the CDHSS-like preconditioned method.
- Deteriorated HSS-like method /
- matrix splitting iteration method /
- convergence /
- preconditioner /
- Krylov subspace method
MSC: 65F08, 65F10, 65F50

FullText(HTML)

References

[1]	N. Aghazadeh, M. Bastani and D. K. Salkuyeh, Generalized Hermitian and skew-Hermitian splitting iterative method for image restoration, Appl. Math. Model., 2015, 39(20), 6126-6138. doi: 10.1016/j.apm.2015.01.042 CrossRef Google Scholar
[2]	Z. Bai and Z. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl., 2008, 428(11-12), 2900-2932. doi: 10.1016/j.laa.2008.01.018 CrossRef Google Scholar
[3]	Z. Bai, M. Benzi, F. Chen and Z. Wang, Preconditioned MHSS iteration methods for a class of block two-by-two linear systems with applications to distributed control problems, IMA J. Numer. Anal., 2012, 33(1), 343-369. Google Scholar
[4]	Z. Bai, F. Chen and Z. Wang, Additive block diagonal preconditioning for block two-by-two linear systems of skew-Hamiltonian coefficient matrices, Numer. Algorithms, 2013, 62(4), 655-675. doi: 10.1007/s11075-013-9696-9 CrossRef Google Scholar
[5]	Z. Bai, G. H. Golub and M. K. Ng, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 2003, 24(3), 603-626. doi: 10.1137/S0895479801395458 CrossRef Google Scholar
[6]	Z. Bai, B. N. Parlett and Z. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math., 2005, 102(1), 1-38. doi: 10.1007/s00211-005-0643-0 CrossRef Google Scholar
[7]	M. Benzi and M. K. Ng, Preconditioned iterative methods for weighted Toeplitz least squares problems, SIAM J. Matrix Anal. Appl., 2006, 27(4), 1106-1124. doi: 10.1137/040616048 CrossRef Google Scholar
[8]	Y. Cao, J. Dong and Y. Wang, A relaxed deteriorated PSS preconditioner for nonsymmetric saddle point problems from the steady Navier-stokes equation, J. Comput. Appl. Math., 2015, 273(1), 41-60. Google Scholar
[9]	Y. Cao, Z. Ren and Q. Shi. A simplified HSS preconditioner for generalized saddle point problems, BIT, 2016, 56(2), 423-439. doi: 10.1007/s10543-015-0588-3 CrossRef Google Scholar
[10]	R. H. Chan and M. K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev., 1996, 38(3), 427-482. doi: 10.1137/S0036144594276474 CrossRef Google Scholar
[11]	J. Cui, G. Peng, Q. Lu and Z. Huang, Accelerated GNHSS iterative method for weighted Toeplitz regularized least-squares problems from image restoration, Comput. Appl. Math., 2018, 37(5), 6152-6175. doi: 10.1007/s40314-018-0681-8 CrossRef Google Scholar
[12]	J. Cui, G. Peng, Q. Lu and Z. Huang, Modified special HSS method for discrete ill-posed problems and image restoration, Int. J. Comput. Math., 2020, 97(4), 739-758. doi: 10.1080/00207160.2019.1585827 CrossRef Google Scholar
[13]	V. Edalatpour, D. Hezari and D. K. Salkuyeh, Accelerated generalized SOR method for a class of complex systems of linear equations, Math. Commun., 2015, 20(1), 37-52. Google Scholar
[14]	D. Hezari, V. Edalatpour and D. K. Salkuyeh, Preconditioned GSOR iterative method for a class of complex symmetric system of linear equations, Numer. Linear Algebra Appl., 2015, 22(4), 761-776. doi: 10.1002/nla.1987 CrossRef Google Scholar
[15]	Y. Huang, A practical formula for computing optimal parameters in the HSS iteration methods, J. Comput. Appl. Math., 2014, 255, 142-149. doi: 10.1016/j.cam.2013.01.023 CrossRef Google Scholar
[16]	Z. Huang, L. Wang, Z. Xu and J. Cui, Preconditioned accelerated generalized successive overrelaxation method for solving complex symmetric linear systems, Comput. Math. Appl., 2019, 77(7), 1902-1916. doi: 10.1016/j.camwa.2018.11.024 CrossRef Google Scholar
[17]	A. K. Jain, Fundamentals of Digital Image Processing, Englewood Cliffs, NJ: Prentice Hall, 1989. Google Scholar
[18]	X. Jin, Preconditioning Techniques for Toeplitz Systems, Higher Education Press, Beijing, 2010. Google Scholar
[19]	T. Kailath and A. H. Sayed, Displacement structure: theory and applications, SIAM Rev., 1995, 37(3), 297-386. doi: 10.1137/1037082 CrossRef Google Scholar
[20]	A. K. Katsaggelos, Digital Image Restoration, Springer Publishing Company, Incorporated, 2012. Google Scholar
[21]	Y. Ke and C. Ma, A new relaxed splitting preconditioner for the generalized saddle point problems from the incompressible Navier-Stokes equations, Comput. Appl. Math., 2018, 37(1), 515-524. doi: 10.1007/s40314-016-0357-1 CrossRef Google Scholar
[22]	L. Liao and G. Zhang, New variant of the HSS iteration method for weighted Toeplitz regularized least-squares problems from image restoration, Comput. Math. Appl., 2017, 73(11), 2482-2499. doi: 10.1016/j.camwa.2017.03.027 CrossRef Google Scholar
[23]	M. K. Ng, Iterative Methods for Toeplitz Systems, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2004. Google Scholar
[24]	M. K. Ng, Iterative Methods for Toeplitz Systems, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2004. Google Scholar
[25]	M. K. Ng and J. Pan, Weighted Toeplitz regularized least squares computation for image restoration, SIAM J. Sci. Comput., 2014, 36(1), B94-B121. doi: 10.1137/120888776 CrossRef Google Scholar
[26]	J. Pan, M. K. Ng and Z. Bai, New preconditioners for saddle point problems, Appl. Math. Comput., 2006, 172(2), 762-771. Google Scholar
[27]	Y. Saad, Iterative Methods for Sparse Linear Systems, volume 82, SIAM, Philadelphia, PA, 2003. Google Scholar
[28]	G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math., 1986, 74(2), 171-176. doi: 10.1002/sapm1986742171 CrossRef Google Scholar
[29]	M. K. Zak and F. Toutounian, A shifted nested splitting iterative method with applications to ill-posed problems and image restoration, Comput. Math. Appl., 2016, 71(1), 213-223. doi: 10.1016/j.camwa.2015.11.005 CrossRef Google Scholar
[30]	J. Zhang and H. Dai, A new block preconditioner for complex symmetric indefinite linear systems, Numer. Algorithms, 2017, 74(3), 889-903. doi: 10.1007/s11075-016-0175-y CrossRef Google Scholar