Linear Algebra › Section F · Orthogonality and least squares › Topic F.4

The Gram-Schmidt process and QR

Orthogonal bases make projections and coordinates easy, but subspaces rarely come with one. The Gram-Schmidt process builds one from any basis, and recording its steps gives the QR factorisation, a workhorse of numerical computing.

From any basis to an orthogonal one

The projection formula in "Orthogonal projections" needs an orthogonal basis of the subspace. In practice a subspace is usually handed over as the span of some vectors, such as the columns of a matrix, and those vectors are rarely perpendicular. The Gram-Schmidt process fixes this. It takes a basis \(\mathbf{x}_1, \dots, \mathbf{x}_p\) of a subspace \(W\) and produces an orthogonal basis \(\mathbf{v}_1, \dots, \mathbf{v}_p\) of the same subspace, one vector at a time, using nothing more than the projection onto a line and onto a subspace.

The idea: remove what you already have

Keep the first vector: \(\mathbf{v}_1 = \mathbf{x}_1\). The second vector \(\mathbf{x}_2\) usually leans partly along \(\mathbf{v}_1\). Subtract that part, its projection onto \(\mathbf{v}_1\), and what is left is perpendicular to \(\mathbf{v}_1\). This is exactly the perpendicular piece \(\mathbf{z}\) of the orthogonal decomposition. For the third vector, subtract its projection onto the plane spanned by \(\mathbf{v}_1\) and \(\mathbf{v}_2\). Since those two are already orthogonal, that projection is the sum of two line projections. Each new \(\mathbf{v}_k\) keeps only the genuinely new direction that \(\mathbf{x}_k\) adds.

The process in formulas

Given a basis \(\mathbf{x}_1, \dots, \mathbf{x}_p\) of \(W\), define \(\mathbf{v}_1 = \mathbf{x}_1\) and, for \(k = 2, \dots, p\),

\mathbf{v}_k = \mathbf{x}_k - \sum_{j=1}^{k-1} \frac{\mathbf{x}_k \cdot \mathbf{v}_j}{\mathbf{v}_j \cdot \mathbf{v}_j}\,\mathbf{v}_j

Then \(\{\mathbf{v}_1, \dots, \mathbf{v}_p\}\) is an orthogonal basis of \(W\). More than that, for every \(k\), \(\mathbf{v}_1, \dots, \mathbf{v}_k\) span the same subspace as \(\mathbf{x}_1, \dots, \mathbf{x}_k\). No \(\mathbf{v}_k\) is zero, because the \(\mathbf{x}\)s are independent: \(\mathbf{x}_k\) is never in the span of the earlier vectors. Each \(\mathbf{v}_k\) may be rescaled, for example to clear fractions, without spoiling later steps.

Worked example: two vectors in R3

Find an orthonormal basis for the plane spanned by \(\mathbf{x}_1 = (1, 2, 2)\) and \(\mathbf{x}_2 = (4, 5, 2)\). 1. Keep \(\mathbf{v}_1 = (1, 2, 2)\), so \(\mathbf{v}_1 \cdot \mathbf{v}_1 = 9\). 2. Weight: \(\frac{\mathbf{x}_2 \cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1} = \frac{4 + 10 + 4}{9} = 2\). 3. Subtract: \(\mathbf{v}_2 = (4, 5, 2) - 2(1, 2, 2) = (2, 1, -2)\). 4. Check: \(\mathbf{v}_1 \cdot \mathbf{v}_2 = 2 + 2 - 4 = 0\). 5. Normalise: both have length 3, giving \(\frac{1}{3}(1, 2, 2)\) and \(\frac{1}{3}(2, 1, -2)\). These two unit vectors span the same plane as \(\mathbf{x}_1\) and \(\mathbf{x}_2\).

Worked example: three vectors in R4

Orthogonalise \(\mathbf{x}_1 = (1, 1, 1, 1)\), \(\mathbf{x}_2 = (3, 1, 3, 1)\), \(\mathbf{x}_3 = (4, 0, 2, 2)\). 1. \(\mathbf{v}_1 = (1, 1, 1, 1)\), with \(\mathbf{v}_1 \cdot \mathbf{v}_1 = 4\). 2. \(\mathbf{x}_2 \cdot \mathbf{v}_1 = 8\), weight 2, so \(\mathbf{v}_2 = \mathbf{x}_2 - 2\mathbf{v}_1 = (1, -1, 1, -1)\). 3. \(\mathbf{x}_3 \cdot \mathbf{v}_1 = 8\), weight 2; \(\mathbf{x}_3 \cdot \mathbf{v}_2 = 4 - 0 + 2 - 2 = 4\) and \(\mathbf{v}_2 \cdot \mathbf{v}_2 = 4\), weight 1. 4. Subtract: \(\mathbf{v}_3 = \mathbf{x}_3 - 2\mathbf{v}_1 - \mathbf{v}_2\), which is \((1, -1, -1, 1)\). 5. Check all three pairs: \(\mathbf{v}_1 \cdot \mathbf{v}_2 = 1 - 1 + 1 - 1\), \(\mathbf{v}_1 \cdot \mathbf{v}_3 = 1 - 1 - 1 + 1\) and \(\mathbf{v}_2 \cdot \mathbf{v}_3 = 1 + 1 - 1 - 1\), all 0.

The QR factorisation

