12 Orthogonal Transformations and the QR Factorization
Orthogonal transformations are the gold standard of numerical linear algebra. Because an orthogonal transformation preserves Euclidean lengths and angles, it neither amplifies nor attenuates perturbations in the data. When an algorithm is composed entirely of orthogonal operations, the accumulation of floating-point rounding errors is strictly controlled, and the condition number of the transformation is identically one.
The QR factorization expresses a matrix as the product of an orthogonal matrix \(\bQ\) and an upper triangular matrix \(\bR\). This factorization provides an orthonormal basis for the column space of the matrix, transforming complicated geometric projections and overdetermined least-squares problems into straightforward triangular solves.
12.1 Orthogonality, Isometry, and Invariance
A square matrix \(\bQ \in \fR^{n \times n}\) is termed orthogonal if its columns form an orthonormal basis for \(\fR^n\). Equivalently, \[ \begin{align} \bQ^T\bQ = \bQ\bQ^T = \bI_n \iff \bQ^{-1} = \bQ^T. \end{align} \] For rectangular matrices \(\bQ \in \fR^{m \times n}\) with \(m \geq n\), we say that \(\bQ\) has orthonormal columns if \(\bQ^T\bQ = \bI_n\).
Let \(\bQ \in \fR^{n \times n}\) be an orthogonal matrix. For all vectors \(\bx, \by \in \fR^n\), the transformation \(\bx \mapsto \bQ\bx\) satisfies the following properties:
Inner Product Preservation: \(\langle \bQ\bx, \bQ\by \rangle = (\bQ\bx)^T(\bQ\by) = \bx^T\by = \langle \bx, \by \rangle\).
Isometry (Length Preservation): \(\|\bQ\bx\|_2 = \|\bx\|_2\).
Matrix 2-Norm and Conditioning: \(\|\bQ\|_2 = 1\) and \(\kappa_2(\bQ) = \|\bQ\|_2 \|\bQ^{-1}\|_2 = 1\).
Determinant: \(\det(\bQ) = \pm 1\), where \(+1\) corresponds to a pure rotation and \(-1\) corresponds to a reflection.
Using the transpose property of matrix multiplication, \((\bQ\bx)^T(\bQ\by) = \bx^T(\bQ^T\bQ)\by = \bx^T\bI\by = \bx^T\by\), which proves the preservation of inner products. Setting \(\bx = \by\) gives \(\|\bQ\bx\|_2^2 = \bx^T\bx = \|\bx\|_2^2\), proving length preservation. Taking the supremum over unit vectors yields \(\|\bQ\|_2 = \sup_{\|\bx\|_2=1} \|\bQ\bx\|_2 = 1\). Because \(\bQ^{-1} = \bQ^T\) is also orthogonal, \(\|\bQ^{-1}\|_2 = 1\), which establishes \(\kappa_2(\bQ) = 1 \cdot 1 = 1\). Finally, taking determinants on \(\bQ^T\bQ = \bI\) gives \((\det \bQ)^2 = 1 \implies \det \bQ = \pm 1\).
12.2 The QR Factorization
Let \(\bA \in \fR^{m \times n}\) with \(m \geq n\).
The Full QR Factorization is given by \[ \begin{align} \bA = \bQ\bR = \begin{pmatrix} \bQ_1 & \bQ_2 \end{pmatrix} \begin{pmatrix} \bR_1 \\ \bzero \end{pmatrix}, \end{align} \] where \(\bQ \in \fR^{m \times m}\) is orthogonal, \(\bQ_1 \in \fR^{m \times n}\), \(\bQ_2 \in \fR^{m \times (m-n)}\), and \(\bR_1 \in \fR^{n \times n}\) is upper triangular.
The Thin (Economy) QR Factorization retains only the first \(n\) columns: \[ \begin{align} \bA = \bQ_1 \bR_1, \end{align} \] where \(\bQ_1 \in \fR^{m \times n}\) satisfies \(\bQ_1^T\bQ_1 = \bI_n\) and \(\bR_1 \in \fR^{n \times n}\) is upper triangular.
If \(\bA\) has full column rank, the thin QR factorization is unique when the diagonal entries of \(\bR_1\) are chosen to be strictly positive.
(Subspace identification via QR) The columns of \(\bQ_1\) form an orthonormal basis for the column space (range) \(\mathcal{R}(\bA)\), while the columns of \(\bQ_2\) form an orthonormal basis for the orthogonal complement \(\mathcal{R}(\bA)^\perp = \mathcal{N}(\bA^T)\). For overdetermined least-squares problems where \(m \gg n\), the thin factorization requires significantly less storage (\(O(mn)\) vs \(O(m^2)\)) and is used in practical implementations.
12.3 Householder Triangularization
The standard method for computing the QR factorization of a dense matrix is the Householder reflection technique. At each step, a Householder reflector is constructed to zero out all subdiagonal entries of a column simultaneously.
Let \(\bv \in \fR^m\) be a nonzero vector. The Householder reflector associated with \(\bv\) is the matrix \[ \begin{align} \bH = \bI - 2 \frac{\bv\bv^T}{\bv^T\bv}. \end{align} \] Geometrically, \(\bH\) reflects any vector across the hyperplane orthogonal to \(\bv\). Every Householder reflector is symmetric (\(\bH^T = \bH\)) and orthogonal (\(\bH^T\bH = \bH^2 = \bI\)).
Given a vector \(\bx \in \fR^m\), we wish to find a reflector \(\bH\) that aligns \(\bx\) with the first canonical coordinate axis: \(\bH\bx = \pm \|\bx\|_2 \be_1\). The vector \(\bv\) is chosen as \[ \begin{align} \bv = \bx + \operatorname{sign}(x_1) \|\bx\|_2 \be_1, \end{align} \] where \(\operatorname{sign}(x_1) = 1\) if \(x_1 \geq 0\) and \(-1\) if \(x_1 < 0\). Choosing the sign of the first component ensures that the two added terms have identical signs, completely preventing catastrophic cancellation.
Let \(\bv = \bx - \alpha \be_1\). Because \(\bH\) preserves vector lengths, we must have \(\|\bH\bx\|_2 = \|\bx\|_2\), which requires \(\alpha = \pm \|\bx\|_2\). Computing \(\bv^T\bv\) gives \[ \begin{align} \bv^T\bv = (\bx - \alpha \be_1)^T(\bx - \alpha \be_1) = \|\bx\|_2^2 - 2\alpha x_1 + \alpha^2 = 2 \|\bx\|_2^2 - 2\alpha x_1 = 2 \bv^T\bx. \end{align} \] Applying \(\bH\) to \(\bx\) yields \[ \begin{align} \bH\bx = \bx - 2 \frac{\bv^T\bx}{\bv^T\bv} \bv = \bx - \bv = \alpha \be_1 = \pm \|\bx\|_2 \be_1. \end{align} \] To ensure numerical stability in floating-point arithmetic, we choose \(\alpha = -\operatorname{sign}(x_1)\|\bx\|_2\), so that \(v_1 = x_1 + \operatorname{sign}(x_1)\|\bx\|_2\) avoids subtracting nearly equal quantities.
(Matrix-free application and complexity) A Householder matrix \(\bH\) is never constructed as an explicit \(m \times m\) array. To apply \(\bH\) to a vector \(\by\), we compute \[ \begin{align} \bH\by = \by - \left( \frac{2\bv^T\by}{\bv^T\bv} \right) \bv, \end{align} \] which requires only an inner product and a vector update costing \(O(m)\) flops. For a matrix \(\bA \in \fR^{m \times n}\), Householder QR requires \(2mn^2 - \frac{2}{3}n^3\) flops.
12.4 Gram-Schmidt Orthogonalization
The Gram-Schmidt process constructs the thin QR factorization column by column by projecting each column of \(\bA\) onto the orthogonal complement of the previously computed basis vectors.
Let \(\ba_1, ..., \ba_n \in \fR^m\) be the columns of \(\bA\).
Classical Gram-Schmidt (CGS): For each column \(k = 1, ..., n\), compute all projections against the original vector simultaneously: \[ \begin{align} r_{ik} = \bq_i^T \ba_k \quad (i = 1, ..., k-1), \qquad \bv_k = \ba_k - \sum_{i=1}^{k-1} r_{ik} \bq_i, \qquad r_{kk} = \|\bv_k\|_2, \qquad \bq_k = \frac{\bv_k}{r_{kk}}. \end{align} \]
Modified Gram-Schmidt (MGS): For each column \(k\), subtract projections sequentially from the partially updated vector: \[ \begin{align} \bv_k^{(1)} = \ba_k, \qquad \bv_k^{(i+1)} = \bv_k^{(i)} - (\bq_i^T \bv_k^{(i)}) \bq_i \quad (i = 1, ..., k-1), \qquad \bq_k = \frac{\bv_k^{(k)}}{\|\bv_k^{(k)}\|_2}. \end{align} \]
(Stability hierarchy among orthogonalization methods) In exact arithmetic, CGS and MGS produce identical outputs. In floating-point arithmetic, however:
Classical Gram-Schmidt loses orthogonality rapidly: \(\|\bQ^T\bQ - \bI\|_2 \approx O(\varepsilon_{\text{mach}} \kappa(\bA)^2)\).
Modified Gram-Schmidt is significantly more robust: \(\|\bQ^T\bQ - \bI\|_2 \approx O(\varepsilon_{\text{mach}} \kappa(\bA))\).
Householder QR maintains orthogonality to machine precision: \(\|\bQ^T\bQ - \bI\|_2 \approx O(\varepsilon_{\text{mach}})\), completely independent of \(\kappa(\bA)\).
12.5 Orthogonal Projectors
Let \(S \subset \fR^m\) be a subspace with orthonormal basis columns stored in \(\bQ_1 \in \fR^{m \times n}\). The orthogonal projector onto \(S\) is the matrix \[ \begin{align} \bP = \bQ_1 \bQ_1^T. \end{align} \] Every orthogonal projector is symmetric (\(\bP^T = \bP\)) and idempotent (\(\bP^2 = \bP\)). The complementary projector \(\bP^\perp = \bI - \bP\) projects onto the orthogonal complement \(S^\perp\).
Let \(S \subset \fR^m\) be a linear subspace and let \(\bP\) be the orthogonal projector onto \(S\). For any vector \(\bb \in \fR^m\), the projected vector \(\bP\bb\) is the unique point in \(S\) that minimizes the Euclidean distance to \(\bb\): \[ \begin{align} \|\bb - \bP\bb\|_2 \leq \|\bb - \bs\|_2 \qquad \text{for all } \bs \in S. \end{align} \] Equality holds if and only if \(\bs = \bP\bb\).
For any \(\bs \in S\), decompose the error vector as \(\bb - \bs = (\bb - \bP\bb) + (\bP\bb - \bs)\). The first term satisfies \(\bb - \bP\bb = (\bI - \bP)\bb \in S^\perp\). The second term satisfies \(\bP\bb - \bs \in S\) because both vectors lie in \(S\). Since the two vectors belong to mutually orthogonal subspaces, the Pythagorean theorem yields \[ \begin{align} \|\bb - \bs\|_2^2 = \|(\bb - \bP\bb) + (\bP\bb - \bs)\|_2^2 = \|\bb - \bP\bb\|_2^2 + \|\bP\bb - \bs\|_2^2. \end{align} \] Because \(\|\bP\bb - \bs\|_2^2 \geq 0\), we have \(\|\bb - \bs\|_2^2 \geq \|\bb - \bP\bb\|_2^2\), with strict equality holding if and only if \(\|\bP\bb - \bs\|_2 = 0 \iff \bs = \bP\bb\).
Construct the Householder reflector \(\bH\) that transforms the vector \(\bx = (3, 4)^T\) into \(\alpha \be_1 = (-5, 0)^T\). Explicitly write out the \(2 \times 2\) matrix \(\bH\) and verify that \(\bH = \bH^T\) and \(\bH^2 = \bI\).
Compute the thin QR factorization of \(\bA = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{pmatrix}\) using Modified Gram-Schmidt.
Let \(\bP \in \fR^{m \times m}\) be an orthogonal projector. Prove that the eigenvalues of \(\bP\) can only be \(0\) or \(1\), and show that \(\operatorname{trace}(\bP) = \operatorname{rank}(\bP)\).
Explain why the condition number of any orthogonal matrix is equal to \(1\). What does this imply about the propagation of errors when applying orthogonal transformations?