Math 753/853 QR and the least-squares problem

The QR decomposition is useful for solving the linear least-squares problem. Briefly, suppose you have an $Ax=b$ system with an oblong matrix $A$ , i.e. A is an $m \times n$ matrix with $n<m$ .

Each of the $m$ rows of $A$ corresponds to a linear equation in the unknown $n$ variables that are the components of $x$ . But with $n<m$ , 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 $x$ such that $Ax=b$ , we look for an $x$ such that $Ax-b$ is small. Since $Ax-b$ is a vector, we measure its size with a norm. That means we are looking for the $x$ that minimizes $\|Ax-b\|$ .

Let $r = Ax-b$ . Thinking geometrically, $\|r\| = \|Ax-b\|$ will be smallest when $r$ is orthogonal to the span of the columns of $A$ . Recall that for the QR factorization $A=QR$ , the columns of $Q$ are an orthonormal basis for the span of the columns of $A$ . So $r$ is orthogonal to the span of the columns of $A$ when

$\begin{equation*} Q^T r = 0 \end{equation*}$

$\begin{equation*} Q^T (Ax-b) = 0 \end{equation*}$

$\begin{equation*} Q^T A x = Q^T b \end{equation*}$

$\begin{equation*} Q^T Q R x = Q^T b \end{equation*}$

$\begin{equation*} R x = Q^T b \end{equation*}$

Since $Q$ is an $m \times n$ matrix whose columns are orthonormal, $Q^T Q = I$ is the $n \times n$ identity matrix. Since $R$ is $n\times n$ , we now have as the same number of equations as unknowns. The last line, $Rx = Q^Tb$ , 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.

channelflow.org

User Tools

Site Tools

Math 753/853 QR and the least-squares problem

Page Tools