5
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.