Least-squares solution using QR

Recall our equation from least-squares:

$$Ax-b\perp \text{span}(A)$$

Let’s use the QR factorization: $A=QR$.

Because $R$ is upper triangular we have

$$\text{span}(A)=\text{span}(Q)$$

Thus, we get the equivalent linear system

$$Q^T(Ax-b)=0$$

Let’s solve for $x$:

$$Q^{T}Ax=Q^{T}QRx=Rx=Q^{T}b$$

using $A=QR$.

The final solution is

$$x=R^{-1}{Q}^{T}b$$

Recall the normal equation:

$$x=(A^{T}A{)}^{-1}{A}^{T}b$$

The condition number is reduced from

$$\kappa (A^{T}A)=\kappa (A{)}^2$$

to

$$\kappa (Q^{T}A)=\kappa (A)$$

This is a huge improvement!

Note that this method requires $R$ to be non-singular. This is equivalent to saying that $A$ should be full column rank.

The computational cost is $O(m{n}^2)$.

Least-squares problems, QR factorization, QR using Householder transformations, QR using Givens transformations, Method of normal equation