Filter factors — where it appears
Named by 28 essays across 3 fields — each of them below, with the objects they name alongside it.
When the answer is a choice
A backward-stable least-squares solve of this problem returns an answer whose relative error is 5.5·10⁸. Nothing went wrong. The singular values decay exponentially with no gap anywhere in them, the data does not determine the answer, and something outside the data has to choose — which is the computation rather than a preliminary to it.
A parameter that counts steps
The regularisation field's knob is a positive real number chosen by one of three rules. The iterative field's is an integer nobody called a knob — where to stop. On the same problem the best step is 20 and the best λ is 0.025, and they reach 0.1426 and 0.1406.
Four knobs and one floor
A truncation, a Tikhonov parameter, a step count and a randomised rank, on one problem with an answer that is known. Their best errors are 0.1445, 0.1406, 0.1426 and 0.1449 — a spread of 3% across four methods that share no arithmetic.
Where the answer stops being in the data
The Picard condition finds the index where a noisy right-hand side stops carrying signal, from the data alone, with no knowledge of the answer. It lands at 32 where the truncation that actually minimises the error is 28 — and at 45 where the best is 38. It overshoots at every stop from 10% noise to 0.0001%, and it overshoots for a reason. The best truncation walks up the spectrum in a straight line, six or seven indices a decade; the crossing climbs in jumps of 11, 0, 8, 5 and 1.
The basis decides what a filter is
The vocabulary of regularisation is spectral — a method keeps a component or discards it, and the weights are a function of the singular value. Row-normalising a symmetric blur so that it preserves a constant makes it 8.6% asymmetric, and that is enough to move GMRES's weights from 7·10⁻¹⁴ off a function of σ to 4.4·10⁻².
An answer that changes with the seed
A randomised rank-k solve is a truncation computed in a random subspace, and it reaches the same floor as the deterministic ones. What it does not do is return the same answer twice — a factor of 1.84 across four seeds at rank 8, and 1.02 at the rank where the method is best.
A second blur, narrower than the first
A regularised answer is not the truth with the noise taken out. It is the truth seen through a second blur, V F Vᵀ, which depends on the operator and λ and on nothing that was measured. At the best λ for 0.1% noise its rows are 2.82 points wide against the instrument's 5.89, they dip to −0.075 on either side, and their width times the number of components kept stays between 1.10n and 1.27n across seven decades of λ. Two spikes four points apart come back as two; three apart, as one.
An expiry date the noise does not move
The polynomial description of conjugate gradients leaves the level of rounding at step 17 or 18 on this operator, at every noise level from 10% to 0.1%. The step worth stopping at moves from 3 to 44 across the same range. They coincide at about 1% noise, which is where the coincidence was first read, and it is a fact about the noise rather than about the method.
The corner reads the norm it is drawn in
The L-curve was the costliest rule this field scored, and the cost was not the rule's. On the same sixty draws, with the same best achievable error, the corner of ‖x‖ against the residual costs 1.53 times the oracle and the corner of ‖L₁x‖ costs 1.003. Across five signals and three penalties the corner lands wherever amplified noise is between a tenth and a fifth of the norm being plotted, and it finds the oracle only when the oracle happens to sit there — twenty-nine times too costly on a smooth signal under ‖x‖, within half a per cent on four spikes.
A preconditioner that arrives past the answer
On a system that is solved to convergence a preconditioner changes how fast the answer arrives and not what it is. On a problem regularised by stopping it changes where every step lands. Conjugate gradients preconditioned by AᵀA + αI reaches its best answer in one step at α = 10⁻³, and at α = 10⁻⁶ its best answer is its first step, with an error of 1.35 against the unpreconditioned run's 0.1426 — while the count of eigenvalues it has clustered at one rises from 22 to 32.
The grid was the first filter
A continuous deconvolution discretised on n points and solved with no regularisation at all is not unregularised. Its error against the continuous signal is least at 24, 26 and 34 points for noise of 1%, 0.1% and 0.01% per sample — beside best truncations of 24, 28 and 32 components on a 64-point grid — and within 4 to 16 per cent of their error. The grid's own filter factors sum to n exactly and fall through a half at k = n. Choosing the grid was choosing a truncation, before anybody chose a λ.
A step that is not a unit of work
Landweber's iteration reaches conjugate gradients' best answer on the same deconvolution — 0.1414 against 0.1426 — at step 1,778 instead of step 20, and at 0.1% noise at step 56,234 instead of 44. Each step costs the same two products. And within 10% of its best it runs from step 7 to step 6,310, where conjugate gradients runs from 4 to 26: the slow method is the one that forgives a late stop.
Thirty-two coefficients instead of a noise level
The discrepancy principle has to be told the noise, and told too little it does not degrade — it falls off a cliff, at 0.80 of the truth when the noise is 10% and at 0.58 when it is 0.001%, exactly where the understatement forces the filter past its best truncation. The missing number is in the data. The root mean square of the last thirty-two coefficients never sends the rule over the cliff at or below 1% noise in four hundred draws, where eight coefficients with the same median do so thirty-five times.
The method that cannot use a smooth answer
On the collection's own signal four regularisers reach the same floor to a few per cent. Score them instead against answers of increasing smoothness and one stops improving. Across six decades of noise Tikhonov's error falls with a fitted slope of 0.70 whether the answer is twice or four times as smooth, while truncation's rises to 0.94 — and at 10⁻⁶ noise Tikhonov's best is 38 times truncation's.
Restarting is a filter
A restart throws away the Ritz values it does not want and begins again from a new starting vector. Written in the eigenbasis, that vector's components have been multiplied by a polynomial with its roots at the discarded values — measured component by component, and agreeing with the polynomial to rounding.
A better discretisation is a weaker filter
A coarse grid's error has two sources — how well the discrete operator approximates the integral, and how well the grid's function represents the answer — and the grid essay could not separate them. Changed one at a time they separate: integrating the kernel against the hat functions takes a fifth off the 12-point error, reading the answer as a cubic spline takes 15 per cent more, and both roughly double the condition number on every grid. At 0.1% noise the spline discretisation's unregularised solve on 26 points reaches the best truncation of a 64-point grid to 0.3%. At 1% it is worse than the crude grid.
What a cheap preconditioner has to leave alone
A blur approximated by a matrix the cosine transform diagonalises agrees with the operator everywhere but its first and last seven rows. Made invertible by a shift, as the exact preconditioner was, it never reaches the unpreconditioned run's floor — at α = 10⁻³ its best iterate is 0.749 against 0.143. Made invertible by leaving every eigenvalue below τ alone, it reaches 0.141 in five steps instead of twenty, and the smallest τ that keeps the floor sits at a third to a half of the Tikhonov oracle's λ at three noise levels.
Where the grid hands over to λ
An unregularised solve on a coarse grid comes within a tenth of the best Tikhonov answer on a fine one, and the pair of a grid and a λ was left unmeasured. Measured, the two do not trade. On every grid up to the best unregularised one no λ helps at all. On every grid of 40 points and more the best λ is the same to within a quarter of a decade — 3.2·10⁻² at 1% noise per sample, 10⁻³ at 0.01% — and the 96-point grid with it beats the best coarse grid by 7, 9 and 13 per cent. The grids between the two, given their own λ, land between them.
A rule that has to be told how good its answer will be
The L-curve's corner reads a noise share of 0.10 to 0.21 across fifteen pairings of signal and penalty, and the share the best λ sits at runs from 0.0037 to 0.43 — a factor of a hundred and fifteen. A rule aimed at the right share is within a few per cent of the oracle on every one of them. The right share is about a third to four-fifths of the relative error that λ will achieve, which is the number the answer was wanted for.
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 second penalty is not a second parameter
Penalise ‖x‖ and ‖L₁x‖ at once and there are two λ to choose. Over ten draws on five signals the best pair beats the better single penalty by between 0.00% and 3.1%, and one of its two parameters is exactly zero on 30 to 70 per cent of draws. Choosing the wrong one of the two costs up to 54%. The surface is a choice between two curves with a knob nobody needs.
The grid on which the discretisation stops mattering
Without regularisation, integrating the blur's kernel against cubic splines beat sampling it at 0.1% noise and lost to it at 1%. Give each discretisation its own best λ on every grid and the difference shrinks to nothing where grids are fine — 0.17, 0.28 and 0.20 per cent apart on 96 points at the three noise levels, with every discretisation choosing the same λ — and stays at 17 to 18 per cent on 16 points. The choice between them is a choice of how coarse a grid can be: at 0.1% noise the integrated discretisations reach the fine-grid answer on 26 points and the sampled one needs 40.
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 α.
A corner the penalty can afford
Every smooth reading of the deconvolution's grid needed about forty points and then stopped improving, and the step was the suspect. Give the step one coefficient of its own and forty-eight points reach an error of 0.0070 at 0.1% noise, against 0.118 for the best smooth reading on ninety-six — the step was most of the error. But the same step given two coefficients recovers half as well, and given a doubled node at each edge it recovers worse than no breakpoint at all, while representing the signal to 0.07%. What decides is what the penalty is charged for the corner, and whether the data can say where it is.
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 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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Tikhonov regularisationIll-posed problemIterative regularisationSemi-convergenceConjugate gradientsDeconvolutionRegularisationTruncated SVDDiscrepancy principleParameter choiceCondition numberEffective dimension