Fast Algorithms for Structured Least Squares and Total Least Squares Problems.
We consider the problem of solving least squares problems involving a matrix M of small displacement rank with respect to two matrices Z 1 and Z 2. We develop formulas for the generators of the matrix M (H) M in terms of the generators of M and show that the Cholesky factorization of the matrix M (H) M can be computed quickly if Z 1 is close to unitary and Z 2 is triangular and nilpotent. These conditions are satisfied for several classes of matrices, including Toeplitz, block Toeplitz, Hankel, and block Hankel, and for matrices whose blocks have such structure. Fast Cholesky factorization enables fast solution of least squares problems, total least squares problems, and regularized total least squares problems involving these classes of matrices.
Applied Mathematics Program, University of Maryland, College Park, MD 20742.
Anoop
A
Kalsi
Dept. of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742.
Dianne P
DP
O'Leary
Tikhonov regularization; block Toeplitz matrix; displacement rank; errors in variables method; image deblurring; structured total least squares; total least squares