The residual the appended block cannot remove

What the appended block inherits found that block modified Gram–Schmidt, whose Q is far from orthogonal, solves least squares at Householder’s accuracy if the right-hand side is appended to A as one more block and the solution read out of the last block column of R. At κ = 10⁸, with the ill-conditioning between the blocks, the appended block gave a forward error of $6.9 \cdot 10^{-10}$ where the same Q through $Q^{\mathsf T}b$ gave $8.9 \cdot 10^{-3}$ — seven orders between two routes through one factorisation. It inherited, one level up, the rescue the right-hand side as one more column had measured for column modified Gram–Schmidt.

Every one of those problems was consistent: b was A times a known x, the residual exactly zero. The essay said so and named the consequence. The least-squares problem’s own sensitivity has two terms,

$$\frac{\|\delta x\|}{\|x\|} \lesssim \kappa u + \kappa^2 u\,\frac{\|r\|}{\|A\|\,\|x\|},$$

and the second, $\kappa^2$ times the relative residual, belongs to the problem rather than to any algorithm. Householder pays it. So does the appended block, which reads its answer from a factorisation that is no better than Householder’s. $Q^{\mathsf T}b$ pays $\kappa^2 u$ whatever the residual, because its loss is the Q’s. The column essay found the three routes converging as the residual grew. The block question was whether the appended block does the same, and at what residual it stops being worth the extra block.

The same problems, with a residual #

The problems are the previous essay’s: 64 × 16 matrices built in four blocks of four columns, with a prescribed κ from $10^2$ to $10^{12}$ and the ill-conditioning placed between the blocks, inside them, or spread through a generic matrix. The one change is the right-hand side. To $Ax_\star$ is added a vector orthogonal to the range of A — a fixed combination of the complementary columns of a Householder Q — scaled so that its norm is ρ times $\|Ax_\star\|$, for ρ = 0, $10^{-10}$, $10^{-8}$, $10^{-6}$, $10^{-4}$, $10^{-2}$ and 1. The exact least-squares solution is still $x_\star$, since the added component is orthogonal to the range, and it is also computed in rational arithmetic to check. Every route is scored against it, medians over three seeds.

At κ = 10⁸ with the ill-conditioning between the blocks, the picture has one flat line and two that climb together. $Q^{\mathsf T}b$ sits at $8.9 \cdot 10^{-3}$ from zero residual to one, unmoved by anything b does. Householder and the appended block sit near $10^{-9}$ until the residual reaches about $10^{-8}$, and then rise in step with it: $2.4 \cdot 10^{-8}$ and $1.6 \cdot 10^{-8}$ at $10^{-6}$, $2.4 \cdot 10^{-6}$ and $1.7 \cdot 10^{-6}$ at $10^{-4}$, $2.4 \cdot 10^{-4}$ and $1.7 \cdot 10^{-4}$ at a per cent. At ρ = 1 they reach $2.4 \cdot 10^{-2}$ and $1.7 \cdot 10^{-2}$, and $Q^{\mathsf T}b$, at $1.1 \cdot 10^{-2}$, is marginally the best of the three.

The climb is the problem’s $\kappa^2$ term, and the two stable routes sit on it together, about a fiftieth of the dotted line’s $\kappa^2 u\rho$ — the bound’s constant, which on these matrices is generous. Nothing the appended block did at zero residual protects it here, because what it did was to avoid the Q’s loss of orthogonality, and this error is not the Q’s. It is the answer’s own sensitivity to the data, paid by every algorithm that computes the answer in floating point.

The advantage falls as one over the residual #

Divided out, the story is a single shape. At each κ the advantage of appending b over multiplying by $Q^{\mathsf T}$ is flat at its consistent value while the residual is small, and once the residual is large enough for the $\kappa^2$ term to dominate the stable routes it falls as one over ρ. With the ill-conditioning between the blocks, at κ = $10^8$: $1.3 \cdot 10^7$ with no residual, $1.3 \cdot 10^7$ still at $10^{-8}$, $5.4 \cdot 10^3$ at $10^{-4}$, 54 at a per cent and 0.67 at one. Each hundredfold increase in the residual past the knee takes a factor of a hundred off the advantage.

The knee is where the two terms of the bound cross, $\kappa u \approx \kappa^2 u \rho$, at ρ of about 1/κ, shifted by the constant. That is why the lines for larger κ leave their plateaus earlier and higher and all arrive at the same diagonal: the advantage past the knee is about $C/\rho$, with no κ in it, because both errors are then proportional to $\kappa^2 u$ and $\kappa^2 u\rho$ and their ratio is one over the residual.

