Estimation of optimal backward perturbation bounds for the linear least squares problem (Q1378467)

Let \(\mathbb{R}^{m \times n}\) denote the set of real \(n\times n\) matrices, \(A\in \mathbb{R}^{m \times n}\), \(b\in \mathbb{R}^m\) and let \(\widetilde x\) be a purported solution to the minimization problem \(\min\| b-Ax \|_2\). The problem is to find a perturbation \(E\) of \(A\) such that \(\widetilde x\) minimizes \(\| b-(A+E) x\|_2\). The authors suggest a method for obtaining approximate estimates of the optimal backward perturbation bound, where the number of operations is moderate \((O(mn))\) in comparison with the work required to solve the least squares problem using standard techniques and therefore it is very suitable for large problems. The methods is based on the computation of a strict lower bound for the spectral norm and a strict upper bound for the Frobenius norm. Some results of computational experiments showing the efficiency of the proposed method are given.