CHARACTERIZING MATRICES THAT ARE CONSISTENT WITH GIVEN SOLUTIONS

For given vectors b is an element of C-m and y is an element of C-n we describe a unitary transformation approach to deriving the set F of all matrices F is an element of C-mxn such that y is an exact solution to the compatible system Fy = b. This is used for deriving minimal backward errors E and f such that (A+E)y = b+f when possibly noisy data A is an element of C-m x n and b is an element of C-m are given, and the aim is to decide if y is a satisfactory approximate solution to Ax = b. The approach might be different, but the above results are not new. However, we also prove the apparently new result that two well-known approaches to making this decision are theoretically equivalent and discuss how such knowledge can be used in designing effective stopping criteria for iterative solution techniques. All these ideas generalize to the following formulations. We extend our constructive approach to derive a superset FSTLS+ of the set F-STLS of all matrices F. C-m x n such that y is a scaled total least squares solution to Fy approximate to b. This is a new general result that specializes in two important ways. The ordinary least squares problem is an extreme case of the scaled total least squares problem, and we use our result to obtain the set F-LS of all matrices F. Cm x n such that y is an exact least squares solution to Fy approximate to b. This complements the original less-constructive derivation of Walden, Karlson, and Sun [Numer. Linear Algebra Appl., 2 (1995), pp. 271-286]. We do the equivalent for the data least squares problem-the other extreme case of the scaled total least squares problem. Not only can the results be used as indicated above for the compatible case, but the constructive technique we use could also be applicable to other backward problems-such as those for underdetermined systems, the singular value decomposition, and the eigenproblem.