I need to solve $Ax=b$ in lots of ways using QR decomposition.
$$A = \begin{bmatrix}
1 & 1 \\
-1 & 1 \\
1 & 2
\end{bmatrix}, b = \begin{bmatrix}
1 \\
0 \\
1
\end{bmatrix}$$
This is an overdetermined system. That is, it has more equations than needed for a unique solution.
I need to find $\min ||Ax-b||$. How should I solve it using QR?
I know that QR can be used to reduce the problem to
$$\Vert Ax – b \Vert = \Vert QRx – b \Vert = \Vert Rx – Q^{-1}b \Vert.$$
but what do I do after this?
Best Answer
The most straightforward way I know is to pass through the normal equations:
$$A^T A x = A^T b$$
and substitute in the $QR$ decomposition of $A$ (with the convention $Q \in \mathbb{R}^{m \times n},R \in \mathbb{R}^{n \times n}$). Thus you get
$$R^T Q^T Q R x = R^T Q^T b.$$
But $Q^T Q=I_n$. (Note that in this convention $Q$ isn't an orthogonal matrix, so $Q Q^T \neq I_m$, but this doesn't matter here.) Thus:
$$R^T R x = R^T Q^T b.$$
If $A$ has linearly independent columns (as is usually the case with overdetermined systems), then $R^T$ is injective, so by multiplying both sides by the left inverse of $R^T$ you get
$$Rx=Q^T b.$$
This system is now easy to solve numerically.
For numerical purposes it's important that the removal of $Q^T Q$ and $R^T$ from the problem is done analytically, and in particular $A^T A$ is never constructed numerically.