A Gauss-Newton iteration for Total Least Squares problems

The Total Least Squares solution of an overdetermined, approximate linear equation Ax approx b minimizes a nonlinear function which characterizes the backward error. We devise a variant of the Gauss–Newton iteration with guaranteed convergence to that solution, under classical well-posedness hypotheses. At each iteration, the proposed method requires the solution of an ordinary least squares problem where the matrix A is modified by a rank-one term. In exact arithmetics, the method is equivalent to an inverse power iteration to compute the smallest singular value of the complete matrix (A | b). Geometric and computational properties of the method are analyzed in detail and illustrated by numerical examples.