An expiry date the noise does not move

The site’s account of conjugate gradients as a spectral filter ends on a sentence that reads like a verdict on the method. A parameter that counts steps put a 64-point deconvolution at one per cent noise through the iteration, obtained the filter factors twice by routes that share no arithmetic, and found that the two agree to 10⁻¹³ for a dozen steps and then separate. The Lanczos basis underneath them loses orthogonality between steps 16 and 20. The error against the true signal is least at step 20. And so: the textbook description of the method stops being true at exactly the step anybody would want to stop at.

That sentence puts three numbers in the method. Two of them are not in the same place at all.

The step at which the description expires is set by the operator and by the arithmetic run on it. It is the step at which a Ritz value has converged hard enough that the three-term recurrence stops producing orthogonal directions, and the derivation of the filter polynomial runs through a basis it assumes is orthogonal. Nothing about the right-hand side enters that number.

The step worth stopping at is set by the data. It is where the noise, amplified by division by a singular value of 10⁻¹⁰ or smaller, overtakes the signal still to be recovered. Nothing about the arithmetic enters that number: the same operator with cleaner measurements has a later optimum, in exact arithmetic as much as in binary64.

Two clocks, then, and the coincidence is that on one problem at one noise level they read the same time. Only one of them was moved when that reading was taken. Moving the other — over two decades of noise, and separately over three times the size — turns a warning about a method into a statement about which of two situations a reader is in, and the two situations want opposite things.

The clock the data sets moves by a factor of fifteen #

The step that minimises the error is the oracle of this field, and it requires the exact answer, so it is a measurement rather than a rule. Taken on the same operator at ten noise levels spanning two decades, it reads:

Three steps at the noisy end and forty-four at the clean one. The growth is not uniform across the range and the difference is worth marking, because a single rule of thumb would hide it: a factor of ten in the noise between 10% and 1% buys a factor of 6.7 in the step count, and the same factor of ten between 1% and 0.1% buys 2.2. Roughly, the optimum doubles for each halving of the noise while the noise is above a per cent, and then flattens out.

That flattening is where the answer stops being in the data arriving as a step count. Past a certain point better measurements stop buying more recoverable components, because the components they would buy sit below a singular value small enough that any noise at all swamps them. The best error column says the same thing more bluntly: a hundredfold improvement in the data moves it from 0.1675 to 0.1050, a factor of 1.6.

The clock the operator sets does not move at all #

The other quantity is the disagreement between the filter factors measured off the iterate and the factors predicted from the recurrence coefficients. It is drawn against the loss of orthogonality in the Lanczos basis, which is the thing that explains it, and both are read at every step.

At ten per cent noise the optimum is at step 3 and the disagreement is still at the level of rounding at step 12, four times later. Orthogonality is first worse than 10⁻⁹ at step 17; the disagreement crosses the same threshold at step 17 and passes 10⁻³ at step 20. So on the worst data in the range the description covers the useful part of the run with fourteen steps in hand, and the alarming sentence is not about this reader at all.

A factor of 3.3 in the noise separates those two figures, and the only thing that has moved is the plate. The whole table says so:

Two columns that do not move and one that moves by a factor of fifteen. The expiry sits at step 17 or 18 at every noise level over two decades, and the step at which the disagreement has become large enough to see sits at 20 or 21 at every one. The loss of orthogonality that drives it is even steadier: first worse than 10⁻⁹ at step 16 or 17, everywhere, with the disagreement following one or two steps behind. That lag is the mechanism visible as a delay — orthogonality goes first and the filter description follows it, which is the direction the derivation predicts and not the reverse.

Why the noise cannot reach that clock #

The noise lives in the right-hand side, and the Krylov space is built out of the right-hand side, so the natural expectation is that the noise ought to reach the expiry somehow. The table says it does not, and the reason is available as one further count.

The predicted factors are a polynomial whose roots are the Ritz values of AᵀA after m steps. The description fails when the basis those Ritz values were extracted from stops being orthogonal, and that basis stops being orthogonal when a Ritz value converges: the recurrence has nothing left to explore in that direction and drifts back into a direction it has already used. The clock that matters is therefore the schedule on which Ritz values converge.

Counted as the number of them within 10⁻⁸ relative of a true σ², that schedule reads 0 at step 12, 7 at step 16, 9 at step 17, and 13 or 14 at step 20. It reads that at every one of the ten noise levels in the table above. Not approximately: the counts at steps 12, 16 and 17 are identical across two decades of noise, and only the count at step 20 varies at all, between thirteen and fourteen.

