An Interval Analysis Approach to Rank Determination in Linear Least Squares Problems

The linear least squares problem A x b has a unique solution only if the matrix A has full column rank. Numerical rank determination is difficult, especially in the presence of uncertainties in the elements of A. This paper proposes an interval analysis approach. We define a set of matrices AI that contains all possible perturbations of A due to uncertainties and say that AI is rank deficient if any member of AI is rank deficient. A modification to the $QR$ decomposition method of solution of the least squares problem allows a determination of the rank of AI and a partial interval analysis of the solution vector x. This procedure requires the computation of R- 1. Another modification is proposed which determines the rank of AI without computing R- 1. The additional computational effort is O(n² ), where n is the column dimension of A.