An Interval Analysis Approach to Rank Determination in Linear Least Squares Problems
Thomas A. Manteuffel · SIAM Journal on Scientific and Statistical Computing · 1981
The linear least squares problem $A{\bf x} \cong {\bf 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 $A^I $ that contains all possible perturbations of A due to uncertainties and say that $A^I $ is rank deficient if any member of $A^I $ is rank deficient. A modification to the $QR$ decomposition method of solution of the least squares problem allows a determination of the rank of $A^I $ and a partial interval analysis of the solution vector ${\bf x}$. This procedure requires the computation of $R^{ - 1} $. Another modification is proposed which determines the rank of $A^I $ without computing $R^{ - 1} $. The additional computational effort is $O(n^2 )$, where n is the column dimension of A.