A count that marks the edge and not the pace

The parameter neither knob is ended with a measurement that looked like a rule waiting to be written down. A truncated fast-transform preconditioner has one parameter, the cutoff τ, and the cutoff decides how many of the approximation’s directions get divided by their eigenvalue and how many are left alone. That count is known the moment the preconditioner is built: it is the number of the transform’s eigenvalues at or above τ, read off a list that the transform produces for nothing — the same closed-form spectrum the matrix that is one row hands over without an eigensolver. On the collection’s usual deconvolution it rose 13, 18, 22, 25 as τ fell, and the stride of the preconditioned run — the effective dimension its best iterate carries, divided by the steps it took to get there — rose alongside it: 1.90, 2.32, 3.44, 3.53.

The effective dimension itself costs a singular value decomposition, which is exactly what an iterative method exists to avoid. The count does not. So the proposal was that the count could stand in for the stride: that a code could read, from something it already has, how fast its preconditioned run would travel, and from that where it would stop being any use. The measurement that would settle it was stated there in one line: does the count predict the stride well enough to be used in its place, and does the prediction survive a change of operator?

It does not predict the stride. It predicts something more useful, and it is worth being exact about which.

Three blurs, and how far each answer is #

Every measurement on this problem has so far been made on one operator: a Gaussian blur of width 2.5 grid points on 64 samples, with a signal that has a step and two bumps. Changing the operator is the whole of the test, and the natural change is the blur’s width. A narrower blur, 1.5 points, destroys less of the signal and lets more of it back; a wider one, 4 points, destroys more. A second blur, narrower than the first measured the same fact from the answer’s side: a regularised answer is itself a blurred copy of the truth, and how narrow its blur can be is set by how much of the data the instrument let through.

The figure shows what that means in the coordinate the effective-dimension essay introduced. With no preconditioner, conjugate gradients climbs an arc: each iterate carries a little more of the data, measured as the sum of the filter factors it is implicitly applying, and the error falls until the best iterate, after which it would rise. On the narrow blur the best iterate carries 33.1 of effective dimension, reached in 17 steps at an error of 0.0968. On the collection’s blur it carries 24.0, reached in 20 steps at 0.1426. On the wide blur it carries 12.8, reached in 11 steps at 0.1566.

Over twelve draws of 1% noise the medians are 32.2, 23.2 and 14.7. The narrow blur’s answer has more than twice the dimension of the wide one’s, which is the plain statement of what a blur does: the narrower the kernel, the more of the signal’s fine structure survives it strongly enough to be recovered above the noise, and the Picard plot would show the crossing moving right with it. None of this has anything to do with a preconditioner. The arc’s top is a fact about the operator, the signal and the noise, and it is the distance any preconditioned run has to cover.

The step counts are worth noticing for what they do not do. The narrow blur’s run covers a longer distance in fewer steps than the middle one’s, because its plain stride — 2.08 of dimension a step over the twelve draws — is longer to begin with. Stride and distance are separate quantities before any preconditioner is involved, and the question the count was meant to answer mixes them. A parameter that counts steps set the step count beside λ as the iterative field’s regularisation parameter; three blurs make plain that a step count without the operator attached is not a quantity at all.

The stride at the edge #

A preconditioner lengthens the stride; that was the finding of the previous measurement, and on the collection’s blur it held to a remarkable degree. Above a certain cutoff, the preconditioned iterates lie on the unpreconditioned arc and simply sample it more coarsely. Below that cutoff, the run’s first stride overshoots the arc’s top and it never lands on the arc at all. The edge between the two regimes was located as the cutoff at which fewer than half the run’s iterates land inside the arc.

If the count were a stride, the edge would be a stride: the construction would have a speed it cannot exceed, a constant fact about fast-transform preconditioners of this kind, and the count at which each blur reached it would differ only because the blurs’ spectra map counts to strides differently. That is a testable claim, and the test is to record the stride at which each blur’s run leaves its arc.

