M4-T4 — The Gram-Schmidt Process

Learning objectives

After this lesson, you should be able to:

• Carry out the Gram-Schmidt process on two or three vectors.
• Derive each step from the projection formula and explain why the results are orthogonal.
• State the QR decomposition that results (A = QR) and what R contains.
• Explain why classical Gram-Schmidt loses orthogonality in floating point and what to use instead.

Introduction and motivation

A sensor's three axes are never exactly perpendicular after mounting. A set of calibration poses gives directions that are independent but not orthogonal. A robot's estimated rotation matrix drifts away from being a true rotation. In each case you want the nearest clean orthonormal frame, and the process that builds one from skewed directions is the simplest idea in the module: keep the first direction, and from each later one remove whatever the earlier ones already explain.

The intuition

Take the first vector and scale it to length 1: that is the first axis q₁. Now take the second vector. Part of it lies along q₁ (its shadow); the rest, perpendicular to q₁, is genuinely new. Subtract the shadow and keep the remainder, then scale it to length 1: that is q₂. For a third vector, subtract its shadows on both q₁ and q₂, and normalise what is left.

Each step uses only what you already know: the projection formula and the dot product. The result spans the same space as the inputs, just with perpendicular directions.

Geometric and physical interpretation

Geometric view. At step k, the span of the first k − 1 results is a flat subspace; the new vector is split into its projection onto that subspace (already covered) and its perpendicular remainder (new). The remainder, normalised, is the next axis, so the first k outputs span exactly the same space as the first k inputs. Physical view. Think of mounting three sensors with slightly misaligned axes. Gram-Schmidt keeps the first axis as the reference, makes the second as close as possible to the measured second while being perpendicular to the first, and so on: the result is the closest clean frame in a staged sense. (The nearest orthonormal matrix in an overall sense is found with the SVD in Module 6.)

The mathematics

a₁, …, a_n

the independent input vectors.

q₁, …, q_n

the orthonormal output vectors.

v_k

the unnormalised remainder at step k.

r_ik

the dot products q_i·a_k removed along the way; they form the matrix R.

The process

q1 = a1 / ‖a1‖
vk = ak − (q1·ak) q1 − ... − (q(k−1)·ak) q(k−1)
qk = vk / ‖vk‖

What it means. Subtract from each new vector its shadows on all the previous outputs. What is left is perpendicular to all of them. Divide by its length to get a unit vector.

The matrix form: QR

A = Q R,    Q = [q1 ... qn] (orthonormal columns),    R upper triangular with rii = ‖vi‖ > 0

What it means. Each input a_k is a combination of q₁, …, q_k with coefficients r_ik = q_i·a_k: a record of what was subtracted. Q holds the clean axes and R the coordinates of the original vectors in them. It is triangular because a_k never needs q_j with j > k.

Fragility

classical GS:  vk uses the ORIGINAL ak for all dot products          modified GS: update the working vector after each subtraction

What it means. Both give the same answer in exact arithmetic. Classical Gram-Schmidt computes every shadow from the original vector and can lose orthogonality badly in floating point; the modified version subtracts one shadow at a time from the updated vector and is much better; Householder QR is better still.

Gram-Schmidt: keep what is new. Subtract the shadows on the earlier axes, normalise the rest. In matrix form it is A = QR.

Step-by-step derivation: orthogonality of the outputs, and the QR relation

q₂ is orthogonal to q₁. With v₂ = a₂ − (q₁·a₂) q₁:

1. Dot with q₁: q₁·v₂ = q₁·a₂ − (q₁·a₂)(q₁·q₁).
2. Since q₁·q₁ = 1, this is q₁·a₂ − q₁·a₂ = 0. So v₂ ⟂ q₁, and so is q₂ = v₂/‖v₂‖.
3. v₂ ≠ 0 exactly because a₂ is not a multiple of a₁ (independence): if v₂ = 0 then a₂ = (q₁·a₂)q₁ would be a multiple of a₁.

The general step. For vk = ak − Σj<k (qj·ak) qj and any i < k: qi·vk = qi·ak − Σj(qj·ak)(qi·qj). By the orthonormality of the earlier outputs only j = i survives, giving qi·ak − qi·ak = 0. So each new vk is perpendicular to all earlier qi. This is the projection-remainder idea from the last lesson applied once per earlier axis.

The QR relation. Rearranging the definition, ak = ‖vk‖ qk + Σj<k (qj·ak) qj. Reading the coefficients as the k-th column of R (entries rjk = qj·ak above the diagonal and rkk = ‖vk‖ on it) gives A = QR with R upper triangular and positive on the diagonal.

Why it fails numerically. When the inputs are nearly dependent, vk is the small difference of nearly equal vectors; the subtraction cancels the leading digits and what remains is mostly rounding error, which then has a large component along the earlier q's. The classical version never corrects for the error committed at earlier subtractions; the modified version removes it as it goes.

A worked example: three vectors, and the numerical failure

Let a₁ = (1, 1, 0), a₂ = (1, 0, 1), a₃ = (0, 1, 1).

