gibson:teaching:fall-2016:math753:qr-leastsquares

The QR decomposition is useful for solving the *linear least-squares problem*. Briefly, suppose you have an system with an oblong matrix , i.e. A is an matrix with .

Each of the rows of corresponds to a linear equation in the unknown variables that are the components of . But with , that means we have more equations than unknowns. In general, a system with more equations than unknowns does not have a solution!

So, instead of looking for an such that , we look for an such that is small. Since is a vector, we measure its size with a norm. That means we are looking for the that minimizes .

Let . Thinking geometrically, will be smallest when is orthogonal to the span of the columns of . Recall that for the QR factorization , the columns of are an orthonormal basis for the span of the columns of . So is orthogonal to the span of the columns of when

Since is an matrix whose columns are orthonormal, is the identity matrix. Since is , we now have as the same number of equations as unknowns. The last line, , is a square upper-triangular system which we can solve by backsubstitution.

That's a quick recap of least-squares via QR. For more detail, see these lecture notes from the University of Utah.

gibson/teaching/fall-2016/math753/qr-leastsquares.txt · Last modified: 2016/10/12 09:18 by gibson