At 1% noise the narrow blur’s run leaves its arc at 33 directions divided and a stride of 5.71. The collection’s blur leaves at 22 directions and 3.44. The wide blur leaves at 15 and 2.41. The strides at the three edges differ by more than a factor of two, and they differ in the order of the arcs’ lengths. There is no speed the construction cannot exceed. The narrow blur’s run is still on its arc at a stride the wide blur’s could never survive, because the narrow blur’s arc is more than twice as long.

The same curves read along the other axis make the count’s failure as a stride just as plain. At 15 directions the narrow blur’s run strides 2.59 a step and the wide blur’s 2.41 — the same speed to within a few per cent. The first is less than half way along an arc of 32 and has three more safe cutoffs below it; the second is at its edge. A count that gives the same stride on two operators and puts one of them in no danger and the other at the cliff is not telling a code what it needs to know. The count does not even order the danger: at 13 directions the wide blur strides faster than the collection’s blur, 2.05 against 1.90, and the wide blur’s run is two cutoffs from its edge where the collection’s is four.

Turned to a tenth of the noise with the dial, every arc lengthens — to 45.2, 28.1 and 16.9 — and every edge moves right and down. The strides at the new edges are 5.87, 2.50 and 1.96. The rings still do not line up, and they never do at any noise level measured.

So the first half of the proposal fails cleanly. The count is not a stride and cannot be used in place of one, because what is fixed at the edge is not the speed. The previous essay put it as “one stride exceeds the distance that was left”, and the three blurs show that both halves of that sentence vary: the stride with the count and the operator, the distance with the operator and the noise.

What the count does predict #

Read the badge on the figure again. The narrow blur leaves its arc at 33 directions and its answer carries 32.2. The collection’s blur leaves at 22 and its answer carries 23.2. The wide blur leaves at 15 and its answer carries 14.7. At a tenth of the noise the pairs are 44 and 45.2, 29 and 28.1, 16 and 16.9.

Each run leaves the arc at the cutoff where the count of directions divided reaches the dimension of the answer.

Divide each count by its own answer’s dimension and the six curves — three blurs, two noise levels, arcs ranging over a factor of three in length — fall onto one shape. Every one of them keeps most of its run on the arc while the count is below about 0.8 of the answer, falls through a half between 0.95 and 1.03, and is at a quarter or less by 1.15. The wide blur at 1% noise is the untidiest of the six: its reach starts sagging from about 0.6 and falls through a half at 1.02, and on that blur the whole arc is only fifteen dimensions long, so a single iterate is several per cent of it.

The reason is visible once it is stated. A truncated preconditioner multiplies the directions it divides by the reciprocal of their approximate eigenvalue, which makes them all converge at once, in the first few steps; it leaves the rest to conjugate gradients at the unpreconditioned rate. An iterate after the first step or two therefore carries nearly all of the divided directions in full. If there are fewer of them than the answer’s dimension, the run is still inside the arc and continues to climb it. If there are more, the run has admitted directions the answer does not want before it has taken a single step that a stopping rule could stop at, and there is nowhere on the arc for it to land. The edge is where the preconditioner’s own dimension meets the answer’s.

That is also a better statement of what the essay that located the edge found by sweeping errors against the truth: that the smallest cutoff which keeps the floor sits at a third to a half of the Tikhonov oracle’s λ. That sentence is in the units of a singular value, and the singular values of the three blurs fall at different rates, so a fixed fraction of λ was never going to mean a fixed thing across operators. In the units of a count it is one statement on all three.

The rule that was calibrated on one blur #

It matters at once, because a rule for the cutoff already exists and it was stated in λ. The rule that is wrong in the right direction set τ at half the discrepancy principle’s λ — the rule usually criticised for picking λ two or three times too large — and found its cutoff keeping the floor on the median draw with a worst draw of 1.12 over twenty-four, where generalised cross-validation’s worst was two hundred times the floor. The halving was a calibration on the collection’s blur. It was never measured anywhere else.

