Linear Algebra: QR Factorization

QR Factorization is one of the most versatile and numerically stable tools in computational linear algebra. It decomposes a matrix into an orthogonal matrix and an upper triangular matrix, providing a reliable foundation for solving linear systems, performing least squares regression, and even computing eigenvalues. For engineers and computational scientists, mastering QR factorization is essential for building robust, accurate algorithms that underpin simulations, data analysis, and signal processing.

What is QR Factorization?

QR factorization, also known as QR decomposition, expresses any real or complex $m\times n$ matrix $A$ (with $m\ge n$) as the product of two matrices: $A=QR$. Here, $Q$ is an $m\times m$ orthogonal matrix (or unitary for complex matrices), meaning its columns are orthonormal vectors and $Q^{T}Q=I$. $R$ is an $m\times n$ upper triangular matrix, where all entries below the main diagonal are zero. For a square matrix $A$, both $Q$ and $R$ are square.

The power of this decomposition lies in its structure. Orthogonal matrices are perfectly conditioned—their condition number is 1—meaning they do not amplify errors during computation. The triangular structure of $R$ makes systems of equations trivial to solve via back-substitution. This combination makes operations on $A$ both stable and efficient.

Computing QR: The Gram-Schmidt Process

The classical method for understanding QR factorization is the Gram-Schmidt orthogonalization process. It provides a constructive, step-by-step method for building the matrices $Q$ and $R$.

Given a matrix $A$ with linearly independent columns ${\vec{a}}_1,{\vec{a}}_2,...,{\vec{a}}_n$, the process orthonormalizes these columns to produce the columns of $Q$, denoted ${\vec{q}}_1,{\vec{q}}_2,...,{\vec{q}}_n$. The steps are:

1. Normalize the first column: ${\vec{q}}_1={\vec{a}}_1/\Vert {\vec{a}}_1\Vert$. The first entry of $R$ is $r_{11}=\Vert {\vec{a}}_1\Vert$.
2. Make the second column orthogonal to the first: Subtract the projection of ${\vec{a}}_2$ onto ${\vec{q}}_1$.

$${\vec{v}}_2={\vec{a}}_2-({\vec{q}}_1^T{\vec{a}}_2){\vec{q}}_1$$ Then normalize: ${\vec{q}}_2={\vec{v}}_2/\Vert {\vec{v}}_2\Vert$. The corresponding entries in $R$ are $r_{12}={\vec{q}}_1^T{\vec{a}}_2$ and $r_{22}=\Vert {\vec{v}}_2\Vert$.

1. Continue for all columns: For the $j$-th column, subtract its projection onto all previously computed ${\vec{q}}_i$:

$${\vec{v}}_j={\vec{a}}_j-\sum _{i=1}^{j-1}({\vec{q}}_i^T{\vec{a}}_j){\vec{q}}_i$$ Then set ${\vec{q}}_j={\vec{v}}_j/\Vert {\vec{v}}_j\Vert$. The entries of $R$ are $r_{ij}={\vec{q}}_i^T{\vec{a}}_j$ for $i<j$ and $r_{jj}=\Vert {\vec{v}}_j\Vert$.

While conceptually clear, classical Gram-Schmidt can suffer from numerical instability due to round-off errors, leading to a loss of orthogonality in $Q$. This is often remedied by using the Modified Gram-Schmidt algorithm, which mathematically yields the same result but performs the projection and subtraction steps in a numerically superior order.

Stable Numerical Methods: Householder and Givens

For serious computational work, engineers rely on more stable algorithms: Householder reflections and Givens rotations. These methods construct $Q$ implicitly as a product of simpler orthogonal transformations, avoiding the sequential error accumulation of Gram-Schmidt.

Householder reflections are the standard method for dense matrix factorization. A Householder matrix $P$ is defined as $P=I-2\vec{v}{\vec{v}}^T/({\vec{v}}^T\vec{v})$, where $\vec{v}$ is a carefully chosen vector. It represents a reflection across a hyperplane. The genius of the algorithm is that for each column of $A$, you can find a $P$ that zeros out all entries below the diagonal. By sequentially applying such reflections, $P_n...P_2{P}_{1}A=R$, and $Q$ is simply the product $Q=P_1^T{P}_2^T...P_n^T$. Householder is highly stable and is the preferred method for most general-purpose QR factorizations.

Givens rotations zero out matrix elements one at a time using $2\times 2$ rotation matrices embedded in an identity matrix. A Givens rotation selectively annihilates a single sub-diagonal entry. While requiring more operations than Householder for dense matrices, Givens rotations are invaluable for structured matrices like banded, sparse, or Hessenberg matrices, where you only need to eliminate specific non-zero elements.

Uniqueness and Applications

