One arc, and what each filter pays to be on it

The parameter neither knob is found two optima landing in the same place. The Tikhonov parameter λ that minimises the error on the collection’s deconvolution gives a solution whose filter factors sum to 22.40; the step at which conjugate gradients is best gives an iterate whose implied filter factors sum to 23.17. At a tenth of the noise the two are 27.97 and 28.09. Nothing arranged that — one optimum is found over a continuum of filters and the other over a sequence of Krylov spaces — and the essay read it as saying that the regularisation parameter of the field is neither λ nor k but the effective dimension both of them are ways of reaching.

It left a question the coincidence could not answer, and stated it as two predictions that differ everywhere except at the point where the measurement was taken. Either the Tikhonov sweep’s whole curve of error against effective dimension lies on the arc the iteration climbs, in which case effective dimension is a coordinate in which the two methods are one method; or the two curves merely cross at the top, in which case the coincidence is about optima and says nothing about the solutions on the way there. Separating them takes the error at matched dimension along both curves, which is one sweep. It turns out to need a second quantity as well, and the second quantity is the more interesting of the two.

Three curves on one pair of axes #

Truncated SVD belongs in the comparison because its effective dimension is its parameter — the number of components it keeps — so it is the one filter whose position on the axis nobody has to compute.

On the collection’s blur at 1% noise, on one draw, the iteration is best at step 20, carrying 24.0 of effective dimension, at an error of 0.1426. Tikhonov’s best carries 23.2 at 0.1405; the best truncation keeps 21 components at 0.1445. Over twelve draws on each of six problems — Gaussian blurs 1.5, 2.5 and 4 grid points wide, at 1% and at 0.1% noise — the three bests are within four per cent of each other in every median, and Tikhonov’s best sits at 0.95 to 0.98 of the iteration’s dimension.

The picture says more than the bests. From about 15 of effective dimension up to the iteration’s best at 24, the three curves lie on top of each other closely enough that the iteration’s dots sit on Tikhonov’s line. Below 12 they part: Tikhonov’s curve runs above the others, and the truncation’s staircase wanders either side of the iteration’s. Past the top all three rise steeply, and the iteration — drawn only as far as its dimension keeps rising, since past its best the filter factors it implies begin to swing negative — rises more slowly than either.

Turned to the narrow blur with the dial, the shared stretch moves right with the answer, which now sits at 33, and runs from about 27 to 36; below 25 Tikhonov’s curve lifts well clear of the other two. On the wide blur it is short, and the three bests are 0.1566, 0.1571 and 0.1551.

One curve over a stretch, and only over a stretch #

A single draw is suggestive. The measurement is the error ratio at matched dimension: take each conjugate-gradients iterate, compute the sum of the filter factors it implies, find the λ at which Tikhonov’s filter sums to the same number and the truncation that keeps that many components, and divide their errors by the iterate’s. Do it at each fraction of the answer’s own dimension from 0.3 to 1.3, over twelve draws, on all six problems.

Between 0.7 and 1.0 of the answer, every ratio on every problem is within 7.2 per cent of one. That is not a statement about medians hiding a spread: it is the whole band, six problems wide, pinched to less than a tenth. On the collection’s blur at 1% noise the Tikhonov ratios through that stretch are 1.002, 0.977, 0.956 and 1.020, and the truncation’s 1.010, 1.024, 1.038 and 1.072.

Outside it the band opens on both sides. At 0.3 of the answer Tikhonov’s ratio runs from 1.03 to 1.68 across the six problems, the high end on the narrow blur, where at half the answer’s dimension it is still 1.37. At 1.3 it runs from 1.01 to 2.35, and the truncation’s from 0.98 to 2.63.

So the first prediction is right over a stretch and the second is right outside it. The curves are one curve from 0.7 of the answer to its top — which is exactly the stretch in which a parameter choice is made, since no rule worth using stops at half the answer’s dimension — and two or three curves everywhere else. This is why the optima coincide, and it is also why the coincidence does not extend to a statement that the methods are the same.

The error has two parts, and they do not agree #

The error of any filtered solution in this problem can be split exactly, direction by direction in the operator’s singular basis. Each direction k carries some fraction $f_k$ of its data coefficient; if the data were exact, that would leave the error $(f_k - 1)\xi_k$ in that direction, where $\xi_k$ is the true signal’s coordinate — the bias, the price of what the filter throws away. The rest of the error in that direction, the solution’s coordinate minus $f_k \xi_k$, comes from the noise. A second blur, narrower than the first drew the first part as a resolution kernel; the second is what the filter lets through.

