The Reduced-QR Computation
For an overdetermined system, the equations \(\mathbf{A}\mathbf{x}=\mathbf{b}\) may have no exact solution. A least-squares solution is a vector \(\mathbf{x}\) that minimizes the residual norm \(\|\mathbf{b}-\mathbf{A}\mathbf{x}\|\). When \(\mathbf{A}\) has full column rank, reduced QR gives a direct computational route: factor \(\mathbf{A}\), take an inner product with the columns of \(\mathbf{Q}\), and solve a triangular system. The steps avoid forming the normal-equation matrix \(\mathbf{A}^{\top}\mathbf{A}\).
Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\) with \(m\ge n\), and suppose its \(n\) columns are linearly independent. A reduced QR factorization is \(\mathbf{A}=\mathbf{Q}\mathbf{R}\), where \(\mathbf{Q}\in\mathbb{R}^{m\times n}\) has orthonormal columns and \(\mathbf{R}\in\mathbb{R}^{n\times n}\) is upper triangular with nonzero diagonal entries. Orthonormal columns mean \(\mathbf{Q}^{\top}\mathbf{Q}=\mathbf{I}_n\). These properties follow from constructing QR by Gram–Schmidt; full column rank ensures that none of the vectors being normalized in that construction is zero.
The dimensions matter. The product \(\mathbf{Q}^{\top}\mathbf{b}\) is in \(\mathbb{R}^n\), so it is the right-hand side for the \(n\times n\) triangular system, not usually the answer itself. The matrix \(\mathbf{Q}\) is \(m\times n\), not necessarily square. In particular, the operation is to multiply by \(\mathbf{Q}^{\top}\), not by \(\mathbf{Q}\).
Why the Triangular Solve Gives the Least-Squares Answer
Proof. Set \(\mathbf{y}=\mathbf{Q}^{\top}\mathbf{b}\). For any candidate \(\mathbf{x}\in\mathbb{R}^n\), use \(\mathbf{A}=\mathbf{Q}\mathbf{R}\) to write the residual as
The two terms on the right are orthogonal. Indeed, multiplying the first by \(\mathbf{Q}^{\top}\) gives \(\mathbf{Q}^{\top}\mathbf{b}-\mathbf{Q}^{\top}\mathbf{Q}\mathbf{y}=\mathbf{y}-\mathbf{y}=\mathbf{0}\). Thus its inner product with every column combination \(\mathbf{Q}\mathbf{z}\) is zero, including the second term. Expanding the squared norm of a sum of orthogonal vectors gives
For the last equality, if \(\mathbf{z}=\mathbf{y}-\mathbf{R}\mathbf{x}\), then \(\|\mathbf{Q}\mathbf{z}\|^2=(\mathbf{Q}\mathbf{z})^{\top}(\mathbf{Q}\mathbf{z})=\mathbf{z}^{\top}\mathbf{Q}^{\top}\mathbf{Q}\mathbf{z}=\mathbf{z}^{\top}\mathbf{z}\). The first squared norm in the displayed sum does not depend on \(\mathbf{x}\). The second is nonnegative and equals zero exactly when \(\mathbf{R}\mathbf{x}=\mathbf{y}\). Since \(\mathbf{R}\) is upper triangular with nonzero diagonal, back-substitution gives exactly one solution. That solution uniquely minimizes the residual norm. \(\square\)
For a right-hand side \(\mathbf{y}=(y_1,\dots,y_n)^{\top}\), back-substitution uses the rows of \(\mathbf{R}\) in reverse order. Since entries below the diagonal are zero, row \(i\) has the equation \(r_{ii}x_i+\sum_{j=i+1}^n r_{ij}x_j=y_i\). Once \(x_{i+1},\dots,x_n\) are known, this determines \(x_i\).
Why the rule works. The last row is \(r_{nn}x_n=y_n\), which has the unique solution \(x_n=y_n/r_{nn}\) because \(r_{nn}\ne0\). After \(x_{i+1},\dots,x_n\) have been determined, row \(i\) has only one still-unknown variable, \(x_i\), and its coefficient \(r_{ii}\) is nonzero. Solving that row gives the stated formula and satisfies it exactly. Continuing to row 1 therefore satisfies every row. The same descending argument shows uniqueness: any solution must have the same \(x_n\), then the same \(x_{n-1}\), and so on through \(x_1\). \(\square\)
A Two-Column Example From Gram–Schmidt
Worked Example: A Nonzero Residual in Three Coordinates
Find the least-squares solution for \(\mathbf{A}=\begin{bmatrix}1&1\\1&0\\0&1\end{bmatrix}\) and \(\mathbf{b}=(1,2,0)^{\top}\), using reduced QR.
Write the columns as \(\mathbf{a}_1=(1,1,0)^{\top}\) and \(\mathbf{a}_2=(1,0,1)^{\top}\). Gram–Schmidt gives \(\|\mathbf{a}_1\|=\sqrt{2}\), so \(\mathbf{q}_1=(1,1,0)^{\top}/\sqrt{2}\). The projection coefficient for the second column is \(\mathbf{q}_1^{\top}\mathbf{a}_2=1/\sqrt{2}\). Therefore
Consequently the reduced factors and the transformed right-hand side are
For example, the second entry of \(\mathbf{Q}^{\top}\mathbf{b}\) is \((1-2+0)/\sqrt{6}=-1/\sqrt{6}\). Back-substitute into \(\mathbf{R}\mathbf{x}=\mathbf{Q}^{\top}\mathbf{b}\). The bottom row gives \((\sqrt{6}/2)x_2=-1/\sqrt{6}\), hence \(x_2=-1/3\). The first row gives \(\sqrt{2}x_1+(1/\sqrt{2})(-1/3)=3/\sqrt{2}\). Multiplication by \(\sqrt{2}\) gives \(2x_1-1/3=3\), so \(x_1=5/3\).
Residual check: Multiplication gives \(\mathbf{A}\mathbf{x}=(4/3,5/3,-1/3)^{\top}\), and therefore \(\mathbf{r}=\mathbf{b}-\mathbf{A}\mathbf{x}=(-1/3,1/3,1/3)^{\top}\). Its inner product with each column is zero: \((1,1,0)\cdot\mathbf{r}=0\) and \((1,0,1)\cdot\mathbf{r}=0\). Also \(\|\mathbf{r}\|^2=1/9+1/9+1/9=1/3\). The residual is nonzero, so this is not an exact solution of \(\mathbf{A}\mathbf{x}=\mathbf{b}\); it is the least-squares fit.
Back-Substitution With Three Unknowns
Worked Example: A Three-Column Reduced QR Solve
Consider the orthonormal columns of \(\mathbf{Q}\) and the upper-triangular \(\mathbf{R}\) below. Compute the least-squares solution for the resulting \(\mathbf{A}=\mathbf{Q}\mathbf{R}\) and \(\mathbf{b}\).
The columns of \(\mathbf{Q}\) have squared length 1, and distinct columns have inner product 0, so \(\mathbf{Q}^{\top}\mathbf{Q}=\mathbf{I}_3\). Multiplying the factors gives
Taking the three column inner products with \(\mathbf{b}\) gives \(\mathbf{y}=\mathbf{Q}^{\top}\mathbf{b}=(2\sqrt{2},\sqrt{2},3)^{\top}\). Solve from the bottom row upward. The third row gives \(x_3=3\). The second row gives \(x_2+x_3=\sqrt{2}\), so \(x_2=\sqrt{2}-3\). The first row gives \(x_1+x_2=2\sqrt{2}\), so \(x_1=2\sqrt{2}-(\sqrt{2}-3)=\sqrt{2}+3\).
Residual check: From \(\mathbf{A}\mathbf{x}=\mathbf{Q}\mathbf{R}\mathbf{x}=\mathbf{Q}\mathbf{y}\), we obtain \(\mathbf{A}\mathbf{x}=(3,1,3,0)^{\top}\). Thus \(\mathbf{r}=\mathbf{b}-\mathbf{A}\mathbf{x}=(0,0,0,4)^{\top}\). Each column of \(\mathbf{A}\) has fourth entry zero, so its inner product with \(\mathbf{r}\) is zero. The nonzero residual is orthogonal to the column space, as expected for the least-squares fit.
An Example With a Fractional Answer
Worked Example: A Best Fit With Two Independent Columns
Use reduced QR to solve the least-squares problem with \(\mathbf{A}=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}\) and \(\mathbf{b}=(1,2,2)^{\top}\).
Let \(\mathbf{a}_1=(1,0,1)^{\top}\) and \(\mathbf{a}_2=(0,1,1)^{\top}\). The first Gram–Schmidt vector is \(\mathbf{q}_1=(1,0,1)^{\top}/\sqrt{2}\). Since \(\mathbf{q}_1^{\top}\mathbf{a}_2=1/\sqrt{2}\), subtracting the projection gives \(\mathbf{u}_2=(-1/2,1,1/2)^{\top}\), whose norm is \(\sqrt{6}/2\). Hence \(\mathbf{q}_2=(-1,2,1)^{\top}/\sqrt{6}\), and
The transformed right-hand side is \(\mathbf{Q}^{\top}\mathbf{b}=(3/\sqrt{2},5/\sqrt{6})^{\top}\): the second entry is \((-1+4+2)/\sqrt{6}=5/\sqrt{6}\). The second row of the triangular system yields \(x_2=(5/\sqrt{6})/(\sqrt{6}/2)=5/3\). The first row gives \(\sqrt{2}x_1+(1/\sqrt{2})(5/3)=3/\sqrt{2}\). Multiplying by \(\sqrt{2}\) gives \(2x_1+5/3=3\), so \(x_1=2/3\).
Residual check: Multiplying by \(\mathbf{A}\) gives \(\mathbf{A}\mathbf{x}=(2/3,5/3,7/3)^{\top}\), so \(\mathbf{r}=(1/3,1/3,-1/3)^{\top}\). The column inner products are \(1/3-1/3=0\) and \(1/3-1/3=0\). Its squared norm is \(1/9+1/9+1/9=1/3\), confirming the residual calculation.
Common Mistake: Stopping After Computing \(Q^{\top}b\)
In the first worked example, \(\mathbf{Q}^{\top}\mathbf{b}=(3/\sqrt{2},-1/\sqrt{6})^{\top}\). A tempting but incorrect step is to report that vector as the least-squares solution. The reduced QR computation requires solving \(\mathbf{R}\mathbf{x}=\mathbf{Q}^{\top}\mathbf{b}\), and \(\mathbf{R}\) is not the identity matrix. For instance, substituting the mistaken value \(x_2=-1/\sqrt{6}\) into the second row would give \((\sqrt{6}/2)x_2=-1/2\), which is not the required value \(-1/\sqrt{6}\). The correct back-substitution gives \(x_2=-1/3\), followed by \(x_1=5/3\).
A useful final check is to form \(\mathbf{r}=\mathbf{b}-\mathbf{A}\mathbf{x}\) and calculate \(\mathbf{A}^{\top}\mathbf{r}\). For a computed least-squares solution this vector is zero: each entry is the inner product of a column of \(\mathbf{A}\) with the residual. This check can reveal an arithmetic error in the factorization, the transformed right-hand side, or the triangular solve. It does not replace following the required full-column-rank setup, but it confirms that the resulting residual is orthogonal to every column.
Check Your Understanding
In each problem, show the triangular solve and verify the result using the residual.
- For the first worked example, recompute the two entries of \(\mathbf{Q}^{\top}\mathbf{b}\) directly as inner products.
- If \(\mathbf{R}=\begin{bmatrix}2&1\\0&3\end{bmatrix}\) and \(\mathbf{y}=(5,6)^{\top}\), find \(\mathbf{x}\) by back-substitution.
- Explain why a nonzero residual can still belong to a least-squares solution.
- For the three-column example, verify directly that each column of \(\mathbf{A}\) has zero inner product with \((0,0,0,4)^{\top}\).
- State what fails in the prescribed triangular solve if a diagonal entry of \(\mathbf{R}\) is zero.