On the narrow blur it fails. At half the rule’s λ the cutoff divides a median of 36 directions against an answer of 32.6 — past the edge on the typical draw, not only on an unlucky one — and the worst draw’s best error is 1.181 times the floor, with a median of 1.089. At a quarter of λ the worst is 1.83. On the collection’s own blur the halved rule’s worst is 1.121, which is the number the earlier essay reported, and on the wide blur 1.100.

At the rule’s λ itself, unhalved, the worst draw on the narrow blur is 1.058, on the collection’s blur 1.063 and on the wide blur 1.034, with medians of 1.011, 1.007 and 1.001. Doubling λ instead of halving it makes the worst draws 1.024, 1.027 and 1.012. Every step to the right on this axis flattens the curves and brings the three blurs together, and every step to the left spreads them apart, with the narrow blur always the first to go.

The counts say why. On the narrow blur the halved rule divides 36 and the unhalved 32, against an answer of 32.6. On the collection’s blur the counts are 22 and 20 against 23.0; on the wide blur 14 and 13 against 14.8. The halved rule sits at 1.10, 0.96 and 0.95 of the answer’s dimension; the unhalved at 0.98, 0.87 and 0.88. The halving took two of the three blurs to within five per cent of the edge and the third past it.

Why the unhalved rule is safe: the count at λ is a dimension already #

There is a reason the unhalved λ lands just below the edge, and it is almost an identity. The count of the transform’s eigenvalues at or above λ is a step function of λ; the effective dimension of the Tikhonov solution at the same λ, $\sum_k \sigma_k^2/(\sigma_k^2 + \lambda^2)$, is a smoothed version of the same step, weighting each singular value by how far above λ it sits and giving a weight of one half to a singular value equal to λ. Where the transform’s eigenvalues approximate the operator’s singular values — and the approximation is good everywhere except in a handful of directions tied to the boundary rows — the two are the same number.

Measured, they are. Over twenty-four draws at 1% noise the discrepancy principle’s Tikhonov answer carries 31.3, 19.6 and 13.1 of effective dimension on the three blurs, and the cutoff at its λ divides 32, 20 and 13 directions. At a tenth of the noise the pairs are 38.4 and 39, 24.9 and 25, 15.8 and 15. Every pair agrees to within one direction.

So a cutoff at the discrepancy principle’s λ divides as many directions as the discrepancy principle’s own Tikhonov answer carries. And that answer carries fewer dimensions than the best answer does — 31.3 against 32.6, 19.6 against 23.0, 13.1 against 14.8 — for the reason the earlier essay made its title out of: the discrepancy principle picks a λ that is too large, so its Tikhonov answer is slightly over-smoothed. That over-smoothing, in λ, is a handful of directions of margin in the count. Halving λ spends the margin, and on an operator whose singular values fall slowly through the relevant range, as the narrow blur’s do, halving λ adds more directions than the margin held.

This also answers a question the earlier essay could only frame. It asked whether the rule’s success was “about the discrepancy principle or about the direction of the bias”, and proposed testing generalised cross-validation with a deliberate upward factor. The count gives the answer without that test: any rule whose λ puts the Tikhonov answer’s dimension below the best answer’s will keep the floor as a cutoff, because the count at that λ is that dimension, and a count below the answer’s dimension is on the right side of the edge. The direction of the bias is the whole of it. The discrepancy principle has that direction reliably because it stops a residual at the noise level, and a residual reaches the noise level before the error is at its least.

What the halving bought, and what it cost #

The halving was not arbitrary. A smaller cutoff divides more directions and the run is shorter, and on the collection’s blur at 1% noise the halved rule’s median run is best at step 7 against 8.5 for the unhalved one. On the narrow blur it is 5 against 6; on the wide blur 6 against 7. A step saved is two products saved, against the unpreconditioned run’s twelve to nineteen steps.

