On Iterative Solution of the Extended Normal Equations

• Published in: SIAM journal on matrix analysis and applications 2020-01, Vol.41 (4), p.1571-1589
• Main Authors: Calandra, Henri, Gratton, Serge, Riccietti, Elisa, Vasseur, Xavier
• Format: Article
• Language: English
• Subjects: General Mathematics; Mathematics
• ISSN: 0895-4798; 1095-7162
• DOI: 10.1137/19M1288644

Given a full-rank matrix $A \in \mathbb{R}^{m\times n}$ ($m\geq n$), we consider a special class of linear systems $A^T\! Ax=A^T\! b+c$ with $x, c \in \mathbb{R}^{n}$ and $b \in \mathbb{R}^{m}$, which we refer to as the extended normal equations. The occurrence of $c$ gives rise to a problem with a different conditioning from the standard normal equations and prevents direct application of standard methods for least squares. Hence, we seek more insights on theoretical and practical aspects of the solution of such problems. We propose an explicit formula for the structured condition number, which allows us to compute a more accurate estimate of the forward error than the standard one used for generic linear systems, which does not take into account the structure of the perturbations. The relevance of our estimate is shown on a set of synthetic test problems. Then, we propose a new iterative solution method that, as in the case of normal equations, takes advantage of the structure of the system to avoid unstable computations such as forming $A^T\! A$ explicitly. Numerical experiments highlight the increased robustness and accuracy of the proposed method compared to standard iterative methods. It is also found that the new method can compare to standard direct methods in terms of solution accuracy.