Optimal backward perturbation bounds for the linear least squares problem

This is the authors' abstract. We don't add key points for this paper.

Let A be an m × n matrix, b be an m ‐vector, and x̃ be a purported solution to the problem of minimizing ‖ b — Ax ‖ 2 . We consider the following open problem: find the smallest perturbation E of A such that the vector x̃ exactly minimizes ‖ b — ( A + E ) x ‖ 2 . This problem is completely solved when E is measured in the Frobenius norm. When using the spectral norm of E , upper and lower bounds are given, and the optimum is found under certain conditions.