That settles which of the two quantities the noise has access to. It changes the vector the iteration starts from and therefore changes the basis; it does not change how quickly the leading eigenvalues of AᵀA are resolved, because that is decided by how far apart they are. This operator’s spectrum decays exponentially with no gap anywhere, so the largest few σ² are separated by clear factors, and a Krylov method resolves well-separated eigenvalues on a schedule the right-hand side does not enter. The rate the condition number predicts is the same fact read for a different purpose — the spectrum sets the schedule, and the vector it is applied to does not appear in the bound.

The count also says what the size sweep below is going to do, before it is run. If the expiry is a fixed amount of convergence rather than a fixed step, then anything that changes how many steps that convergence takes will move it, and the number of unknowns is exactly such a thing.

The coincidence is a crossing, and it happens at about one per cent #

Read the two moving columns against each other and the coincidence stops being a property of anything. The optimum passes the expiry somewhere between one per cent noise and seven tenths of a per cent: at 1% the least-error step is 20 and the disagreement passes 10⁻³ at 21, and at 0.7% the least-error step is 24 and the threshold has not moved.

The first essay’s problem sat within one step of the crossing. That is not a coincidence about conjugate gradients; it is the one noise level at which the two situations meet, and picking anywhere else on the range would have produced a different sentence. At three per cent it would have read the description is exact throughout the region worth running in, and at two tenths of a per cent it would have read the description is false for half the run that matters.

At a tenth of a per cent the optimum is step 44 and the figure declines to be drawn — the generator refuses more than forty steps, on the ground that a longer run of this problem is not what the picture is about, and the marker would leave the canvas. The measurement is available without it: 44, at an error of 0.1050, against an expiry that has not moved from 18.

What the expiry actually costs, which is much less than the sentence suggests #

The natural reading of the description fails where the method is best is that a reader on the clean side of the crossing has been left without one. The honest question is what it costs to stay inside the description — to stop at step 18, the last step at which the two routes still agree to rounding, rather than at the optimum.

Twenty-six per cent, at the far end of the range and worst there. The step window on this problem is wide and lopsided — stopping early is forgiving and stopping late is not — and this is that fact collected at one particular early step. Retreating to the last step the filter description covers puts a reader inside the window everywhere on the clean side of the crossing.

The other side is where the cost is real, and it runs the other way. At ten per cent noise the error at step 18 is 0.6192 against a best of 0.1675, a factor of 3.70, and at five per cent it is 2.29. Holding to the description costs nothing there because the description already covers the optimum; holding to step 18 costs a factor of nearly four, because on that data eighteen steps is far too many. The expensive mistake and the invalid description are on opposite sides of the crossing, which is the practical content of separating the two clocks and is invisible while they are read as one.

The size moves the first clock and not the second #

The third control is the size of the problem, and it separates the two quantities again by moving the one the noise could not.

Nine sizes at one per cent noise, with the expiry read as the first step whose disagreement exceeds 10⁻⁹ and the optimum read from the same run:

The expiry rises at every step of the sweep, from 11 to 25 — one further step for every four or five unknowns added — and it does it monotonically, with the loss of orthogonality one or two steps ahead of it throughout. The optimum does not move in any direction: it wanders between 11 and 20 with no trend, which is what it should do, since the noise level and the shape of the singular value decay are unchanged and the number of components worth recovering is a property of those and not of how finely the operator is discretised.

So the same operator family at the same noise gives opposite verdicts at its two ends. At thirty-two unknowns the description has expired before the optimum, at 11 against 11 with the disagreement already 1.8·10⁻⁴ at step 12. At ninety-six it holds nine steps past the optimum. The sentence about the method is true at one size and false at another, on one problem, with the noise held fixed.

And the count of converged Ritz values says the same thing from the other side. Read at each size’s own expiry step, it is 7, 9, 11, 11 and 12 at thirty-two, forty-eight, sixty-four, eighty and ninety-six unknowns — near enough constant across a threefold change in size, while the step at which that many have converged runs from 11 to 25. The expiry is a fixed amount of convergence rather than a fixed step count, which is why the size moves it and the noise cannot.

The mechanism is the one an eigenvalue that arrives twice is about, seen through a different quantity. Orthogonality is lost when a Ritz value converges, and a smaller matrix has fewer directions for the recurrence to spread over, so convergence comes sooner in step count. The smaller problem is better conditioned — its smallest singular value is 2.1·10⁻¹² of the largest against 1.1·10⁻¹³ at ninety-six unknowns — and its description expires earlier anyway, which rules out conditioning as the explanation and leaves the count of converged Ritz values holding it.

At thirty-two unknowns the figure cannot be drawn at all, and the refusal is the informative kind. The generator asserts that the two routes agree through step 12 before it draws anything, and at thirty-two the assertion fails on its own evidence: the two routes agree at the early steps: worst 1.84·10⁻⁴. A picture whose whole subject is where an identity expires must refuse to be drawn on a problem where it has expired before the picture starts.

