📂Matrix Algebra

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.