Suppose the columns of an \(m \times n\) matrix \(A\) are linearly independent. Apply Gram-Schmidt to them and normalise, giving orthonormal vectors \(\mathbf{q}_1, \dots, \mathbf{q}_n\), and let \(Q\) be the \(m \times n\) matrix with these columns. Then

A = QR

where \(R\) is an \(n \times n\) upper triangular matrix with positive diagonal entries, so \(R\) is invertible. Why upper triangular? The span property says column \(\mathbf{x}_k\) of \(A\) lies in the span of \(\mathbf{q}_1, \dots, \mathbf{q}_k\), so it needs no later \(\mathbf{q}\)s: the entries of \(R\) below the diagonal are zero. The columns of \(Q\) are an orthonormal basis of \(\operatorname{Col} A\).

Computing R

There is no need to keep track of the weights during Gram-Schmidt. Once \(Q\) is known, multiply \(A = QR\) on the left by \(Q^T\). Since \(Q^TQ = I\),

R = Q^TA

Entry \((i, j)\) of \(R\) is \(\mathbf{q}_i \cdot \mathbf{x}_j\), the component of column \(j\) along \(\mathbf{q}_i\). The diagonal entry \(r_{kk}\) equals \(\|\mathbf{v}_k\|\), the length of the new direction found at step \(k\), which is why it is positive. A good check is that the computed \(R\) really comes out upper triangular; a non-zero entry below the diagonal signals an arithmetic slip.

Worked example: a QR factorisation

Let \(A\) have columns \(\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\) from the R4 example. 1. Each \(\mathbf{v}_k\) there has length 2, so dividing by 2 gives

Q = \frac{1}{2}\begin{bmatrix} 1 & 1 & 1 \\ 1 & -1 & -1 \\ 1 & 1 & -1 \\ 1 & -1 & 1 \end{bmatrix}

2. Compute \(R = Q^TA\), for example \(r_{12} = \mathbf{q}_1 \cdot \mathbf{x}_2 = \frac{3 + 1 + 3 + 1}{2} = 4\):

R = \begin{bmatrix} 2 & 4 & 4 \\ 0 & 2 & 2 \\ 0 & 0 & 2 \end{bmatrix}

3. Check the third column of \(A\): \(4\mathbf{q}_1 + 2\mathbf{q}_2 + 2\mathbf{q}_3\) is the sum of \((2, 2, 2, 2)\), \((1, -1, 1, -1)\) and \((1, -1, -1, 1)\), which is \((4, 0, 2, 2)\).

In practice: stability and history

The process is named after Jørgen Pedersen Gram, who used it in 1883, and Erhard Schmidt, who presented it in 1907; historians note that Laplace had used a similar computation earlier. Computed by hand with exact fractions it is flawless, but in floating-point arithmetic the classical version can lose orthogonality badly as rounding errors build up, especially when the columns are nearly dependent. Software therefore uses modified Gram-Schmidt, which subtracts one projection at a time from the updated vector, or Householder reflections. QR factorisations are central to solving least-squares problems, in the next topic, and to the QR algorithm for eigenvalues met in "Iterative and numerical eigenvalue methods".

Common mistakes to avoid

First, projecting \(\mathbf{x}_k\) onto the earlier \(\mathbf{x}\)s instead of the earlier \(\mathbf{v}\)s; only the \(\mathbf{v}\)s are orthogonal, so only they can be projected onto one at a time. Second, forgetting the denominators \(\mathbf{v}_j \cdot \mathbf{v}_j\). Third, adding a projection instead of subtracting it. Fourth, building \(Q\) from the unnormalised \(\mathbf{v}\)s; then \(Q^TQ \ne I\) and \(R = Q^TA\) fails. Fifth, computing \(AQ^T\) or \(A^TQ\) for \(R\). And if some \(\mathbf{v}_k\) comes out zero, the original vectors were dependent: \(\mathbf{x}_k\) was a combination of the earlier ones.

Key takeaways

Gram-Schmidt keeps \(\mathbf{v}_1 = \mathbf{x}_1\) and sets each \(\mathbf{v}_k\) to \(\mathbf{x}_k\) minus its projections onto \(\mathbf{v}_1, \dots, \mathbf{v}_{k-1}\). The result is an orthogonal basis of the same subspace, and the first \(k\) new vectors span the same space as the first \(k\) old ones. Normalising gives an orthonormal basis. For a matrix with independent columns, \(A = QR\): \(Q\) has orthonormal columns spanning \(\operatorname{Col} A\), and \(R = Q^TA\) is upper triangular with positive diagonal. Software uses modified Gram-Schmidt or Householder reflections for stability.

Flashcards

Flashcard

Gram-Schmidt process

Turns any basis of W into an orthogonal basis of W

One vector at a time.

Test your understanding

Question 1 of 5

Apply Gram-Schmidt to x₁ = (1, 0, 1) and x₂ = (3, 1, 1). What is v₂?

Question 2 of 5

A has linearly independent columns and A = QR is its QR factorisation. Which describes R?

Question 3 of 5

Q has orthonormal columns, and A = QR. How is R found from A and Q?

Question 4 of 5

Gram-Schmidt applied to x₁, x₂, x₃ produces v₃ = 0. What does this show?

Question 5 of 5

The first column of A is (3, 0, 4). In the QR factorisation of A, what is the (1, 1) entry of R?

← Previous topicNext topic →