← Back to Linear Algebra

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

Projection onto W

Sum of projections onto an orthogonal basis

y-hat.

Check your understanding

In Gram-Schmidt, what is subtracted from each new vector x_k?

← Previous lesson Next lesson →