QR Decomposition for Least Squares Method
Algorithm
$A \in \mathbb{C}^{m \times n}$ and vector $\mathbb{b} \in \mathbb{C}^{m}$, let $\text{rank} A = n$ and the least squares solution of $A \mathbb{x} = \mathbb{b}$ be $\mathbb{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 \mathbb{x}_{\ast} = P \mathbb{b}$, it follows that $\widehat{Q} \widehat{R} \mathbb{x}_{\ast} = \widehat{Q} \widehat{Q}^{\ast} \mathbb{b}$, and by multiplying the left side of both sides by $\widehat{Q}^{\ast}$, we derive $\widehat{R} \mathbb{x}_{\ast} = \widehat{Q}^{\ast} \mathbb{b}$.
Step 3.
Calculate $\mathbb{y} := \widehat{Q}^{\ast} \mathbb{b}$ to get $\widehat{R} \mathbb{x}_{\ast} = \mathbb{y}$.
Step 4. Back substitution
Since $\widehat{R}$ is an upper triangular matrix, solve for $\mathbb{x}_{\ast}$ in equation $\widehat{R} \mathbb{x}_{\ast} = \mathbb{y}$ using back substitution.