Complete Orthogonal Decomposition for Weighted Least Squares (Q4337387)

In this paper the authors propose a complete orthogonal decomposition (COD) algorithm for solving weighted least squares problems. \textit{G. W. Stewart} [Linear Algebra Appl. 112, 189-193 (1989; Zbl 0658.15003)] and \textit{M. J. Todd} [Oper. Res. 38, No. 6, 1006-1018 (1990; Zbl 0724.90037)] independently established a norm bound for the weighted least squares problem that is independent of the weight matrix. Using this norm bound \textit{S. A. Vavasis} [SIAM J. Matrix Anal. Appl. 15, No. 4, 1108-1131 (1994; Zbl 0806.65020)] proposed a definition of a ``stable'' solution of the weighted least squares problem: The solution computed by a stable algorithm must satisfy an accuracy bound that is not affected by ill-conditioning in the weight matrix. A forward analysis shows that COD algorithm is stable in this sense, but it is simpler and more efficient than the algorithm proposed by Vavasis [loc. cit.]. The forward error bound is compared to the backward error analysis of other previous workers on weighted least squares. The paper concludes with a discussion of open questions.