Complete Orthogonal Decomposition for Weighted Least Squares

Patricia D. Hough and Stephen A. Vavasis

Consider a full-rank weighted least-squares problem in which the weight matrix is highly ill-conditioned. Because of the ill-conditioning, standard methods for solving least-squares problems, QR factorization and the nullspace method for example, break down. G.~W.~Stewart established a norm bound for such a system of equations, indicating that it may be possible to find an algorithm that gives an accurate solution. S.~A.~Vavasis proposed a new definition of stability that is based on this result. He also proposed the NSH algorithm for solving this least-squares problem and showed that it satisfies the new definition of stability. This paper describes a complete orthogonal decomposition algorithm to solve this problem and shows that it is also stable. This new algorithm is simpler and more efficient than the NSH method.

Preprint, Cornell University, March, 1995.