The runs part before the copy

The copies cost steps, not the filter ran conjugate gradients on the normal equations of a blurring matrix two ways that are one method in exact arithmetic: the short recurrence, which keeps two vectors and forgets the rest, and Golub–Kahan bidiagonalisation with every new basis vector reorthogonalised against all the earlier ones. The short recurrence found its leading Ritz values again and again — copies, a hundred of them on some draws — and spent steps doing it, up to four times as many to reach the same place. The best error was the same both ways.

It also compared the power $m = \theta_{\min}\sum_j 1/\theta_j$ that a power the spectrum does not set had found inside the filter, and here the two runs disagreed draw by draw by up to 0.49, though their medians agreed. The comparison was made at “1.3 of the answer” — the iterate whose position, the sum of its filter factors, was nearest 1.3 times the best iterate’s — and the essay read the scatter as an artefact of that: two runs reaching one position at different steps, with their smallest Ritz values in different places. It proposed the test with a sign. “At equal step counts the two runs’ $m$ agree to within 0.01 on every draw up to the step at which the short recurrence acquires its first copy, and diverge only after it — so that a copy, while it carries none of the power, changes it at once by moving the smallest Ritz value.”

The comparison at equal steps is straightforward to make, and every clause of the prediction is wrong in a direction that says something about what loss of orthogonality is.

Four events on every draw #

The problems are the earlier essays’: a Gaussian blur 1.5, 2.5 or 4 samples wide on sixty-four points, noise of one per cent or a tenth of one per cent, twelve draws of each. Each draw is run sixty steps both ways, and at every step both runs’ Ritz values are computed — the eigenvalues of the short recurrence’s Lanczos tridiagonal, and the squared singular values of the reorthogonalised run’s bidiagonal — and with them both values of $m$. Four events are read off each draw:

• the step at which the reorthogonalised run’s largest Ritz value is within $10^{-8}$ of the largest squared singular value — the first Ritz value to converge;
• the step at which the short recurrence’s newest basis vector has an inner product above $10^{-4}$ with an earlier one — its basis no longer orthogonal;
• the step at which the two values of $m$ differ by more than $10^{-6}$ — the runs have parted;
• the step at which the short recurrence holds two Ritz values within a relative $10^{-6}$ of each other, which on these spectra an orthogonal basis never does — the first copy.

The figure at the top of the page is in the order the events happen, and on every problem the order is the same: convergence, loss of orthogonality, parting, copy. On the narrowest blur the leading Ritz value converges at step 23, the basis loses orthogonality at 29, the runs part at 31 and the first copy appears at 39 or 40. On the middle blur: 15, 19, 20 or 21, and 27.5. On the widest: 10, 13, 14 or 15, and 18. The copy comes three to seventeen steps after the parting, never before it and never at the same step.

So the first clause, “up to the step at which the short recurrence acquires its first copy”, is wrong on all seventy-two draws. The two runs are already different numbers when the copy arrives.

Eleven digits, and then not one #

The second thing the figure cannot show is how complete the agreement is before the parting. The prediction allowed 0.01. While the short recurrence’s basis stays orthogonal to $10^{-4}$, the two values of $m$ agree to better than $10^{-11}$ on every draw, the largest difference over all seventy-two being $7.5 \cdot 10^{-12}$. That is not two methods approximating one quantity; it is one quantity computed twice, which is what exact-arithmetic equivalence promises and what rounding allows. Orthogonal is a number put the loss of orthogonality in general form, as a quantity that grows with the work done; for the first two-thirds of the run here it has not grown into any digit that matters, and the two routes are the same arithmetic in every digit $m$ is computed to.

The dial puts the three quantities on one axis, and the picture is the classical one. The leading Ritz value’s error falls steadily and then steeply, reaching $10^{-8}$ at step 14 and rounding level at 16 on the middle blur. As it falls, the short recurrence’s basis begins to lose orthogonality: its worst inner product, near $10^{-13}$ for the first thirteen steps, rises through $10^{-10}$ at step 16 and $10^{-4}$ at 19, and is near one two steps later. The difference in $m$ sits at rounding level throughout and then follows the inner product up, two or three decades behind it, passing $10^{-6}$ at step 21.

