QR Decomposition

QR decomposition is an alternative to the normal equations for solving overdetermined systems. It factors the coefficient matrix $A$ into an orthonormal matrix $Q$ and an upper triangular matrix $R$, then reduces the least squares problem to a simple triangular system. QR decomposition tends to be numerically more stable than forming $A^T A$ explicitly.

---

The Factorization $A = QR$

Any $m \times n$ matrix $A$ with $m \geq n$ and linearly independent columns can be written as:

$$A = QR$$

where:

• $Q$ is an $m \times n$ matrix whose columns $q_1, q_2, \dots, q_n$ form an orthonormal set.
• $R$ is an $n \times n$ upper triangular matrix with positive diagonal entries.

The columns of $Q$ are computed from the columns of $A$ using the Gram-Schmidt process.

---

The Gram-Schmidt Process

Let $u_1, u_2, \dots, u_n$ be the columns of $A$. The Gram-Schmidt process converts them into orthonormal vectors $q_1, q_2, \dots, q_n$ using two formulas applied for $k = 1, 2, \dots, n$:

$$p_k = u_k - \sum_{i=1}^{k-1} (u_k^T q_i)\,q_i$$ $$q_k = \frac{p_k}{|p_k|}$$

At each step, $p_k$ removes from $u_k$ all components in the directions already spanned by $q_1, \dots, q_{k-1}$. Dividing by $|p_k|$ then normalizes the result to unit length.

For $k=1$: The sum is empty (lower limit exceeds upper limit), so $p_1 = u_1$. We just normalize:

$$p_1 = u_1, \qquad q_1 = \frac{u_1}{|u_1|}$$

For $k=2$: Subtract the projection onto $q_1$:

$$p_2 = u_2 - (u_2^T q_1)\,q_1, \qquad q_2 = \frac{p_2}{|p_2|}$$

For $k=3$: Subtract projections onto both $q_1$ and $q_2$:

$$p_3 = u_3 - (u_3^T q_1)\,q_1 - (u_3^T q_2)\,q_2, \qquad q_3 = \frac{p_3}{|p_3|}$$

---

Assembling $R$

Once $Q$ is known, the entries of $R$ are the dot products of the original columns of $A$ with the orthonormal columns of $Q$. Because of the upper triangular structure of the Gram-Schmidt construction:

$$R = \begin{bmatrix} u_1^T q_1 & u_2^T q_1 & u_3^T q_1 & \cdots \\ 0 & u_2^T q_2 & u_3^T q_2 & \cdots \\ 0 & 0 & u_3^T q_3 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$

In general, $R_{ij} = u_j^T q_i$ for $i \leq j$, and $R_{ij} = 0$ for $i > j$.

---

Solving the Least Squares Problem via QR

Starting from $Ax = b$, substitute $A = QR$:

$$QR\, x = b$$

Multiply both sides on the left by $Q^T$:

$$Q^T Q R\, x = Q^T b$$

Because $Q$ has orthonormal columns, $Q^T Q = I$ (proved below). Therefore:

$$R\, x = Q^T b$$

This is an $n \times n$ upper triangular system, which is solved by back substitution. No matrix inversion or formation of $A^T A$ is needed.

---

Proof: $Q^T Q = I$

Let $Q = \begin{bmatrix} q_1 & q_2 & \cdots & q_n \end{bmatrix}$. Then:

$$Q^T Q = \begin{bmatrix} - & q_1^T & - \\ - & q_2^T & - \\ \vdots & & \vdots \end{bmatrix} \begin{bmatrix} | & | & \\ q_1 & q_2 & \cdots \\ | & | & \end{bmatrix} = \begin{bmatrix} q_1^T q_1 & q_1^T q_2 & \cdots \\ q_2^T q_1 & q_2^T q_2 & \cdots \\ \vdots & \vdots & \ddots \end{bmatrix}$$

Since $Q$ has orthonormal columns, $q_i^T q_j = \delta_{ij}$. Every diagonal entry equals 1 and every off-diagonal entry equals 0:

$$Q^T Q = \begin{bmatrix} 1 & 0 & \cdots \\ 0 & 1 & \cdots \\ \vdots & \vdots & \ddots \end{bmatrix} = I \qquad \blacksquare$$

---

Proof: $A = QR$

We show that the Gram-Schmidt process produces exactly the factorization $A = QR$.

From the Gram-Schmidt recurrence $q_k = p_k / |p_k|$, we have $p_k = |p_k|\,q_k$. Substituting back into the formula for $p_k$:

$$|p_k|\,q_k = u_k - \sum_{i=1}^{k-1}(u_k^T q_i)\,q_i$$

Rearranging to express $u_k$:

$$u_k = |p_k|\,q_k + \sum_{i=1}^{k-1}(u_k^T q_i)\,q_i \tag{1}$$

Multiply both sides of (1) by $q_k^T$ from the left:

$$q_k^T u_k = |p_k|\underbrace{q_k^T q_k}_{1} + \sum_{i=1}^{k-1}(u_k^T q_i)\underbrace{q_k^T q_i}_{0} = |p_k|$$

(The sum vanishes because $q_k^T q_i = 0$ for $i < k$, by orthogonality.)

Since the dot product is symmetric, $q_k^T u_k = u_k^T q_k$. Substituting $|p_k| = u_k^T q_k$ back into (1):

$$u_k = (u_k^T q_k)\,q_k + \sum_{i=1}^{k-1}(u_k^T q_i)\,q_i = \sum_{i=1}^{k}(u_k^T q_i)\,q_i$$

For $n = 3$ this expands to:

$$u_1 = (u_1^T q_1)\,q_1$$ $$u_2 = (u_2^T q_1)\,q_1 + (u_2^T q_2)\,q_2$$ $$u_3 = (u_3^T q_1)\,q_1 + (u_3^T q_2)\,q_2 + (u_3^T q_3)\,q_3$$

Stacking the columns:

$$A = \begin{bmatrix} | & | & | \\ u_1 & u_2 & u_3 \\ | & | & | \end{bmatrix} = \begin{bmatrix} | & | & | \\ q_1 & q_2 & q_3 \\ | & | & | \end{bmatrix} \begin{bmatrix} u_1^T q_1 & u_2^T q_1 & u_3^T q_1 \\ 0 & u_2^T q_2 & u_3^T q_2 \\ 0 & 0 & u_3^T q_3 \end{bmatrix} = QR \qquad \blacksquare$$

The second factor is exactly the upper triangular matrix $R$ defined earlier, confirming that the Gram-Schmidt construction gives a valid QR factorization.