Why does Gram-Schmidt lose orthogonality when the input vectors are nearly parallel?
answer
- subtracting two nearly equal vectors
- relative error explodes, absolute error does not
- dividing by a tiny norm amplifies it
- errors propagate into later vectors
- modified variant reorders the subtractions
basics
~20 sEach step subtracts projections from a vector, and for nearly parallel inputs that subtraction cancels two almost identical vectors. The tiny survivor is mostly rounding error, and normalising it magnifies that error, so the resulting directions are not truly perpendicular.
solid answer
~50 sGram-Schmidt builds `v_1 = a_1`, then `v_2 = a_2 - proj_{v_1}(a_2)`, then `v_3 = a_3 - proj_{v_1}(a_3) - proj_{v_2}(a_3)`, normalising each `v_k` to unit length. When `a_2` sits at a very small angle to `a_1`, the projection is almost all of `a_2`, so the subtraction is catastrophic cancellation: two nearly equal quantities differ in their leading digits and the small remainder keeps only the low-order bits, which are contaminated by rounding. Dividing that remainder by its own tiny norm scales the contamination up to unit size, so `u_2` is only approximately perpendicular to `u_1`, and the error propagates into every later vector. Mitigations: use the modified variant, which subtracts each projection from the running residual rather than all at once; re-orthogonalise a second time; or use Householder reflections, which are backward stable and give orthogonality near machine precision regardless of conditioning.
go deeper
Be ready to run the algorithm by hand on two or three small vectors: subtract the projections, normalise, and check that the results dot to zero. The numerical failure mode comes later.
Expect to explain what cancellation is — that subtracting nearly equal quantities leaves a result whose relative error is huge — and why dividing that result by its own small norm makes matters worse.
Show that you would measure orthogonality rather than assume it, name the modified variant and re-orthogonalisation as fixes, and describe the residual-norm check that catches effectively dependent input before it produces a noise vector.
Own the build-versus-adopt call: whether to keep an incremental column-at-a-time routine for its structure or move to a backward-stable factorisation, and set the standard that numerical properties are asserted with measurements, not with the textbook derivation.
## The algorithm Gram-Schmidt turns a set of independent vectors into an orthonormal set spanning the same directions. Given `a_1, a_2, a_3` in three dimensions: 1. `v_1 = a_1`, then `u_1 = v_1 / ||v_1||` 2. `v_2 = a_2 - (a_2 . u_1) u_1`, then `u_2 = v_2 / ||v_2||` 3. `v_3 = a_3 - (a_3 . u_1) u_1 - (a_3 . u_2) u_2`, then `u_3 = v_3 / ||v_3||` Each step removes everything the new vector shares with the directions already fixed, leaving only the genuinely new part. In exact arithmetic the output is perfectly orthonormal. ## Where the arithmetic goes wrong Consider `a_1 = (1, 0)` and `a_2 = (1, 1e-8)`. These are almost the same arrow. The projection of `a_2` onto `u_1 = (1, 0)` is `(1, 0)`, so `v_2 = (0, 1e-8)`. Mathematically that is fine: the residual is small but exactly perpendicular. In floating point it is not fine. Computing `a_2 - (a_2 . u_1) u_1` subtracts two vectors whose leading digits agree. **Catastrophic cancellation** means the leading digits annihilate and what survives is built from the trailing bits, where the earlier rounding of the dot product and the multiplication already live. The *absolute* error is unchanged by the subtraction, but the *relative* error explodes, because the result is now many orders of magnitude smaller than the terms that produced it. The normalisation step then divides by `||v_2||`, which is tiny. That scales the contaminated remainder — error included — up to unit length. The unit vector `u_2` you get back is a direction dominated by noise, and `u_1 . u_2` comes out noticeably far from zero rather than at machine precision. The damage does not stay local. Step 3 subtracts projections onto `u_1` and `u_2`; if `u_2` is not truly perpendicular to `u_1`, the corrections are wrong and `u_3` inherits the defect. Loss of orthogonality compounds across the set. ## How bad, in one number The standard way to quantify near-parallelism is the **condition number** of the set: loosely, the ratio between the largest and smallest amount of stretch the vectors can produce. Nearly parallel vectors have a huge condition number. For classical Gram-Schmidt, the departure from orthogonality grows roughly like machine epsilon times the **square** of the condition number. For the modified variant it grows roughly like machine epsilon times the condition number itself — one power better, which in practice is the difference between a usable answer and garbage. Householder reflections, the standard alternative, achieve orthogonality at machine precision essentially independent of the conditioning. ## Modified Gram-Schmidt The modified variant computes the same thing in exact arithmetic but reorders the operations. Instead of computing all projection coefficients against the original `a_3` and subtracting them at the end, it subtracts one projection, then computes the next coefficient against the **already partially reduced** vector: `w = a_3` `w = w - (w . u_1) u_1` `w = w - (w . u_2) u_2` The second coefficient is now taken from a vector that no longer contains any `u_1` component, so it does not carry that component's rounding error into the next correction. The reordering is free and strictly better numerically, which is why the classical form should be regarded as an exposition device rather than an implementation. ## Other mitigations **Re-orthogonalisation.** Run the subtraction step a second time on the result. The folk rule, backed by analysis, is that twice is enough: a second pass restores orthogonality to machine precision in all but pathological cases. The cost is roughly double. **Householder reflections or Givens rotations.** These build the orthonormal set by applying norm-preserving transformations instead of subtracting projections, so there is no cancellation step to poison. They are the default in serious numerical work when orthogonality matters more than the incremental, column-at-a-time structure that Gram-Schmidt offers. **Pivot on the largest residual.** Gram-Schmidt is order dependent — the first input keeps its direction exactly, and the rest are shaped by the sequence. Processing the vector with the largest remaining residual first delays the ill-conditioned subtractions and improves the outcome. ## Detecting the failure The cheap in-flight check is the ratio `||v_k|| / ||a_k||`. If the residual has collapsed to a small fraction of the original vector, the subtraction was nearly total and the direction you are about to normalise is unreliable. Below a chosen tolerance the honest response is to treat the input as effectively dependent and drop it, rather than emit a unit vector made of noise. The after-the-fact check is to compute all pairwise dot products of the outputs. They should be zero to within a few multiples of machine epsilon. Values around `1e-8` or larger on a double-precision run mean orthogonality was lost, and any downstream step relying on it — reading coordinates off with plain dot products, for instance — will be quietly wrong. A candidate who says the outputs are orthogonal because the algorithm says so, without ever measuring, has missed the point of the question.
- What does the modified variant of Gram-Schmidt actually change?It subtracts projections one at a time from the running residual, computing each new coefficient against the partially reduced vector rather than against the original input. In exact arithmetic the result is identical, but in floating point each coefficient is free of the components already removed, so rounding error is not recycled into later corrections. Same cost, strictly better accuracy.
- How would you detect mid-run that an input vector is effectively dependent on the earlier ones?Compare the residual norm to the original vector norm before normalising. If `||v_k|| / ||a_k||` has collapsed below a tolerance, almost everything was cancelled away and what remains is rounding noise. Treat that input as dependent and drop it instead of normalising a meaningless direction — which is exactly what pivoted implementations do.
- Is the output of Gram-Schmidt dependent on the order of the input vectors?Yes. The first input keeps its direction exactly and every later one is defined relative to those before it, so a different ordering produces a different orthonormal set — still valid, but not the same vectors. Numerically the ordering matters too: handling the vector with the largest residual first postpones the worst cancellation.
- Does normalising the inputs to unit length before you start fix the instability?No. Near-parallelism is about the angles between the vectors, not their lengths, and normalising changes only the lengths. Two unit vectors half a microradian apart still cancel almost entirely when one is projected out. Prescaling can help avoid unrelated overflow issues, but it leaves the conditioning of the set untouched.
Weigh a letter by putting a loaded truck on a weighbridge, then the truck plus the letter, and subtracting. The letter's weight is real, but the two big readings each carry more error than the answer you are trying to extract.
saying these in an interview costs you the question
- Calls the orthogonality loss ordinary rounding and therefore negligible
- Thinks normalising the output repairs lost orthogonality
- Claims classical and modified variants behave identically in floating point
- Cannot explain why subtracting nearly equal vectors loses precision
- Assumes the algorithm fails loudly on dependent input
- Never measures the pairwise dot products of the result