This is Paige’s account of the Lanczos process in floating point, and it is a theorem rather than a measurement: the component of each new Lanczos vector along a Ritz vector grows in inverse proportion to how small that Ritz vector’s residual has become, so a run starts losing orthogonality exactly when its first Ritz value converges, and only in the direction of that Ritz vector. An eigenvalue that arrives twice watched the mechanism on a symmetric eigenproblem. What the measurement adds is the order in which the consequences reach a quantity someone cares about. The leading Ritz value converges to eight digits four to eight steps before the runs part on every draw; the basis passes $10^{-4}$ at the same step or up to two before; and from $10^{-6}$ the difference in $m$ passes 0.01 within three steps on every draw.

Turn the dial and the events move together: on the narrowest blur everything happens at 23, 29, 31 and 39, on the widest at 10, 13, 14 and 18. The noise does not move them. At both noise levels each blur’s median parting step is the same to within a step, because the leading Ritz value converges at a rate set by the gap between the largest singular values, which is the blur’s and not the data’s.

Where the difference starts #

If the runs part before any copy exists, what is moving? The prediction’s last clause named the right quantity for the wrong reason: the smallest Ritz value. At the step the runs part, the largest relative difference between their sorted Ritz values is in the bottom fifth of the spectrum on every draw — at the very bottom on most — while their largest Ritz values agree to eight digits.

On this draw both runs hold twenty Ritz values at step 20, and the two smallest differ by three parts in a million. At step 21 the third smallest differs by a fifth, and the smallest by three per cent; at step 22 the bottom three differ by seventy per cent or more and the plain run’s smallest Ritz value stands at $6.6 \cdot 10^{-4}$ against the reorthogonalised run’s $3.8 \cdot 10^{-4}$. Only at step 24 does the short recurrence’s second Ritz value reach 1.0021, next to its first at 1.0025 — the start of a copy — and only at step 28 are the two within a millionth.

A copy is born at the bottom. Once the basis carries a component along the converged leading direction, the projected tridiagonal acquires an eigenvalue that belongs to no new direction of the operator; it appears low in the spectrum and climbs over the following steps until it sits on the converged value it duplicates. While it climbs it sits among the small Ritz values, and $m$, which is the smallest Ritz value times the sum of reciprocals, is made almost entirely of the bottom of the spectrum. The short recurrence’s smallest Ritz value is the larger of the two after the parting on this draw, which is what one should expect if one of its dimensions is spent on the climbing value and it has one fewer to push the bottom down with — the copies’ cost in steps, seen from inside a single step.

So the quantity the earlier essay chose to compare is the most sensitive one available. It is decided by the end of the spectrum where the duplicate is born, and it registers the duplicate’s birth several steps before the duplicate is recognisable as one.

The scatter was already there #

The earlier essay’s comparison point lies past the parting on 71 draws of 72. At one per cent noise 1.3 of the answer comes at 16 to 116 steps on the short recurrence; at a tenth of one per cent at 41 to 150. The parting comes at 14 to 31. Every one of those comparisons, but one, was made between a run whose bottom Ritz values had been disturbed and a run whose had not, and comparing them at the same step instead of the same position would not have removed the scatter. It would have shown it more cleanly. On the four problems where that step falls inside the sixty measured here, the two values of $m$ compared at the short recurrence’s own step differ by more than 0.01 on 36 draws of 39.

Where the answer itself falls is the more consequential reading, and it divides the problems sharply. At one per cent noise the answer comes before the parting on every draw of the narrowest blur, and on ten and eleven of twelve on the other two: a run stopped at its answer on noisy data never sees the disagreement, as the copies cost steps, not the filter found for the copies themselves. At a tenth of one per cent the answer comes after the parting on every draw of every blur — at medians of 60, 43 and 20 steps against partings at 31, 20 and 14. Any quantity read off the short recurrence’s Ritz values at the answer on clean data is read after the recurrence has stopped computing the projected problem it claims to compute. The first step’s filter, kept for the whole run and a corner chosen without the iteration both read Ritz values at and past the answer; on clean data, those readings belong to whichever run computed them.

What the iterates do meanwhile #

The iterates part with the power and not before it, though they are never as close as the powers are. A step before the parting they differ by $10^{-8}$ to $10^{-6}$ at the median; at the parting by $10^{-5}$ to $10^{-2}$; five steps later by two to sixty-seven per cent. That the iterates differ by a millionth while $m$ agrees to eleven digits is the difference between the two quantities’ conditioning: an iterate of a blurring problem is the solution of an ill-conditioned system and carries the rounding of two different computations multiplied by it, while the Ritz values are eigenvalues of a symmetric matrix and move by about as much as the rounding does.

