Methods for large scale total least squares problems

The solution of the total least squares (TLS) problems, min(E,f) parallel>(*) over bar * (E, f)parallel to (F) subject to (A + E)x = b + f, can in the generic case be obtained from the right singular vector corresponding to the smallest singular value sigma (n+1) of (A, b). When A is large and sparse (or structured) a method based on Rayleigh quotient iteration (RQI) has been suggested by Bjorck In this method the problem is reduced to the solution of a sequence of symmetric, positive definite linear systems of the form (A(T) A-I-2(<(<sigma>)over bar>)) z = g, where <(<sigma>)over bar> is an approximation to sigma (n+1). These linear systems are then solved by a preconditioned conjugate gradient method (PCGTLS). For TLS problems where A is large and sparse a (possibly incomplete) Cholesky factor of A(T) A can usually be computed, and this provides a very efficient preconditioner. The resulting method can be used to solve a much wider range of problems than it is possible to solve by using Lanczos-type algorithms directly for the singular value problem. In this paper the RQI-PCGTLS method is further developed, and the choice of initial approximation and termination criteria are discussed. Numerical results con rm that the given algorithm achieves rapid convergence and good accuracy.