OPTIMAL BACKWARD PERTURBATION BOUNDS FOR THE LINEAR LEAST-SQUARES PROBLEM

Let A be an m x n matrix, b be an m-vector, and ($) over tilde x: be a purported solution to the problem of minimizing \\b - Ax\\(2). We con sider the following open problem: find the smallest perturbation E of A such that the vector ($) over tilde x exactly minimizes \\b - (A + E )x\\(2). This problem is completely solved when E is measured in the F robenius norm. When using the spectral norm of E, upper and lower boun ds are given, and the optimum is found under certain conditions.