Projections and the Gram-Schmidt process
Projecting onto subspaces finds closest points, and the Gram-Schmidt process converts any basis into an orthonormal one. Together they power least squares and the QR factorisation.
Projection onto a subspace
If \(\{\mathbf{u}_1, \dots, \mathbf{u}_p\}\) is an orthogonal basis of W, the orthogonal projection of \(\mathbf{y}\) onto W is \(\hat{\mathbf{y}} = \sum_i \frac{\mathbf{y} \cdot \mathbf{u}_i}{\mathbf{u}_i \cdot \mathbf{u}_i}\mathbf{u}_i\). The difference \(\mathbf{z} = \mathbf{y} - \hat{\mathbf{y}}\) lies in \(W^\perp\), so every vector decomposes uniquely as \(\mathbf{y} = \hat{\mathbf{y}} + \mathbf{z}\), one part in W and one orthogonal to it.
The best approximation theorem
The projection \(\hat{\mathbf{y}}\) is the point of W closest to \(\mathbf{y}\): \(\|\mathbf{y} - \hat{\mathbf{y}}\| < \|\mathbf{y} - \mathbf{v}\|\) for every other \(\mathbf{v}\) in W. This turns approximation problems, such as finding the best line through data or the best polynomial approximation of a function, into projection problems.
Projection matrices
If the columns of U form an orthonormal basis of W, the projection onto W is \(\hat{\mathbf{y}} = UU^T\mathbf{y}\), so the projection matrix is \(P = UU^T\). It is symmetric and satisfies \(P^2 = P\). With a general basis in the columns of A, the projection matrix is \(A(A^TA)^{-1}A^T\).
The Gram-Schmidt process
Given a basis \(\mathbf{x}_1, \dots, \mathbf{x}_p\), Gram-Schmidt builds an orthogonal basis of the same subspace: \(\mathbf{v}_1 = \mathbf{x}_1\); then each new \(\mathbf{v}_k\) is \(\mathbf{x}_k\) minus its projections onto all the earlier \(\mathbf{v}\)s. Each step removes the components along previous directions, leaving only the genuinely new direction. Dividing each \(\mathbf{v}_k\) by its length gives an orthonormal basis.
History and numerical practice
The process is named after Jorgen Pedersen Gram (1883) and Erhard Schmidt (1907), though Laplace used a similar idea earlier. In floating-point arithmetic, classical Gram-Schmidt can lose orthogonality; the modified Gram-Schmidt variant, which subtracts projections one at a time from the updated vector, and Householder reflections are more stable and are used in practice.
Orthogonal polynomials
Applying Gram-Schmidt to 1, t, \(t^2\), ... with the inner product \(\int_{-1}^{1} f g\,dt\) produces the Legendre polynomials, up to scaling: 1, t, \(t^2 - \frac{1}{3}\), and so on. Orthogonal polynomials are used in numerical integration (Gaussian quadrature), approximation theory, and physics, including solutions of equations in spherical coordinates.
Uses
Gram-Schmidt underlies the QR factorisation, discussed in the decompositions unit, which solves least-squares problems stably. In signal processing, orthonormal bases let signals be analysed and reconstructed exactly. In statistics, regression on orthogonalised predictors separates their contributions cleanly.
Worked example
Apply Gram-Schmidt to \(\mathbf{x}_1 = (1, 1, 0)\) and \(\mathbf{x}_2 = (1, 0, 1)\). Set \(\mathbf{v}_1 = (1, 1, 0)\). Then \(\mathbf{v}_2 = \mathbf{x}_2 - \frac{\mathbf{x}_2 \cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1}\mathbf{v}_1 = (1, 0, 1) - \frac{1}{2}(1, 1, 0) = (\frac{1}{2}, -\frac{1}{2}, 1)\). Check: \(\mathbf{v}_1 \cdot \mathbf{v}_2 = \frac{1}{2} - \frac{1}{2} + 0 = 0\). Normalising gives \(\frac{1}{\sqrt{2}}(1, 1, 0)\) and \(\frac{1}{\sqrt{6}}(1, -1, 2)\).
Key takeaways
Projection onto W with an orthogonal basis sums the projections onto each basis vector, and y = y-hat + z splits uniquely into parts in W and W-perp. The projection is the closest point of W to y, the best approximation theorem. With orthonormal columns U, the projection matrix is U U^T; with a general basis A, it is A (A^T A)^{-1} A^T. Gram-Schmidt (Gram 1883, Schmidt 1907) subtracts projections onto earlier vectors to build orthogonal, then orthonormal, bases; modified Gram-Schmidt and Householder reflections are more stable. Applied to polynomials it yields Legendre polynomials. It underlies QR and least squares.
Flashcard
Sum of projections onto an orthogonal basis
Check your understanding
In Gram-Schmidt, what is subtracted from each new vector x_k?
