Regularisation — where it appears
Named by 25 essays across 5 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.
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 valley with no bottom
A degree-nine fit's coefficients can be moved by a third of their own size before the residual changes in the sixth significant figure. The arithmetic did not lose those digits. The data never contained them.
The vertex nobody solves for
A Laplacian is singular, so every solve with one has to remove its kernel first. There are three ways, they agree to fourteen digits, and the one everybody uses carries a free parameter that no account of the method mentions and that moves the condition number by nine hundred.
Choosing without knowing
Three published rules for choosing a regularisation parameter, scored against an oracle that requires the exact answer and is therefore not a method. Generalised cross-validation lands on the oracle's λ exactly; the discrepancy principle costs 6%; the L-curve costs 129%. And told a noise level ten times too small, the discrepancy principle's error goes from 0.112 to 10,449.
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.
Noise that spares the answer and fools the rules
Make each noise sample remember the last one, keep its size fixed, and the best answer available gets slightly better — 0.1056 to 0.1010 — because slow noise hides in the directions where dividing by σ costs nothing. The Picard crossing still lands two dozen indices past the best truncation. What breaks is the rules. Generalised cross-validation more than doubles the best error on 14 draws of 48 instead of 3, the discrepancy principle's typical cost triples, and the two miss in opposite directions. Whitening by the covariance takes GCV back to 3.
The regularisation that legalises every order
Perturb a saddle-point matrix's two blocks in opposite directions and it acquires a factorisation with a diagonal D under every symmetric permutation — not under a good one, under all of them. Five hundred random orderings, five hundred successes, and a growth factor that spans six orders across them.
A ranking that is an eigenvector
PageRank is the stationary vector of a walk that follows links with probability α and jumps at random otherwise. The iteration and the elimination agree to 4·10⁻¹⁷. What α is set to changes which pages come third, fourth and fifth.
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 chain with no stationary vector
A page with no outgoing links loses forty per cent of the walker's probability in six hundred steps. A directed cycle never converges at all. And on a graph whose links only run one way, the entire rank of half the vertices is exactly one minus the teleportation parameter.
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 λ.
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.
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.
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.
The perturbation that does the work
A saddle-point matrix made quasi-definite is perturbed in both blocks, and the laws measured for it moved both together. Moved apart, the laws all belong to one block. The zero block's perturbation γ decides whether every ordering factorises, sets the worst ordering's growth at 0.51/γ, and costs the answer 1,451 per unit — the reciprocal of the smallest eigenvalue of AH⁻¹Aᵀ to three figures. The perturbation of H moves none of the first two and costs 19 per unit. Refinement removes each block's perturbation at the rate its own Schur complement sets, so γ's limit sits fifty times nearer than δ's.
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 repair that costs exactly itself
A ridge on every subproblem is the standard cure for a swamp and it works — the terms stop at 1.61 instead of climbing past 6.7, and a run that never finished finishes in 798 sweeps. On a tensor that does have an answer the error it costs is the ridge itself, to within a factor of two, at every setting from 10⁻¹⁰ to 10⁻¹. And the terms it returns are still the right terms.
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 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.
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 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.
More samples take the floor and leave the dip
GCV's catastrophic misses on fine grids were blamed on squareness: on an n × n system the residual and n − t both reach zero as λ does, and their ratio can dip there. With more samples than unknowns neither reaches zero, and the prediction was that the dip would be gone by construction. Half of it is. The minimum at the floor of the scale, 21 draws in 240 on square systems, is gone at every ratio. The interior dip is not — 28, 20, 13, 8 and 4 draws at one to four samples per unknown — and at four per unknown one draw still misses the oracle by 877 times.
A third penalty on a flat floor
Two penalties at once were worth three per cent at most, and the explanation offered was that one penalty already does the work — which predicts that a third buys less still and that the best choice sits on a face of the parameter cube. The third buys a median of exactly nothing on all five signals and 0.66% on its best draw. But on twelve draws of forty the best triple does use all three, and on every one of them the nearest point with a penalty switched off is within that same 0.66%. The minimum is not on a face; it is on a floor so flat that where it lands is noise. Choosing the right single penalty is worth a factor of two.
Named alongside it
The objects these essays reach for when they reach for this one.
Tikhonov regularisationFilter factorsParameter choiceIll-posed problemDeconvolutionDiscrepancy principleDiscretisationCondition numberGeneralised cross-validationL-curveTruncated SVDNoise floor