Why QR Solves Least-Squares Problems

Why Orthogonality Simplifies Least Squares

In a least-squares problem, the vector \(\mathbf{b}\) need not equal \(\mathbf{A}\mathbf{x}\) for any choice of \(\mathbf{x}\). Instead, we choose \(\mathbf{x}\) to make the residual \(\mathbf{b}-\mathbf{A}\mathbf{x}\) as short as possible. A QR factorization makes this minimization transparent: it separates the part of \(\mathbf{b}\) that can be represented by the columns of \(\mathbf{A}\) from the part that cannot.

Work over \(\mathbb{R}\). The norm is the Euclidean norm, so \(\|\mathbf{v}\|^2=\mathbf{v}^{\top}\mathbf{v}\), and two vectors are orthogonal when their dot product is zero. Suppose \(\mathbf{A}\in\mathbb{R}^{m\times n}\) has full column rank, with \(m\ge n\), and has a reduced QR factorization \(\mathbf{A}=\mathbf{Q}\mathbf{R}\). Here \(\mathbf{Q}\in\mathbb{R}^{m\times n}\) has orthonormal columns and \(\mathbf{R}\in\mathbb{R}^{n\times n}\) is nonsingular and upper triangular. Orthonormality means that the columns have length one and are pairwise orthogonal; in matrix form, \(\mathbf{Q}^{\top}\mathbf{Q}=\mathbf{I}_n\).

The columns of \(\mathbf{A}=\mathbf{Q}\mathbf{R}\) are combinations of the columns of \(\mathbf{Q}\). When \(\mathbf{R}\) is nonsingular, both matrices have the same column space. Thus the component of \(\mathbf{b}\) in \(\operatorname{Col}\mathbf{A}\) can be written using \(\mathbf{Q}\), while the leftover component is orthogonal to that space. The key is that changing \(\mathbf{x}\) changes only the first component; it cannot remove the orthogonal leftover.

The Orthogonal Decomposition Behind the QR Solve

For any \(\mathbf{b}\in\mathbb{R}^m\), define \(\mathbf{y}=\mathbf{Q}^{\top}\mathbf{b}\) and \(\mathbf{z}=\mathbf{b}-\mathbf{Q}\mathbf{y}\). Then \(\mathbf{b}=\mathbf{Q}\mathbf{y}+\mathbf{z}\). Moreover,

So \(\mathbf{z}\) is orthogonal to every column of \(\mathbf{Q}\), and hence to every vector in \(\operatorname{Col}\mathbf{Q}\). For any \(\mathbf{x}\), the residual can now be split into two orthogonal parts:

The second term lies in \(\operatorname{Col}\mathbf{Q}\); the first is orthogonal to that space. For orthogonal vectors \(\mathbf{u}\) and \(\mathbf{v}\), expanding the dot product gives \(\|\mathbf{u}+\mathbf{v}\|^2=\|\mathbf{u}\|^2+\|\mathbf{v}\|^2\), because the two cross terms are zero. Also, \(\|\mathbf{Q}\mathbf{c}\|^2=\mathbf{c}^{\top}\mathbf{Q}^{\top}\mathbf{Q}\mathbf{c}=\|\mathbf{c}\|^2\). Together these facts give the exact objective:

Proof. Put \(\mathbf{y}=\mathbf{Q}^{\top}\mathbf{b}\) and \(\mathbf{z}=\mathbf{b}-\mathbf{Q}\mathbf{y}\). The calculation above proves that \(\mathbf{z}\perp\operatorname{Col}\mathbf{Q}\) and that, for every \(\mathbf{x}\), \(\|\mathbf{b}-\mathbf{A}\mathbf{x}\|^2=\|\mathbf{z}\|^2+\|\mathbf{y}-\mathbf{R}\mathbf{x}\|^2\). The second summand is nonnegative, so the objective is at least \(\|\mathbf{z}\|^2\). Since \(\mathbf{R}\) is nonsingular, the system \(\mathbf{R}\widehat{\mathbf{x}}=\mathbf{y}\) has exactly one solution. At that solution the second summand is zero, so the lower bound is attained. Any minimizer must make that summand zero, which forces \(\mathbf{R}\mathbf{x}=\mathbf{y}\), and thus must equal \(\widehat{\mathbf{x}}\). The residual there is \(\mathbf{z}=\mathbf{b}-\mathbf{Q}\mathbf{Q}^{\top}\mathbf{b}\). \(\square\)

