# How can I tell which matrix decomposition to use for OLS?

I want to find the least squares solution to $\boldsymbol{Ax}=\boldsymbol{b}$ where $\boldsymbol{A}$ is a highly sparse square matrix.
I found two methods that look like they might lead me to a solution: QR factorization, and singular value decomposition. Unfortunately, I haven't taken linear algebra yet, so I can't really understand most of what those pages are saying. I can calculate both in Matlab though, and it looks like the SVD gave me a smaller squared error. Why did that happen? How can I know which one I should be using in the future?

-

It's all dependent on the 2-norm condition number of your matrix (the ratio of the largest singular value to the smallest); as a nice rule of thumb, if the base-10 logarithm of the reciprocal of the condition number is much less than the number of digits your computer uses to store numbers, QR (and maybe even the normal equations) might be sufficient. Otherwise, SVD is a "safer bet": it always works, but is much slower than the other methods for solving least squares problems.

Good references would be the classic "Solving Least Squares Problems" by Lawson and Hanson, and the newer "Numerical Methods for Least Squares Problems" by Björck.

To add to the answer I gave previously, one way you can proceed for a matrix A whose conditioning you don't know would be as follows:

1. Compute the QR decomposition of A.
2. Estimate the condition number of R.
3. If R is well conditioned (condition number is "small enough"), stop; else
4. Compute the singular value decomposition of R=U∑VT
5. Multiply Q and U to get the SVD of A.

The advantage of proceeding in this manner is if your matrix is badly conditioned enough to necessitate the use of SVD, the algorithm for computing the SVD has to handle only a triangular matrix instead of the original matrix (which may have more rows than columns as is usual in least-squares applications).

-
@J. Mangaldan: I combined your two answers into this one, since it looks like you switched accounts. –  Larry Wang Aug 3 '10 at 6:15
Sounds good, I decided not to be anonymous anymore after spending an hour browsing here. :) –  Guess who it is. Aug 3 '10 at 8:27