Five steps after the parting the difference is large because the two runs are at different places along the same path: the short recurrence has spent a dimension on its climbing duplicate and is one step behind, and on a run past its answer one step can change the error by a fifth. That is the earlier essay’s finding — the same iterates, more slowly — seen at the moment it begins.

What the copy was #

The copy was the visible end of a process with three earlier stages, each measurable and each at a predictable step: a Ritz value converges, the basis begins to lose orthogonality along it, the projected spectrum acquires a value that belongs to no new direction, and only then does that value climb far enough to be recognised as a duplicate. The prediction picked the last of these as the moment of change because it is the one that is easy to see, and $m$, which reads the bottom of the spectrum, sees the third.

The lag between the parting and the copy is the stage the prediction skipped, and it is the one that varies. It is three to seven steps on the widest blur, three to eleven on the middle one and four to seventeen on the narrowest. The order matches how closely the operator’s two largest squared singular values sit: 1.0039 and 0.9656 on the widest blur, a relative gap of 3.8 per cent; 1.0025 and 0.9887 on the middle one, 1.4 per cent; 1.0015 and 0.9971 on the narrowest, 0.44 per cent. A duplicate climbing towards a converged value has to pass every Ritz value below it and resolve itself from its nearest neighbour, and the nearer that neighbour, the longer the duplicate spends looking like an ordinary Ritz value approaching the second singular value rather than a copy of the first. On the narrowest blur that ambiguity lasts up to seventeen steps, during which a reader counting copies would count none and a reader computing $m$ would already have the wrong number.

Two practical consequences follow. The first is about monitoring: a code that wants to know whether its short recurrence still computes the projected problem should watch the leading Ritz value’s convergence, which is cheap — the top of a tridiagonal’s spectrum — and predicts the parting four to eight steps ahead, not wait for a copy, which arrives three to seventeen steps too late. The second is about selective reorthogonalisation, the compromise the earlier essay raised, which reorthogonalises against converged Ritz vectors only. The measurement says when its first act is needed: at the step the first Ritz value converges, and not before, since until then the two runs are one computation to eleven digits.

What seventy-two draws do not settle #

The events are thresholds — $10^{-8}$ for convergence, $10^{-4}$ for orthogonality, $10^{-6}$ for parting, $10^{-6}$ for a copy — and moving any of them moves its event by a step or two, since each quantity is changing by orders of magnitude per step when it crosses. The ordering does not depend on them on any draw measured, and the gaps between events are several steps wide. The problems are all of one kind: Gaussian blurs on sixty-four points, whose leading singular values are well separated, so the first convergence is early and clean. An operator whose leading values are clustered would converge later and lose orthogonality along several directions at once, and the account here — one duplicate, born at the bottom — would then be several at once. The account of where the duplicate is born rests on the bottom-fifth measurement at the parting step and on reading one draw step by step; it is not followed through the climb on every draw.

Still open: reorthogonalising at the first convergence, and the climb itself #

One reorthogonalisation, at the right step. If the parting is caused by the first converged Ritz vector, then orthogonalising each new basis vector against that one vector, from the step it converges to $10^{-8}$, should hold the two runs together. The prediction with a sign is that on all seventy-two draws this keeps the two values of $m$ within $10^{-6}$ until the second Ritz value converges, which on these blurs is six to twelve steps later than the first, and that it removes the first copy entirely while leaving the second.

The climb. The duplicate is born at the bottom of the projected spectrum and climbs to the value it copies. The prediction is that its climb takes a number of steps proportional to the logarithm of the gap between the converged value and the next one down — slowest on the narrowest blur, where the leading squared singular values sit within a few per cent of each other — which would make the parting-to-copy lag, three to seventeen steps here, a property of the operator’s top gap and nothing else.

The flat stretch, still. The question the earlier essays asked about what sets the spacing of the smallest Ritz values can now be asked of a run with no duplicate in it, the reorthogonalised one: whether its ratio of the two smallest Ritz values at the answer is predicted, to a factor of 1.5, by the count of squared singular values between its corner and the noise floor of the data’s Picard plot — where the answer stops being in the data.