An important question is: is the QR factorization unique? For a full-rank matrix $A$, the factorization $A=QR$ is unique if we require that the diagonal entries of $R$ are all positive. If you allow negative diagonal entries, you can always adjust the signs by multiplying a column of $Q$ by -1 and the corresponding row of $R$ by -1, yielding a different but valid QR pair.

The primary applications of QR factorization are solving the least squares problem and powering the QR algorithm for eigenvalues.

Using QR for Least Squares: Given an overdetermined system $A\vec{x}\approx \vec{b}$ where no exact solution exists, the least squares solution minimizes $\Vert A\vec{x}-\vec{b}{\Vert }^2$. Using the normal equations (A^TA\vec{x} = A^T\vec{b) is algebraically correct but numerically disastrous, as it squares the condition number. The QR method is superior. Substitute $A=QR$: $$\Vert QR\vec{x}-\vec{b}{\Vert }^2=\Vert Q^T(QR\vec{x}-\vec{b}){\Vert }^2=\Vert R\vec{x}-Q^T\vec{b}{\Vert }^2$$ Because $Q$ is orthogonal, it preserves the 2-norm. Let $\vec{d}=Q^T\vec{b}$. We now have $\Vert R\vec{x}-\vec{d}{\Vert }^2$. Since $R$ is upper triangular, we find $\vec{x}$ by solving only the first $n$ rows of $R\vec{x}=\vec{d}$ via back-substitution, ignoring the bottom zero rows. This is stable and avoids forming $A^{T}A$.

QR Algorithm for Eigenvalue Computation: The celebrated QR algorithm is the standard method for finding all eigenvalues of a matrix. It works through an iterative process:

1. Start with $A_0=A$.
2. For $k=0,1,2,...$:

a. Compute the QR factorization of $A_k$: $A_k=Q_k{R}_k$. b. Form the next iterate by reversing the product: $A_{k+1}=R_k{Q}_k$. This iteration produces a sequence of similar matrices ($A_{k+1}=Q_k^T{A}_k{Q}_k$) that typically converges to an upper triangular Schur form, whose diagonal entries are the eigenvalues. Practical implementations first reduce the matrix to Hessenberg form using Householder reflections to dramatically improve efficiency.

Computational Advantages Over Normal Equations

The computational advantages of QR over the normal equations are significant and dictate modern practice. Forming the normal equations $A^{T}A$ requires roughly $m{n}^2$ operations and squares the condition number from $\kappa (A)$ to $\kappa (A{)}^2$. This means relative errors in $A$ or $\vec{b}$ can be amplified quadratically, potentially rendering the solution useless for ill-conditioned problems.

In contrast, computing the QR factorization via Householder requires about $2m{n}^2-\frac{2}{3}{n}^3$ operations—a comparable cost—but it operates directly on $A$ without forming $A^{T}A$. This preserves the original condition number, leading to vastly superior numerical stability. For rank-deficient or nearly rank-deficient problems, QR with column pivoting can also provide reliable diagnostics, whereas the normal equations simply fail.

Common Pitfalls

1. Using Classical Gram-Schmidt for Computation: Using the textbook Gram-Schmidt algorithm for numerical work often leads to a loss of orthogonality in $Q$ due to round-off error. Correction: Always use the Modified Gram-Schmidt algorithm or, better yet, default to Householder reflections for a general dense matrix.
2. Applying QR to the Normal Equations: It is a misconception that using QR on the normal equations is an improvement. Computing $A^{T}A$ and then performing QR on it loses all the stability benefits. Correction: Perform QR factorization directly on the original matrix $A$ and use it to solve the least squares problem as described.
3. Ignoring Matrix Structure: Using a dense Householder routine on a sparse or banded matrix is computationally wasteful. Correction: For matrices with special structure (e.g., tridiagonal, sparse), use the appropriate algorithm like Givens rotations to exploit the zeros and save substantial computation time and memory.
4. Assuming Uniqueness Without Condition: Stating that "the QR factorization is unique" is incorrect without specifying the condition on $R$. Correction: Remember that for a full-rank matrix, the QR factorization with positive diagonal entries in $R$ is unique. Otherwise, there is a sign ambiguity.

Summary

• QR Factorization decomposes a matrix $A$ into an orthogonal matrix $Q$ and an upper triangular matrix $R$ ($A=QR$), providing a numerically stable framework for a host of linear algebra problems.
• It can be computed via the conceptual Gram-Schmidt process, but for stability, engineers rely on Householder reflections (for dense matrices) and Givens rotations (for structured/sparse matrices).
• The factorization is unique if the diagonal entries of $R$ are restricted to be positive.
• Its premier application is solving the linear least squares problem stably, avoiding the error amplification inherent in solving the normal equations.
• It forms the core of the iterative QR algorithm, the standard method for computing all eigenvalues of a matrix.
• The key computational advantage of QR over the normal equations is the preservation of the condition number, leading to solutions that are reliable even for ill-conditioned problems.