Turn the dial and only the constant C moves. With the ill-conditioning between blocks it is about one half; inside the blocks, about one; on a generic matrix, about twenty. At ρ = 1 the advantage is therefore between 0.67 and 2.1 on the two structured placements and 21 on the generic one at κ = $10^8$; across every placement and every κ it is never above 43 at a residual of one. The generic matrix keeps more because its $Q^{\mathsf T}b$ error is larger — 0.22 at κ = $10^8$, against $8.9 \cdot 10^{-3}$ with the ill-conditioning between blocks — while the stable routes’ $\kappa^2$ term is about the same size on both. The two routes’ $\kappa^2$ terms are not one term with one coefficient; they are two terms of the same order, set by different things — the Q’s loss of orthogonality on one side, the problem’s own sensitivity on the other.

The knee is where the problem’s two terms cross #

At a smaller condition number the knee moves right, and the figure shows where. At κ = $10^6$ on a generic matrix Householder’s error is $3.1 \cdot 10^{-11}$ with no residual and still $3.1 \cdot 10^{-11}$ at a residual of $10^{-6}$; then $1.5 \cdot 10^{-10}$ at $10^{-4}$, $1.5 \cdot 10^{-8}$ at a per cent and $1.5 \cdot 10^{-6}$ at one — a factor of a hundred for every factor of a hundred in ρ past the knee. The appended block follows it a factor of three below, from $8.3 \cdot 10^{-12}$ to $5.1 \cdot 10^{-7}$. $Q^{\mathsf T}b$ does not move from $2.2 \cdot 10^{-5}$, so at ρ = 1 the appended block is 43 times better and Householder 14 times.

The bound’s two terms, κu and $\kappa^2 u\rho$, are equal at ρ = 1/κ, which is $10^{-6}$ here and $10^{-8}$ at κ = $10^8$. The measured knees sit there to within the factor of fifty by which these matrices fall short of the bound’s second term: between $10^{-6}$ and $10^{-4}$ at κ = $10^6$, between $10^{-8}$ and $10^{-6}$ at $10^8$. Read as a rule of thumb for a code that knows its condition number roughly, the appended block’s full consistent advantage holds while the relative residual is below about one over κ, and past that it is about one over the residual whatever κ is.

A relative residual is not an abstraction in a fitting code. It is the size of what the model does not explain, relative to what it does: the noise in the data, plus whatever the model leaves out. Data measured to one part in a thousand, fitted by a model that is otherwise right, gives a relative residual near $10^{-3}$, and at κ = $10^8$ the appended block is then worth about five hundred against $Q^{\mathsf T}b$ between blocks — a large factor on an error that is itself already the problem’s.

Never worse than Householder #

What the residual does not do is separate the appended block from Householder. At every κ, every residual and every placement where the answer has a digit left, the appended block’s error is between 0.061 and 3.6 times Householder’s, and most of the dots are below one. The previous essay’s finding survives the residual whole: the appended block reads its answer from the factorisation at Householder’s accuracy. It is only $Q^{\mathsf T}b$ it pulls away from less, and it pulls away less because Householder itself has come up to meet $Q^{\mathsf T}b$.

That distinction is the practical one. The column essay found the same convergence for column modified Gram–Schmidt and Householder, and the textbook statement of the result — that $Q^{\mathsf T}b$ from modified Gram–Schmidt is “only” as bad as the problem’s $\kappa^2$ term when the residual is large — is the same fact read from the other side. Two Gram–Schmidts showed the loss of orthogonality that makes $Q^{\mathsf T}b$ pay $\kappa^2$ at all; with a large residual the problem charges $\kappa^2$ anyway, and the loss stops mattering.

When the extra block is worth it #

Appending b is not free. In block modified Gram–Schmidt each block step projects the remaining blocks against the one just finished, and b as a fifth block is one more column in each of those projections — about $2mn$ extra multiply-adds against the $2mn^2$ of the projections themselves, and, in the modified loop, one more column riding along in each block step’s reduction rather than a synchronisation of its own. What it buys is the factor measured above, and the useful threshold is a factor of ten: below that, a code that already has Q would lose little by computing $Q^{\mathsf T}b$ afterwards.

On the grid, appending b buys a factor of ten or more up to a relative residual of one per cent at every κ from $10^4$ up and every placement, and up to a residual of one on the generic placement and at two of the between-blocks condition numbers. The only place it never buys ten is the best-conditioned problem with the ill-conditioning inside the blocks, κ = $10^2$, where the consistent advantage is only 5.3 and there was little to rescue. A per cent is a large residual for a fitting problem — a model that misses its data by one part in a hundred — and most least-squares problems met in practice sit below it. So the appended block remains the right default; a code solving problems it knows to be badly inconsistent can skip it with a loss that the figure bounds.

The other variants meet the same term #