Because \(\mathbf{R}\) is upper triangular, the equation can be solved by back substitution, starting from its last row. The QR argument does not claim that the original equations \(\mathbf{A}\mathbf{x}=\mathbf{b}\) have an exact solution. It proves instead that matching the \(\mathbf{Q}\)-coordinates of \(\mathbf{b}\) removes every part of the residual that lies in the column space, leaving only the orthogonal component.

Worked QR Least-Squares Calculations

What Changes When the Columns Are Dependent?

A rank-deficient matrix cannot have a nonsingular square \(\mathbf{R}\) in a reduced factorization with \(n\) columns in \(\mathbf{Q}\). A rank-\(r\) factorization instead has \(\mathbf{Q}\in\mathbb{R}^{m\times r}\) with orthonormal columns and \(\mathbf{R}\in\mathbb{R}^{r\times n}\). In this case \(\mathbf{R}\) has full row rank, but may have more columns than rows. The same orthogonal decomposition proves that the least-squares minimizers are exactly the solutions of \(\mathbf{R}\mathbf{x}=\mathbf{Q}^{\top}\mathbf{b}\); the system may have multiple solutions rather than one triangular back-substitution solution.

Proof. Set \(\mathbf{y}=\mathbf{Q}^{\top}\mathbf{b}\) and \(\mathbf{z}=\mathbf{b}-\mathbf{Q}\mathbf{y}\). As before, \(\mathbf{Q}^{\top}\mathbf{z}=\mathbf{0}\), and for every \(\mathbf{x}\), \(\mathbf{b}-\mathbf{A}\mathbf{x}=\mathbf{z}+\mathbf{Q}(\mathbf{y}-\mathbf{R}\mathbf{x})\), a sum of orthogonal vectors. Therefore the squared residual norm is \(\|\mathbf{z}\|^2+\|\mathbf{y}-\mathbf{R}\mathbf{x}\|^2\). Full row rank means that the columns of \(\mathbf{R}\) span \(\mathbb{R}^r\), so the equation \(\mathbf{R}\mathbf{x}=\mathbf{y}\) has a solution. Every solution attains the lower bound \(\|\mathbf{z}\|^2\), and any minimizer must attain that bound, forcing \(\mathbf{R}\mathbf{x}=\mathbf{y}\). \(\square\)

Common Mistake: Requiring an Exact Fit

In the first worked example, a tempting but incorrect step is to solve \(\mathbf{A}\mathbf{x}=\mathbf{b}\) and conclude that the least-squares problem has no solution because the third row says \(0=4\). That calculation only proves that no exact fit exists. It does not rule out a vector that minimizes the residual. The QR calculation gives \(\widehat{\mathbf{x}}=(\tfrac32,2)^{\top}\), with residual \((0,0,4)^{\top}\); every other choice adds a nonzero component in the column space to this orthogonal residual, increasing the squared norm.

Another error is to replace \(\mathbf{Q}^{\top}\mathbf{b}\) with \(\mathbf{Q}\mathbf{b}\). The matrix \(\mathbf{Q}\) is generally rectangular, so \(\mathbf{Q}\mathbf{b}\) may not even be defined. The coordinate vector in the orthonormal columns is \(\mathbf{Q}^{\top}\mathbf{b}\); the corresponding vector in the original space is \(\mathbf{Q}\mathbf{Q}^{\top}\mathbf{b}\). Keeping those two roles separate makes the decomposition and dimensions consistent.