Structured Matrix Computations With Applications In Digital Image Restoration

Structured linear systems frequently arise in a variety of applications in differentfields of mathematics, scientific computing and engineering, such as partial differentialequations, signal and image processing, queueing networks, integral equations, time-series analysis and control theory, etc. The design of fast and numerically reliable al-gorithms for large-scale problems with structure has become an increasingly importantactivity, especially in recent years, driven by the ever-increasing complexity of practicalapplications. The major challenge in this area is to develop algorithms that blend speedand numerical accuracy. These two requirements often have been regarded as competitive,so that the design of fast and numerically reliable algorithms for large-scale structured lin-ear equations has remained a significant open issue in many instances. This dissertationfirst considers the problems of developing effective algorithms for the solutions of large-scale structured linear systems.A new algorithm for solving linear systems of the Pascal matrices is proposed. Themethod is based on the explicit Jordan factorization of the Pascal matrices. The algorithmrequires no multiplications and O(n2) additions for n×n Pascal linear systems. Thelinear systems of the generalized Pascal matrices are also considered.The results about the centrosymmetric and skew-centrosymmetric splitting(CSS) it-erative method for solving the positive definite Toepltiz linear systems are presented. Theanalysis about the convergence and the choice of the parameter of the presented methodis given. Some simple numerical results show the effectiveness of the CSS iteration.A modified T. Chan’s preconditioner for solving Toeplitz linear systems with the pre-conditioned conjugate gradient (PCG) method is developed. Especially, some importantresults when the matrices are Hermitian positive definite Toeplitz matrices are derived.The computational costs and convergence of the preconditioned conjugate gradient(PCG)method are discussed. Numerical examples are presented to illustrate the effectiveness ofthe presented preconditioner.Restoration of an image is the process of removing or minimizing degradations in theobserved image. Mathematically, it can be modeled as a discrete ill-posed problem Kf +η= g, where K is a matrix of large dimension representing the blurring phenomena, g is a vector representing the observed image, andηis a vector representing noise. Restorationmethods attempt to recover an approximation to the original image f, given g, K, and, insome cases, statistical information about the noise. Often K is severely ill-conditioned,and g is corrupted with noise. Thus, standard techniques to solve Kf = g are likely toproduce solutions that are highly corrupted with noise. In general, a regularization methodcan address these problems efficiently. One may employ it to compute the approximatesolutions that are less sensitive to noise than the naive solution. The dissertation alsoattempts to devise some efficient and reliable regularization methods for digital imagerestoration problems.The use of the whole-sample symmetric boundary conditions (BCs) in image restora-tion is considered. The blurring matrices constructed from the point spread func-tions (PSFs) for the BCs have block Toeplitz-plus-PseudoHankel with Toeplitz-plus-PseudoHankel blocks structures. Regardless of symmetric properties of the PSFs, a tech-nique of Kronecker product approximations is successfully applied to restore images withthe whole-sample symmetric BCs. It is noted that when the size of the true PSF is small,the computational complexity of the algorithm obtained for the Kronecker product ap-proximation of the resulting matrix is very small, since all calculations in the algorithmare implemented only at the upper left corner submatrices of the big matrices.The global Krylov methods for ill-posed image restoration problem are proposed.It is shown that the global methods can act as good regularization methods for imagerestoration problems when equipped with a suitable stopping rule based on the discrep-ancy principle. To accelerate the convergence of the global methods, project the computedapproximate solution onto the set of matrices with nonnegative entries before restarting.Some numerical examples from image restoration are given to illustrate the efficiency ofthe global methods.A special Hermitian and skew-Hermitian splitting (SHSS) iterative method is estab-lished for solving the linear systems from image restoration. The approach is based on anaugmented system formulation. The convergence and operation cost of the SHSS iterativemethod for image restoration problems are discussed. The optimal parameter minimizingthe spectral radius of the iteration matrix is derived. Finally, the successive overrelaxation(SOR) acceleration scheme for the SHSS iterative method is discussed.