At the answer’s dimension Tikhonov’s noise part is 1.22 to 1.42 times the iteration’s on the six problems, and its bias part is 0.951 to 0.998 times. Across 0.9 to 1.1 of the answer the noise ratio exceeds 1.05 on every problem at every fraction measured. The one exception anywhere in the band from 0.6 is the wide blur at a tenth of the noise at 0.8 of the answer, where Tikhonov’s noise is 0.83 of the iteration’s — a problem whose noise part there is a few thousandths of the signal’s size, so small that the ratio of two such numbers is loose.

So the errors agree near the top because Tikhonov buys a little less bias with a lot more noise, and near the top the bias is the larger part — on the collection’s blur at 1% noise the iteration’s error at its best is 0.1426, of which the bias part is 0.1254 and the noise part 0.0648. A 30 per cent difference in the smaller part, set against a 5 per cent difference in the larger, nets out to under one per cent. The arc is shared the way two portfolios with the same return and different holdings share a line on a chart.

Past the top the balance reverses — the noise becomes the larger part — and so the noise difference shows directly in the error, which is the band opening above one. Below 0.6 the noise is negligible for every method and the difference is in the bias, which depends on the shape of each filter’s transition and not only on where it sits.

Where the dimension goes #

The split says what differs. The filter factors themselves say why.

At 23.95 of effective dimension the three filters have spent the same total and spent it differently. The truncation keeps the first 24 directions entirely and nothing after. Tikhonov keeps the first twenty almost entirely and then rolls off smoothly, admitting a tail of partial weights through direction 30 and beyond. Conjugate gradients rolls off at about the same place but more steeply, with almost no tail — and before it does, it overshoots: its factors on directions 18, 20 and 21 are above one, reaching 1.21.

The overshoot is conjugate gradients’ filter polynomial doing what an expiry date the noise does not move measured it doing, and here it has a consequence. A factor of 1.21 on a direction contributes 1.21 to the effective dimension, 0.21 more than keeping that direction exactly. The sum does not distinguish between admitting a new direction and over-weighting one already admitted. So of the 23.95 the iteration carries, a part is spent amplifying directions that carry signal, where the other two filters must spend that part admitting a tail of directions that carry mostly noise. The noise part of the error follows: 0.0648 for the iteration, 0.0740 for Tikhonov, 0.0744 for the truncation.

At 1.2 times the answer the effect is large. The iteration at step 32 carries 28.72, and its factors on directions 23 to 26 run up to 1.81 — directions that still carry signal on this draw, since the exact data’s coefficient stays above the noise’s through direction 28. Tikhonov at the same dimension admits directions out past 33 at partial weight. The noise parts are 0.2017 for the iteration, 0.3213 for Tikhonov and 0.3551 for the truncation, and the whole errors 0.2207, 0.3347 and 0.3698. The iteration’s error past its best rises more slowly than the others’ at matched dimension, and this is the reason: its dimension is not all new directions.

The accounting can be made exact. On this draw, of the iteration’s 28.72, the excess of its factors above one sums to 1.66 — nearly two whole directions’ worth of dimension spent on over-weighting — and its factors on directions past the true crossing at 28 sum to 0.28. Tikhonov at the same dimension puts 1.30 past the crossing and the truncation 1.00: four to five times as much weight on directions whose data is mostly noise. At the answer’s own dimension the same three sums are 0.02, 0.07 and 0.00, and the overshoot is 0.53. The difference in noise at the top is small because there is almost nothing past the crossing for any filter to spend on; the difference past the top is large because there is, and only one of the three has somewhere else to put the dimension.

The reason the iteration can do this is the one that distinguishes it from the other two. Tikhonov and truncation are fixed functions of the singular values: they would apply the same factors to any data. Conjugate gradients builds its polynomial from the data’s own residuals, so its factors are larger where the data has content and smaller where it does not. Of the three filters it is the only one that reads the right-hand side, and at a matched dimension what it reads is where to put the dimension.

Six problems at the answer’s dimension #

The one-draw filters show the mechanism; the six problems show how general it is, at the one dimension that matters most — the dimension the iteration’s best iterate carries.

Tikhonov’s noise part at the answer’s dimension is 1.26, 1.38 and 1.42 times the iteration’s on the narrow, middle and wide blurs at 1% noise, and 1.29, 1.22 and 1.39 at 0.1%. On not one of the six is it below 1.2. Its whole error is 1.002 to 1.046 times the iteration’s. The truncation is less consistent: its noise part runs from 0.90 to 1.20 of the iteration’s, below one on three problems, because a truncation’s noise is all or nothing per direction and whether the last kept direction is a clean one or a noisy one depends on the draw. What does not vary is the order of the whole errors: all twelve open circles sit within 7.2 per cent of one.