What a stopping rule that anybody runs actually does about this #

None of the optima above is available without the exact answer, so the practical question is where a real rule lands relative to the expiry. The discrepancy principle stops at the first step whose residual has fallen to the noise level, and the rules that have to find the step without the answer are all biased in the same direction.

Measured at its own stopping step, the disagreement between the two routes reads 8.8·10⁻¹⁴, 8.0·10⁻¹⁴, 7.1·10⁻¹⁴, 3.6·10⁻¹⁴, 4.8·10⁻¹⁴, 1.3·10⁻¹³ and 8.4·10⁻¹⁴ as the noise runs from ten per cent down to half a per cent — rounding, at every one. At three tenths of a per cent it has reached 1.1·10⁻¹¹, at two tenths 3.3·10⁻⁶, and at a tenth 0.29, where the description is simply gone.

So the rule stays inside the description for eight of the ten noise levels, and it does so for a reason nobody chose. It over-regularises — that is the standing criticism of it — and over-regularising means stopping early, and stopping early is exactly the side on which the filter polynomial is still an accurate account of what the iteration did. A rule tuned to hit the optimum would have walked out of the description on the clean half of the range. The conservative bias buys a second thing beyond the error margin it is usually defended on, and this is the measurement of it.

Where this stops being true #

The disagreement is not monotone, so “the step it expires at” is a threshold crossing rather than a last good step. At ten per cent noise the sequence past the crossing reads 5.2·10⁻³ at step 20, 1.1·10⁻¹ at 21, 1.4·10⁻² at 22 and 4.0 at 23. Orthogonality is monotone — the loss never repairs itself, and that is asserted step by step rather than between the ends — but the quantity built on top of it bounces by two orders of magnitude. A reader who stopped at step 22 on the strength of the number at 21 would have been lucky rather than right. Orthogonality read as a number is the monotone half of this pair, and it is the half worth watching.

The expiry is a property of this arithmetic and would move under a different one. Full reorthogonalisation would keep ‖QᵀQ − I‖ near rounding for as long as it was paid for, and the description would then hold wherever the budget reached; the two orthogonalisations measured against each other price exactly that. The first clock is not a fact about conjugate gradients, it is a fact about conjugate gradients run in binary64 without reorthogonalisation, which is how conjugate gradients is run.

One operator, one noise model, one decay. Everything here is a discretised convolution with an exponentially decaying spectrum and Gaussian noise added to the right-hand side. A spectrum with a gap in it would converge its Ritz values on a different schedule and move the expiry; correlated noise would move the optimum. The claim is that the two are set by different things, and it is measured over one operator’s noise range and one operator’s size range.

And the filter description is not the only one available. For a method whose Krylov space is built from A rather than AᵀA the weights are not a function of the singular value at all, which is what the basis decides what a filter is measures. That is a failure of the description at every step rather than past a particular one, and it is a different defect wearing similar clothes.

What follows for a reader on either side of the crossing #

On noisy data, the description is exact where it matters and can be used. Anything derived from the filter polynomial — an effective cutoff, a comparison against a Tikhonov λ at the matching σ, an estimate of which components the run has recovered — is accurate at the step worth stopping at, because the optimum sits well inside the valid region. At three per cent noise there are ten steps of margin.

On clean data, the optimum lies past the expiry, and stopping inside the description costs at most a quarter of the error. That is the cheap fix and it is worth naming as a decision rather than a default: a reader who needs the filter reading to be true buys it for twenty-six per cent at the worst point of the range measured here.

The knob is one of several, and the crossing moves when the others do. Four knobs against one floor puts the step count beside the other settings that decide where a computation lands, and the expiry is a constraint on only one of them.

The hybrid method removes the second clock and leaves the first. Solving a penalised problem inside the Krylov space at every step is the step that stops mattering, and it flattens the error curve so completely that the stopping decision stops being a decision. It does nothing to the orthogonality of the basis underneath, so the filter description of the outer iteration expires on the same schedule; what changes is that nobody needs to be at step 35 any more.

And a threshold decides where the expiry is, which makes it the same kind of number as the others this site is careful about. Leaves 10⁻⁹ and past 10⁻³ are two different columns above, three steps apart, and neither is the moment the identity stops holding — nothing is. Deciding when a quantity has become large enough to act on is the subject of the zero a reader is allowed to write, and it applies to a disagreement climbing through ten orders of magnitude as much as to anything else.

The sentence this essay started from is true of the problem it was measured on. What it is not is a property of conjugate gradients, and the difference is a per cent of noise either way. A description with an expiry date is only alarming if the date falls inside the interval anybody uses, and whether it does is a question about the data, not about the algorithm.