Linear Least Squares Minimization

[swartzism]

I'm going through some methods to solve the LLS method of minimization and have come upon 3 general methods to solve the problem. The 3 methods I am looking at are normal equations, QR factorization, and SVD. I've come upon a fact that I can't find an explanation for: If a matrix is rank-deficient, meaning that there are at least two linearly dependent rows (or columns), then there are an infinite number of solutions to the least squares problem. If this is the case, then neither normal equations nor QR factorization can be used. An alternative method called Single Value Decomposition (SVD) can be used in the rank-deficient case. (Warmuth, 2004)

Can anyone explain why this is, or point me to an article that offers an explanation?

Thanks in advance.

[Stephen Tashi]

Suppose you want the least squares fit a of a quadratic with 3 unknown coefficients to a single data point. There are many quadratics that will give you a least squares error of zero. That's an extreme example of how the matrix for the system of linear equations can have insufficient rank. I don't know what the SVD approach would do in this case.

( By the way, the SVD is one of the most useful decompositions of matrices. The way I look at the SVD is that it says all tabular data can be written as a linear combinations of simple data tables of products. Each of the simple data tables has some row headings a_i and some column headings b_j and the i,j entry in the table is a_i b_j . )

[swartzism]

Thanks for the reply (after 47 people viewed and no responses, I was getting worried...) I understand how a matrix can be rank-deficient (1 or more linearly dependent, or "parallel", columns/rows), but why can't normal equations or QR factorization handle it? What makes them only able to handle fully-ranked matrices?

Thanks again.

[Stephen Tashi]

If A is the matrix of equations for the coefficients of the function, using the normal equations requires that A^T A be invertible. In the case of fitting a quadratic to a single point x = 1, y = 2 , A^T A is a 3 by 3 matrix all of whose entries are 1's, so it isn't invertible. There's probably a similar requirement for invertibility in the QR method.

[hotvette]

QR and SVD are methods to solve the least squares normal equations without having to actually compute the normal equations (if that makes any sense). Re why SVD can be used for rank deficient problems, I can't explain very much but it has to do with calculation of the singular values during the SVD decomposition process. The main diagonal of 'D' contains the singular values. If any are zero (or small compared to the others) the problem is rank deficient and the least norm solution can be calculated.