1. q₁. ‖a₁‖ = √2, so q₁ = (0.7071, 0.7071, 0).
2. q₂. q₁·a₂ = 0.7071, so v₂ = a₂ − 0.7071 q₁ = (1, 0, 1) − (0.5, 0.5, 0) = (0.5, −0.5, 1), with ‖v₂‖ = √1.5 = 1.2247, hence q₂ = (0.4082, −0.4082, 0.8165).
3. q₃. q₁·a₃ = 0.7071 and q₂·a₃ = 0.4082, so v₃ = a₃ − 0.7071 q₁ − 0.4082 q₂ = (0, 1, 1) − (0.5, 0.5, 0) − (0.1667, −0.1667, 0.3333) = (−0.6667, 0.6667, 0.6667), with ‖v₃‖ = 1.1547, hence q₃ = (−0.5774, 0.5774, 0.5774).
4. Check. q₁·q₂ = 0.2887 − 0.2887 + 0 = 0, q₁·q₃ = −0.4082 + 0.4082 = 0, q₂·q₃ = −0.2357 − 0.2357 + 0.4714 = 0. ✓ And R has diagonal 1.4142, 1.2247, 1.1547 (the norms found) with the dot products above the diagonal.
5. Failure. On the 8 × 8 Hilbert matrix (columns nearly parallel; condition number about 1.5·10¹⁰) the measured orthogonality error max|QᵀQ − I| is about 1 for classical Gram-Schmidt, about 2.4·10⁻⁷ for the modified version and about 3·10⁻¹⁶ for Householder QR, as in the figure.

Robotics application

Cleaning up frames. When a calibration yields three skewed axis estimates for a sensor frame, Gram-Schmidt (or the SVD-based nearest rotation of Module 6) produces a proper orthonormal frame. Check that the result has determinant +1 before using it as a rotation.

QR for least squares. Module 5 solves fitting problems with the QR decomposition, because working with the orthonormal Q avoids squaring the condition number. Gram-Schmidt explains where Q and R come from; library QR uses Householder reflections for accuracy.

Re-orthonormalising rotations. An attitude matrix integrated from gyro data slowly loses orthonormality. The UAV track's attitude representation lesson discusses why and how it is repaired; Gram-Schmidt on its columns is the textbook fix, with the caveat that it favours the first axis.

Subspace tracking. Incremental orthogonalisation of a stream of measurement directions (for example in a degeneracy detector) uses exactly this step: project out what is known, and measure what is left as a novelty score.

Engineering implications and limitations

Practical rules

• Use QR from a library, not hand-written Gram-Schmidt. Library QR uses Householder reflections and is backward stable. Classical Gram-Schmidt can lose all orthogonality (error near 1 on the Hilbert example).
• If you must write Gram-Schmidt, use the modified version and, for nearly dependent inputs, re-orthogonalise (run the step twice, “twice is enough”).
• Watch ‖v_k‖. A remainder much smaller than the input signals near-dependence: the direction of q_k is then dominated by rounding error. Treat a tiny ‖v_k‖ as “no new direction” and drop it, instead of normalising noise.
• The order matters. Different input orders give different, equally valid orthonormal bases. Gram-Schmidt favours the first vector (q₁ is exactly its direction), so put the most trustworthy axis first.
• Do not divide by zero. If an input is dependent on earlier ones its remainder is zero; the process must detect this (a rank-revealing method such as QR with pivoting or the SVD handles it).

Limits

Gram-Schmidt needs independent inputs. For dependent or nearly dependent data, use a rank-revealing factorisation (the SVD, Module 6). For turning an almost-orthogonal matrix into the nearest orthogonal one, the SVD, not Gram-Schmidt, is the right tool.

Common misconceptions

Engineering takeaways

1. Gram-Schmidt: q₁ = a₁/‖a₁‖; then subtract from each a_k its shadows on the earlier q’s and normalise the rest.
2. Each output is orthogonal to all earlier ones, because every shadow was removed; the first k outputs span the same space as the first k inputs.
3. In matrix form A = QR with Q orthonormal and R upper triangular holding the dot products and norms.
4. A tiny remainder means a nearly dependent input.
5. Classical Gram-Schmidt is numerically fragile (error near 1 on a hard example); use library QR (Householder) or at least the modified version.

References and further reading

Primary papers and authoritative documentation.

• MIT 18.06SC Linear Algebra (OCW): lecture on orthogonal bases and Gram-Schmidt
• Boyd and Vandenberghe, Introduction to Applied Linear Algebra (VMLS): the chapter on the Gram-Schmidt algorithm and QR; the site did not load when we last checked
• Mathematics for Machine Learning: the chapter on analytic geometry: Gram-Schmidt orthogonalisation
• Michigan ROB 101: Computational Linear Algebra: Gram-Schmidt and QR in a computational course

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Orthonormal columns give a matrix Q with QᵀQ = I. Matrices with this property, orthogonal matrices, deserve their own lesson: they are exactly the rotations and reflections, and they are the most numerically perfect matrices there are.

Related content

Nothing below is required to finish this lesson.

• Before
  M4-T3: Orthogonal Projections

  Project a vector onto a line or a subspace, and recognise the projection as the closest point.