QR Decomposition for Least Squares Method
Algorithm
$A \in \mathbb{C}^{m \times n}$ and vector $\mathbf{b} \in \mathbb{C}^{m}$, let $\text{rank} A = n$ and the least squares solution of $A \mathbf{x} = \mathbf{b}$ be $\mathbf{x}_{\ast}$.
Step 1. QR decomposition
Find the orthogonal matrix $\widehat{Q}$ and upper triangular matrix $\widehat{R}$ that satisfy $A = \widehat{Q} \widehat{R}$.
Step 2.
Using the obtained $\widehat{Q}$ from QR decomposition to compute the projection $P : = \widehat{Q} \widehat{Q}^{\ast}$. Since $A \mathbf{x}_{\ast} = P \mathbf{b}$, it follows that $\widehat{Q} \widehat{R} \mathbf{x}_{\ast} = \widehat{Q} \widehat{Q}^{\ast} \mathbf{b}$, and by multiplying the left side of both sides by $\widehat{Q}^{\ast}$, we derive $\widehat{R} \mathbf{x}_{\ast} = \widehat{Q}^{\ast} \mathbf{b}$.
Step 3.
Calculate $\mathbf{y} := \widehat{Q}^{\ast} \mathbf{b}$ to get $\widehat{R} \mathbf{x}_{\ast} = \mathbf{y}$.
Step 4. Back substitution
Since $\widehat{R}$ is an upper triangular matrix, solve for $\mathbf{x}_{\ast}$ in equation $\widehat{R} \mathbf{x}_{\ast} = \mathbf{y}$ using back substitution.