Rosetak Document 4: Rank Degeneracies and Least Square Problems

In this paper we shall be concerned with the following problem. Let A be an m x n matrix with m being greater than or equal to n, and suppose that A is near (in a sense to be made precise later) a matrix B whose rank is less than n. Can one find a set of linearly independent columns of A that span a good approximation to the column space of B? The solution of this problem is important in a number of applications. In this paper we shall be chiefly interested in the case where the columns of A represent factors or carriers in a linear model which is to be fit to a vector of observations b. In some such applications, where the elements of A can be specified exactly (e.g. the analysis of variance), the presence of rank degeneracy in A can be dealt with by explicit mathematical formulas and causes no essential difficulties. In other applications, however, the presence of degeneracy is not at all obvious, and the failure to detect it can result in meaningless results or even the catastrophic failure of the numerical algorithms being used to solve the problem. The organization of this paper is the following. In the next section we shall give a precise definition of approximate degeneracy in terms of the singular value decomposition of A. In Section 3 we shall show that under certain conditions there is associated with A a subspace that is insensitive to how it is approximated by various choices of the columns of A, and in Section 4 we shall apply this result to the solution of the least squares problem. Sections 5, 6, and 7 will be concerned with algorithms for selecting a basis for the stable subspace from among the columns of A.