Efficient algorithms for solution of regularized total least squares

Error-contaminated systems Ax ≈ b, for which A is ill-conditioned, are considered. Such systems may be solved using Tikhonov-like regularized total least squares (RTLS) methods. Golub, Hansen, and O'Leary [SIAM J. Matrix Anal. Appl., 21 (1999), pp. 185-194] presented a parameter-dependent direct algorithm for the solution of the augmented Lagrange formulation for the RTLS problem, and Sima, Van Huffel, and Golub [Regularized Total Least Squares Based on Quadratic Eigenvalue Problem Solvers, Tech. Report SCCM-03-03, SCCM, Stanford University, Stanford, CA, 2003] have introduced a technique for solution based on a quadratic eigenvalue problem, RTLSQEP. Guo and Renaut [A regularized total least squares algorithm, in Total Least Squares and Errors-in-Variables Modeling: Analysis, Algorithms and Applications, S. Van Huffel and P. Lemmerling, eds., Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002, pp. 57-66] derived an eigenproblem for the RTLS which can be solved using the iterative inverse power method. Here we present an alternative derivation of the eigenproblem for constrained TLS through the augmented Lagrangian for the constrained normalized residual. This extends the analysis of the eigenproblem and leads to derivation of more efficient algorithms compared to the original formulation. Additional algorithms based on bisection search and a standard L-curve approach are presented. These algorithms vary with respect to the parameters that need to be prescribed. Numerical and convergence results supporting the different versions and contrasting with RTLSQEP are presented.