Methods for large scale total least squares problems. (English) Zbl 0974.65037

Björck, Åke; Heggernes, P.; Matstoms, P.

SIAM J. Matrix Anal. Appl. 22, No. 2, 413-429 (2000).

Authors’ abstract: The solution of the total least squares (TLS) problems, \[ \min_{E,f}\|(E, f)\|_F\quad\text{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 bases on Rayleigh quotient iteration (RQI) has been suggested by A. Björck [Proc. 2nd Int. Workshop on Total Least Squares, Leuven 1996, SIAM 149-160 (1997; Zbl 0879.65105)]. In this method the problem is reduced to the solution of a sequence of symmetric, positive definite linear systems of the form \((A^TA- \overline\partial^2 I)z= g\), where \(\overline\sigma\) 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^TA\) 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 methods are further developed, and the choice of initial approximation and termination criteria are discussed. Numerical results confirm that the given algorithm achieves rapid convergence and good accuracy.

Reviewer: A.Meister (Hamburg)

MSC:

65F20

Numerical solutions to overdetermined systems, pseudoinverses

Keywords:

total least squares; Rayleigh quotient iteration; conjugate gradient method; singular values; preconditioning; large sparse matrix; numerical results; Lanczos-type algorithms; algorithm; convergence

Software:

mctoolbox