At a tenth of the noise the halving is worth more and risks less. The steps are 8.5 against 13 on the narrow blur and 12 against 15 on the collection’s — three to four and a half steps saved — while the halved rule’s worst draws are 1.082, 1.039 and 1.021. The unhalved rule’s are 1.035, 1.013 and 1.005. On the wide blur the halving is outright counterproductive: its median run is best at step 10 against the unhalved rule’s 8.5, because dividing seventeen directions of an answer that carries 16.8 puts the first iterate slightly past the top and the run takes extra steps recovering, even though it does recover.

So the trade is stated in the right units. Halving λ adds between one and four directions to the count, which saves one to four steps where the count stays below the answer’s dimension and costs up to eighteen per cent of accuracy where it does not. A code that cannot see the answer’s dimension cannot tell which of those two cases it is in, and the unhalved rule is the one that does not need to.

One draw on the wide blur #

Medians over draws can hide what an individual run does, and on the wide blur the arcs are short enough that a single run’s geometry is legible.

The arc on this draw ends at 12.8. The run dividing 8 directions stays on it at a stride of 1.32 and reaches the same error as the plain run. The run dividing 13 is at the edge — its count is at the arc’s top — and wanders off the arc in the middle before coming back to finish close to it. The run dividing 17 has admitted four directions more than the answer holds before its first useful step, climbs to an effective dimension of 14.8, and ends at 0.1868 against the plain run’s 0.1566: nineteen per cent worse, which is the size of the failure the halved rule produced on the narrow blur, arrived at by the same route.

What this draw also shows is why the stride could never have been the rule. The run past the edge is not particularly fast: its stride is 2.46, not far above the 2.15 of the run dividing thirteen, which ends at the plain run’s error. It fails because of where it starts, not how fast it travels.

What this does not settle #

Three Gaussian blurs of one family on one signal, at two noise levels, with one fast transform. The approximation is good in every direction but a handful, and the agreement between the count at λ and the Tikhonov dimension at λ depends on that. An operator whose fast approximation is poor in many directions — a blur with a varying width, say, approximated by a transform that assumes a constant one — would break the identity the unhalved rule rests on, and nothing here measures how far it can be broken before the rule fails.

The edge is located on a quarter-decade grid of cutoffs, so the count at the edge is known to within the jump between two consecutive cutoffs, which is one to three directions. The six ratios between 0.95 and 1.03 are that grid’s resolution, not a measurement of the edge’s sharpness.

The effective dimension of the best answer is used here to explain the rule and to score it, and a code cannot compute it. The rule itself needs only the transform’s eigenvalues and the discrepancy principle’s λ, which needs a noise level. With the noise level understated the discrepancy principle’s λ falls, the count rises, and the margin that makes the rule safe is spent in the same way the halving spends it; a stopping rule that follows the run it is given measured that cliff for the step count, and not for the cutoff.

Still open: the margin under a misstated noise level, and the count for the shift #

The rule told the noise wrongly. The unhalved cutoff is safe because the discrepancy principle over-smooths, and an understated noise level removes the over-smoothing. How far the noise level can be understated before the count at λ crosses the answer’s dimension, on each blur, is the direct measurement of how much margin the rule actually has, and it can be read off the Tikhonov dimension alone without running a single preconditioned step.

The shifted construction, measured by the same count. A shift $1/(\mu^2 + \alpha)$ divides every direction partially rather than some fully, so it has no count — but it has an effective dimension of its own, $\sum \mu_k^2/(\mu_k^2 + \alpha)$, and the argument here predicts that its runs should sit off the arc whenever that dimension is comparable to the answer’s. The shifted runs measured so far — a preconditioner that arrives past the answer with the exact operator, and the fast approximation since — never reached the floor at any α, and whether that is because their own dimension is always too large at the α that makes them fast, or for some other reason, is the question the count now makes testable.

Whether the arc is the same arc for Tikhonov. Both methods stop at the same effective dimension. Whether the Tikhonov sweep’s whole curve of error against dimension lies on the iteration’s arc, or only meets it at the top, is still unmeasured, and it decides whether “the answer’s dimension” is one number describing the problem or two numbers that happen to coincide at the optimum.