##
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.