The consistency of the Tikhonov figure is the useful part. A smooth filter that admits a tail of partial weights must pay for the tail in noise, and it does so on every blur and at both noise levels by a fifth to two-fifths. The iteration pays nothing for a tail it does not have, and pays instead with a small excess of bias, the price of rolling off more steeply — 0.1254 against Tikhonov’s 0.1192 on the draw drawn above.

That is a trade a user could choose between if the two answers were for different purposes. A solution that will be differentiated, or whose small-scale structure will be read as signal, is hurt more by noise than by bias, and at the same dimension and the same total error the iteration’s is the better one to hand over. A solution that will be integrated or averaged is hurt more by bias, and Tikhonov’s is. Nothing in the effective dimension, and nothing in the error, distinguishes the two cases; the split does.

What the dimension is a coordinate for #

That settles the question in a form more useful than either prediction. Effective dimension is the right coordinate for where a method should stop — near the top of the arc every method’s error is a function of it alone, to a few per cent, which is why the method that cannot use a smooth answer found four regularisers reaching one floor and why the preconditioned runs of the count measurements could be judged by it. It is not a coordinate for what a method returns. Two solutions at one dimension differ in how they split their error, by twenty to forty per cent in the noise part near the top and by far more on either side.

Two practical consequences follow. A parameter rule tuned to one method transfers to another if it is stated as a dimension and lands between 0.7 and 1.0 of the answer; the count essay’s unhalved cutoff lands at 0.86 to 0.99 of it, inside that stretch, which is part of why it survived a change of operator. And a rule that errs past the top errs less on the iteration than on Tikhonov or truncation — at 1.2 of the answer the iteration’s error is 0.66 of Tikhonov’s on this draw — so a rule that stops late is cheaper on conjugate gradients than the same rule’s λ would be, measured at the same dimension.

The second consequence is a small correction to how the Picard reading relates to any of this. The Picard reading looks for where the data’s coefficients sink into the noise, and on the draw above the true crossing — the last direction whose exact coefficient exceeds the noise’s — is 28. The effective dimension of the best solution sits below it, at 24, because every filter keeps some bias to avoid the noise in the last few signal directions. The iteration reaches furthest toward the Picard index at the least noise cost, by overshooting where it can and admitting almost no tail.

What this does not settle #

Three filters, one signal, three blurs of one family, two noise levels, twelve draws. The signal’s coefficients decay in one particular way and the split between bias and noise is a property of that decay as much as of the filters; a signal whose coordinates fall more slowly would put more of the error in the bias near the top and less in the noise.

The matching uses the conjugate-gradients iterate nearest each target fraction, so the fractions are approximate at low dimension, where the iteration takes large strides — at 0.3 and 0.4 of the answer several problems match to the same iterate. The bands there are coarser than the axis suggests.

The bias–noise split is exact for any solution because it is computed from coordinates, but “noise part” means the part of the error that would vanish with exact data at the same filter factors, and for the iteration the filter factors themselves depend on the noise. The split describes the iterate that exists, not the one the iteration would have built from clean data.

Still open: a dimension that counts directions, and the overshoot as a choice #

A dimension that does not count overshoot. The effective dimension adds 0.81 for a factor of 1.81. A count of directions admitted — say, the sum of $\min(f_k, 1)$, or the number of factors above one half — would read the iteration as having admitted fewer directions than Tikhonov at the same effective dimension. Whether the three curves line up better in that coordinate, over the whole range and not only near the top, is one recomputation of the sweep above.

Tikhonov with the data’s shape. The iteration’s advantage past the top comes from placing its factors where the data has content. A Tikhonov filter weighted by the data — a penalty that falls where the coefficients are large — would carry the same information, at the price of a second thing to choose, which is the price a second penalty is not a second parameter found not worth paying for a second smoothness penalty. Whether it matches the iteration’s noise part at matched dimension would say whether reading the data is the whole of the difference.

The same comparison on a preconditioned run. Every iteration here is unpreconditioned. A truncated preconditioner clusters the divided directions near one, which changes the polynomial’s freedom to overshoot, and the stride measurements say the preconditioned run lies on this arc near the top. Whether it keeps the iteration’s lower noise at matched dimension, or trades it for speed, is the question that would say what a preconditioner costs beyond the products it saves.