Symon Kimitei

Algorithms for Toeplitz Matrices with Applications to Image Deblurring: Solving Linear Equations or Linear Least Squares Problems with Low Displacement Rank Using the Schur Algorithm, Sped Via Via Fft Symon Kimitei

In this thesis, we present the O(n log^2 n) superfast linear least squares Schur algorithm(ssschur). The algorithm we describe illustrates a fast way of solving linear equations or linear least squares problems with low displacement rank. This algorithm is based on the O(n^2) Schur algorithm, sped up via FFT. The algorithm solves an ill-conditioned Toeplitz-like system using Tikhonov regularization. The regularized system solved is Toeplitz-like and is of displacement rank, 4. In this thesis, we also show the effect of the choice of the regularization parameter on the quality of the images reconstructed.