Effective dimension — where it appears
Named by 9 essays across 2 fields — each of them below, with the objects they name alongside it.
The parameter neither knob is
A preconditioned run has a cutoff and a step count, and neither is the regularisation parameter. The parameter is the effective dimension of the iterate: every cutoff that works puts its own best at 23.7 to 24.3 of it, where the unpreconditioned run's best sits at 23.2, and what the cutoff buys is the rate — 1.27 of it a step with no preconditioner and 3.53 with one. The edge is where a single stride is longer than the distance left.
A count that marks the edge and not the pace
The number of directions a truncated preconditioner divides is counted for free when it is built, and it was proposed as a stand-in for the stride it buys. On three blurs it is not one — the runs leave the answer at strides of 5.71, 3.44 and 2.41. What the count does predict is the edge: on all three blurs, at two noise levels, a run stops landing on the answer's path within five per cent of the point where the count reaches the answer's own effective dimension. And the halved cutoff rule, measured on one blur, crosses that line on the narrowest.
The shift had an edge, and the approximation moved it
A fast-transform preconditioner made invertible by a shift was recorded as never reaching the unpreconditioned floor, and predicted to sit off the answer's path at every shift. At a large shift it sits on the path and reaches the floor to a tenth of a per cent. It has an edge like the truncated one — but on the exact operator that edge is where the shift's own effective dimension reaches the answer's, 1.02 to 1.05 of it on six problems, and on the fast approximation it arrives at 0.49 to 0.77. The difference is sixteen samples at the ends of the signal, where the approximation is wrong and a shift divides the error by α.
One arc, and what each filter pays to be on it
Conjugate gradients and Tikhonov stop at the same effective dimension, and that could have meant two curves crossing once or one curve. It is one curve over a stretch — on six problems, Tikhonov and truncation reach the iteration's error at the iteration's dimension to within 7.2 per cent from 0.7 of the answer to its top — and the two separate on either side. But the curve is shared by a trade, not by an identical answer: at the same dimension Tikhonov carries 22 to 42 per cent more noise than the iteration and up to five per cent less bias.
The data count their dimensions, not the step's
Every grid in the deconvolution essays was chosen with the answer in hand, and so was every λ. From the data alone, the discrepancy principle's worst draw is within 16 per cent of the oracle on every grid from 16 points to 96; generalised cross-validation is better on the median draw and, on grids of thirty points and more, has draws thousands of times worse. And the data can say how many dimensions they carry — about 20, 25 and 29 at three noise levels, one number once the grid exceeds it — but not how many more the step needs: the grid that count chooses is 14 to 19 per cent worse than forty points at the lower two.
The overshoot was the lead
Past its best, conjugate gradients' error rose more slowly than Tikhonov's at the same effective dimension — on the narrow blur at 0.1% noise Tikhonov was 2.35 times worse at 1.3 of the answer — and the reading was that the iteration spends its dimension where the data has content. Count admitted directions instead of summing factors, so that a factor of 1.81 counts once, and the lead is gone: 0.96 on that problem, and within 0.17 of one on all six from 1.1 to 1.3. Tikhonov now carries less noise than the iteration there. Below half the answer, where the three filters also disagree, the count changes nothing.
The minimum on the right
Generalised cross-validation's worst draws on a fine grid were all one mistake: a second dip in its function at λ near zero, deeper than the real minimum. The proposed repair was a residual threshold, one number, refusing any λ whose residual falls too far below the real minimum's. Measured over 528 draws, a threshold of one half still lets two hundredfold misses through; only the extreme value, which is no threshold at all but the rule 'take the rightmost local minimum', removes all eleven. It costs nothing on the coarse grids where the dip is the right answer, and on the collection's own problem over five thousand draws it turns 243 tenfold misses into 17.
A tail from Tikhonov and a corner from truncation
Below half the answer, conjugate gradients beat Tikhonov at a matched count of directions by up to 69 per cent, and the proposed measurement was the sharpness p of a roll-off between Tikhonov and truncation that matches the iteration there. Any p from 2 to 4 closes the gap to a tenth; truncation, the family's limit, reopens it to a third. But no p describes the iteration. Its filter has Tikhonov's slope exactly in its tail and a local sharpness of 2 to 5 on its shoulder, and a single fitted p is a compromise that drifts from 2.3 at the first step to 1.7 at the answer.
The first step's filter, kept for the whole run
Conjugate gradients' first step applies a ramp — Tikhonov's slope up to a corner, then one — and the essay that found it proposed the ramp as a fixed method, predicting that it would match the iteration below half the answer better than any sharpened Tikhonov and lose the match near the answer. The first half holds by more than predicted: 0.044 from the iteration below half, where the best member of the family was 0.106. The second does not: near the answer the ramp is within 0.016, closer than any filter measured. And two numbers read off the iteration's own Ritz values — its tail's slope and its smallest Ritz value — reproduce it past the top as well, where every fixed filter falls ten to seventeen per cent below it.
Named alongside it
The objects these essays reach for when they reach for this one.
Tikhonov regularisationConjugate gradientsDeconvolutionFilter factorsIterative regularisationSemi-convergenceTruncated SVDCirculant preconditionerDiscrepancy principleParameter choicePreconditioningRitz values