The previous essay’s other three variants are worth reading at a residual too, because the residual changes their ranking as well. With the ill-conditioning between blocks at κ = $10^8$, two passes of classical block Gram–Schmidt with Householder inside, whose Q is orthogonal to rounding, gave $1.5 \cdot 10^{-9}$ by either route with no residual — Householder’s accuracy, since with an orthogonal Q the two routes are the same computation. At a residual of $10^{-4}$ it gives $1.1 \cdot 10^{-6}$, at a per cent $1.1 \cdot 10^{-4}$, and at one $1.1 \cdot 10^{-2}$: the $\kappa^2$ term again, at half Householder’s constant. The two-pass Cholesky variant, which on this placement solved the consistent problem well, sits a further factor of two below. One pass of classical block Gram–Schmidt gets 2.0 at every residual — its answer was already nothing, and a residual cannot take away digits that were never there.

So at a large residual every variant that was stable on the consistent problem sits on the $\kappa^2$ line within a factor of five of every other, and the choice between them goes back to what how wide the block should be and doing it twice priced — synchronisations and passes — rather than to accuracy. The appended block’s case rested on the consistent problem, where it bought a single pass of the modified loop the two-pass variants’ accuracy. At a residual of one, a single pass of the modified loop with $Q^{\mathsf T}b$ is as good as any of them, and so is everything else except the one-pass classical loop; at a per cent it is still fifty times behind the rest.

The factorisation reports the residual it was given #

A code that appends b gets one more number for free, and it is the one this essay’s threshold needs. In exact arithmetic, modified Gram–Schmidt on $[A\;b]$ leaves in the last diagonal entry of R the norm of what remains of b after projecting out every column of A — the least-squares residual norm, $\|b - Ax_\star\|$. Divided by $\|b\|$ it is the relative residual, up to the difference between $\|b\|$ and $\|Ax_\star\|$ that matters only when the residual is large. So the appended block tells its caller, after the fact, which side of the knee the problem was on: a small last diagonal entry means the solve was in the regime where appending bought its full factor, and a large one means the answer’s error is the problem’s $\kappa^2$ term, which no route could have removed.

$Q^{\mathsf T}b$ reports nothing of the kind; a code on that route computes the residual with one more product by A. That the entry means the same thing in floating point on these matrices — that its rounding is small against the residuals measured here — follows from the padded-matrix equivalence and is not separately measured.

Why the residual reaches Householder and not the appended block’s rescue #

It is worth being exact about which part of the previous result the residual removes. The rescue was that the appended block’s answer does not see the loss of orthogonality in Q. Björck and Paige’s account, which the column essay checked numerically, is that modified Gram–Schmidt on $[A\;b]$ is numerically a Householder factorisation of a padded matrix, so the last column of R is what Householder would have put there. That account says nothing about the problem’s conditioning, and so says nothing about the $\kappa^2$ term: Householder pays it, and so the padded Householder factorisation pays it too. The rescue is intact. What the residual removes is the thing it was being compared against — the gap between a stable route and $Q^{\mathsf T}b$ — by bringing the stable route up to $Q^{\mathsf T}b$’s order.

The road that squares the problem measured the normal equations paying $\kappa^2$ at once where QR pays κ, on consistent problems. The $\kappa^2$ term measured here is the reason that gap narrows on problems with a large residual: QR comes up to meet the normal equations exactly as Householder comes up to meet $Q^{\mathsf T}b$, which consistent problems could not show. An orthogonalisation nobody calls one priced the synchronisations a block Gram–Schmidt pays; the appended block adds none of its own in the modified loop, which is why its cost here is counted in arithmetic.

One size, one block width, one direction for the residual #

One size, one block width, three seeds, and a residual built from a fixed combination of the complementary directions. The $\kappa^2$ term’s constant depends on how the residual aligns with the left singular vectors paired with the smallest singular values, and a residual aimed at those directions would reach the bound’s full $\kappa^2 u\rho$ rather than a fiftieth of it. That would move the knee left and leave the slope where it is.

The column-wise modified Gram–Schmidt solve on $[A\;b]$, drawn in the sweep but not in the figures, sits below Householder by a factor of ten at large residuals on these problems — $2.1 \cdot 10^{-3}$ against $2.4 \cdot 10^{-2}$ at κ = $10^8$ and ρ = 1 between blocks. Both are on the $\kappa^2$ term; the constant differs, and why is not measured.

Still open: an aimed residual, and the tree #

A residual aimed at the weak directions. The residual here is a fixed combination of the complementary space. The worst case for the $\kappa^2$ term is a residual whose component along the left singular vectors paired with the smallest singular values is as large as it can be — which for a residual orthogonal to the range means one aligned with how those directions sit in the full space. Aiming it there and sweeping again would say whether the knee moves by the factor of fifty the bound’s slack suggests, and whether the appended block’s threshold of one per cent shrinks with it.

A tree instead of a sequence. The previous essay’s second question stands. A reduction that changes the order measured a tall-skinny QR done as a tree of Householder factorisations. Appending b to every leaf would inherit Householder’s accuracy leaf by leaf; whether the combining steps keep it, and whether a residual then reaches the tree’s answer the same way it reaches the sequence’s, is the block question asked where a distributed code asks it.