Thirty-two coefficients instead of a noise level

Choosing without knowing put the discrepancy principle beside two rules that are told nothing and found it the most predictable of the three: within 6% of the oracle at every noise level drawn, never the best and never far from it. It also found the objection to it, and measured it. The principle must be told the noise norm ‖e‖, and told a tenth of the truth it returned an error of 10,449 where told the truth it returned 0.112.

That measurement was taken at two points, a tenth and ten times, on one draw. It says the rule is fragile in one direction and not in the other. It does not say where the fragility begins, and that is the number anybody who has to supply ‖e‖ needs, because nobody supplies it exactly. A noise level is an instrument specification, a variance from repeated measurement or an estimate from the data, and every one of those is wrong by some amount. The question worth answering is how wrong it may be.

Too little noise is not a small mistake #

The curve has two sides and they are not two degrees of one behaviour.

On the right, the principle is told more noise than there is. It looks for the largest λ whose residual stays under a target that is too generous, finds a larger λ than it should, and over-smooths. The answer is blurrier than necessary and the error rises slowly: 1.13 times the oracle when told half as much again, 1.17 at twice, 1.22 at three times, with the worst of the four hundred draws at 1.31.

On the left, the principle is told less noise than there is, and for a while almost nothing happens. At nine tenths of the truth the median cost is 1.04, slightly better than being told the truth, because the principle left to itself leans slightly towards over-smoothing and a small understatement offsets it. At seven tenths the median is 1.20 — and the 90th percentile is 13.5 and the worst draw is 5,560. At a half the median is 3,200. At a third it is 81,000.

The cliff drawn on the figure is defined per draw and then summarised: for each draw, the largest understatement at which the error is already twice the oracle’s, read on a grid of half a hundredth in ρ. Its median over the four hundred draws is 0.685, and the middle eighty per cent of draws put it between 0.60 and 0.76. So at 0.1% noise a noise level that is right to within a quarter is safe on nearly every draw, and one that is a third too small is a coin toss between a small cost and an enormous one.

That shape is the one the earlier essay’s asymmetry predicted, and the thing it adds is a location. A rule of thumb that says “overstate when in doubt” is correct and does not say by how much caution the error is bought. The figure does: understatement is free to about 0.8 and ruinous below 0.6, and overstatement costs a fifth at a factor of three.

An understatement forces the filter to keep more #

The cliff has a mechanism, and the mechanism puts a number on it that the figure only reads off.

A Tikhonov solution keeps, roughly, the components whose singular value is above λ and discards the rest. Its residual is what it discards. Past the index where the data stops carrying signal, each discarded coefficient uₖᵀb is noise, and noise spread evenly over sixty-four directions puts about ‖e‖²/64 into each. So a filter that keeps p components and discards n − p of pure noise has a residual of about ‖e‖·√((n − p)/n).

The principle is told ρ‖e‖ and has to find a residual that small. Once ρ is small enough that the noise in the discarded components is what the residual consists of, the only way to reach the target is to discard fewer of them:

n − p ≈ ρ²·n,   so   p ≈ (1 − ρ²)·n

Told 0.685 of the truth on sixty-four points, that is p ≈ 34 components kept.

It is checked rather than trusted. The effective number of components a Tikhonov filter keeps is the sum of its filter factors Σfₖ, and at each draw’s cliff it can be read off directly. The median over four hundred draws at 0.1% noise is 33.3, against (1 − ρ²)·n of 34.0. At 10% noise the two are 21.8 and 22.5; at 0.001% they are 42.3 and 42.8. The arithmetic describes the cliff to within a component at all three.

The cliff moves, and it moves the wrong way for caution #

Measured at five noise levels, four hundred draws each:

The louder the noise, the closer the cliff comes to the truth. At 10% noise a noise level understated by a fifth doubles the median error. At 0.001% an understatement by two fifths does not.

The reason is in the last three columns. A loud problem has few components worth keeping — the best truncation is 13 at 10% noise — so the principle, forced to keep (1 − ρ²)·n, runs past them after a small understatement. A quiet problem has thirty-eight worth keeping, and the principle can be forced to keep forty-two before any of the extra ones is mostly noise.

That is the uncomfortable direction. The problems on which the noise level is hardest to know are the noisy ones, where it is a large part of the data and the data is least able to say how much of it is signal; and those are the problems on which the principle tolerates the least error in being told.

Between the boundary of use and the boundary of information #

Where the answer stops being in the data found two indices on this problem and argued that they are different things. The best truncation is where the components stop being worth keeping; the Picard crossing, later, is where they stop carrying any signal at all. Between them sit components that carry some signal and more error than they are worth.

The cliff lands in that interval. At every noise level in the table, the number of components the principle is forced to keep at its cliff lies above the median best truncation and below the median crossing, and it does so draw by draw as well as at the median — on 361 of the 400 draws at 0.1%, and on no fewer than 327 at any level.

That gives the cliff a reading that is more useful than its number. The discrepancy principle fails when an understatement pushes it past the boundary of usefulness by five or six components — not all the way to the boundary of information, where the components are pure noise, but into the band where the last few carry more error than signal. Measured at 0.1% noise, told 0.79 of the truth the principle keeps 27 components and the median draw costs nothing; told 0.71 it keeps 30 and costs a fifth; told 0.51 it keeps 47 and costs three thousand times the oracle. Each extra component is a coefficient of noise divided by a σ between 10⁻³ and 10⁻⁵.

So the principle does not need to be told the noise to a digit, and it does not survive being told a figure that is only right in order of magnitude. It needs to be told a number that keeps (1 − ρ²)·n short of the best truncation plus a handful, and the size of the handful is a property of the problem.

What the data holds about its own noise #

The noise level has to come from somewhere, and on this problem the data itself holds a measurement of it — in the same coefficients the Picard picture is drawn from.

Past the crossing, a coefficient uₖᵀb is almost entirely uₖᵀe, and uₖ is a unit vector, so uₖᵀe is the noise measured along one direction. With the noise spread evenly each has variance ‖e‖²/n. A set of m such coefficients is therefore a sample of m draws from a distribution whose spread is the thing the principle needs, and two textbook estimates of that spread are available:

• the root mean square, √(Σ(uₖᵀb)²/m), times √n; and
• the median absolute value divided by 0.6745, the constant that makes it an estimate of a normal distribution’s standard deviation, times √n.

The second is the one statistics recommends when a sample might be contaminated, because one stray large value moves a median not at all. Here contamination has an obvious source — a coefficient near the crossing that still carries signal — so the recommendation looks apt.

Which coefficients to use is the other choice. The last m, for some fixed m, trusts that the end of the spectrum is noise. Everything past the Picard crossing trusts the crossing to say where the noise begins, which is what it was designed to find.

That makes six estimators from two choices, and each can be scored twice: by how close its estimate is to the true ‖e‖, and by what the principle does when handed the estimate instead of the truth.

Six estimates with the same centre #

At 0.1% noise, four hundred draws:

Every estimator is right on average. Six medians between 0.98 and 1.07 of the truth: none of them is biased enough to notice, and a comparison of estimators by their typical error would call them equivalent.

What separates them is the first percentile, because the cliff reads nothing else. The principle tolerates overstatement and punishes understatement past 0.685, so an estimator’s value to it is set by how far below the truth its low draws go. Eight coefficients reach 0.48 on one draw in a hundred and send the principle over on thirty-five. Thirty-two reach 0.77 and send it over on none, at a median cost of 1.068 against 1.063 for being told the truth — indistinguishable.

The dependence on m is the one sampling theory predicts. The root mean square of m normal samples has a relative spread of about 1/√(2m): a quarter for eight, an eighth for thirty-two. Quadrupling the sample halves the spread, and halving the spread moves the lower tail from below the cliff to above it.

That is the refusal this essay publishes, and it is worth stating plainly because the tempting check passes. An estimate that is unbiased to two figures is not therefore safe. The principle does not average its errors over draws; it takes each draw’s estimate at face value, and one draw in eleven with eight coefficients is a draw that costs between two and thirty-three thousand times the error the rule should have returned.

The loud end is where the margin runs out #

The estimates are nearly the same at every noise level: the last thirty-two coefficients are noise whether the noise is 10% or 0.01%, so their spread does not change. The cliff does, and the table of failures follows the cliff rather than the estimates:

Read across a row and the ordering is the same at every level. Read down a column and every estimator fails most often where the noise is largest. The four draws on which thirty-two coefficients fail at 10% might be expected to be its four lowest estimates, and they are not quite that. Two of them had estimates of 0.69 and 0.78 of the truth; the other two had 0.82 and 0.83, on draws whose own cliff sat high — the cliff is a distribution too, and at 10% its upper tenth is above 0.86, so an estimate that is safe at the median cliff is not safe on every draw. The worst of the four costs 4.5 times the oracle, a failure by the cliff’s definition and a mild one beside the other estimators, whose worst draws at the same noise run from hundreds to millions.

So “thirty-two coefficients are enough” is a statement with a range. On this problem it holds without exception from 1% noise down; at 10% it holds on ninety-nine draws in a hundred.

Why the robust estimate loses #

The median of the same thirty-two coefficients sends the principle over on thirty-three draws at 10% where the root mean square sends it over on four. It has the same data and a worse answer, and the reason is the price of its robustness.

For normal samples the median absolute deviation is a much less efficient estimate of spread than the root mean square: it needs roughly two and three quarter times as many samples to reach the same precision. The price buys immunity to a few large values. Here the price is paid and the immunity buys nothing, because the contamination it guards against points the safe way — a stray signal coefficient is larger than the noise, pushes an estimate up, and makes the principle over-smooth, which costs a few per cent. What the principle cannot afford is an estimate that comes out low, and a less efficient estimator comes out low more often.

That is a general reading worth keeping. Robustness is protection against one kind of error, and its value depends on which kind of error the consumer of the estimate can survive. The discrepancy principle survives high estimates and does not survive low ones, so the estimator it wants is the efficient one, biased upward if anything — which a robust median of a set that includes a little signal happens not to be, since its extra spread reaches down as well as up.

Reading the crossing first makes it worse #

The two estimators that start from the Picard crossing fail more often than any fixed tail of sixteen or more coefficients at every noise level, and about as often as a tail of eight. They were the natural ones to write: find where the noise begins, then measure it.

The trouble is the same trouble the Picard essay found in a different form. Across draws the crossing wanders — the gap between it and the best truncation ran from −2 to 42 indices over twenty-four seeds — and a crossing that lands late leaves only a handful of coefficients past it. At 0.1% noise the median draw has sixteen coefficients past its crossing and one draw in ten has four; 113 of the 400 have eight or fewer, and those draws account for 37 of the estimator’s 44 failures. On them the estimate is the root mean square of a few numbers, its spread is a third or more, and its low tail reaches 0.31. Using a detector to decide which samples to trust has made the detector’s variance part of the estimate’s.

A fixed tail has no such failure. The last thirty-two coefficients are noise at every level from 10% down to 0.01% because this blur’s singular values have fallen to 10⁻³ by index 32 and to 10⁻⁷ by index 48, and that is a property of the operator, known before any data is collected.

Caution bought by a factor instead of by coefficients #

The standing advice from the essay that measured the asymmetry was to overstate the noise when in doubt. With an estimate in hand, that advice has a price that can be computed. Multiplying every estimate by a safety factor before handing it to the principle, at 0.1% noise:

A factor of 1.5 rescues eight coefficients almost completely and costs 7% on the median draw. It does not rescue the crossing-based estimate — eleven failures remain, because its lowest estimates are a third of the truth and a factor of one and a half does not reach — and it charges the thirty-two coefficient estimate the same 7% for protection it did not need.

So caution and sample size are two ways to buy the same thing and they are not interchangeable. A safety factor pays on every draw to insure the few; more coefficients narrow the distribution and pay nothing on the typical draw. Where the coefficients exist, they are the cheaper insurance.

Where thirty-two stops being the right number #

Four things bound this, and none of them is measured here.

At the quiet end the tail carries signal. At 0.001% noise the Picard crossing is at 52 and the last thirty-two coefficients start at index 32, so a dozen of them carry signal. The estimate leans high — a median of 1.10 of the truth rather than 1.00 — and the principle, over-smoothing slightly, costs 1.043 against 1.041 for being told the truth. It is harmless here because it errs in the forgiving direction, and it is the reason “thirty-two” is a number about this operator rather than a rule.

The coefficients need the decomposition. uₖᵀb is available because the problem is small enough for a full singular value decomposition. A problem too large to decompose has to find its noise level some other way, and a parameter chosen on a smaller problem is the site’s closest approach: inside a Krylov method the discrepancy principle transfers exactly, and nothing there says where an estimate of ‖e‖ would come from.

The operator decides how many noise-only coefficients there are. This blur’s singular values fall exponentially, from 10⁻³ at index 32 to 10⁻⁷ at index 48, so half its spectrum sits below any noise floor measured here. An operator whose singular values decay slowly leaves fewer coefficients that are purely noise, the sample shrinks, and by the arithmetic above the lower tail widens towards the cliff. How fast is not measured.

And white noise is assumed everywhere. Each noise-only coefficient has variance ‖e‖²/n only if the noise is spread evenly over directions. Correlated noise concentrates in some and avoids others, the floor tilts, and both the estimate and the principle’s own target ‖e‖ stop meaning what they mean here.

The site’s standing caution about samples applies to the counts themselves. Zero failures in four hundred draws bounds the failure rate, it does not make it zero; the tail a sample never reaches is the measured reminder that a running worst case can only get worse as draws are added. What four hundred draws do settle is the comparison: an estimator that fails thirty-five times and one that fails none are not the same estimator.

What the principle was being asked for #

It is worth saying what has changed, because the rule itself has not.

The discrepancy principle was presented as the rule that needs something the data does not contain, and that was the standard criticism of it. On this problem the data does contain it, in the part of the spectrum that carries no signal, and the principle handed thirty-two of those numbers is as good as the principle handed the truth — 1.068 against 1.063 on the median draw, and no draw between 1% and 0.001% noise on which it fails.

What the criticism should have been is narrower and more useful. The principle needs a noise level whose lower tail stays above a cliff at (1 − ρ²)·n components, and that cliff sits closest to the truth on exactly the problems where the noise is largest. A noise level from an instrument specification carries no distribution at all, so its tail is unknown; a noise level from the data carries one that can be measured, which is the one advantage over it that matters.

This is the same shape as a small residual is not a small error, one level up. There a quantity that looks like accuracy was not; here a quantity that looks like reliability — an unbiased estimate — was not, and the thing that decided it was a distribution’s edge rather than its centre. Four knobs and one floor showed that the rules and methods of this field all reach nearly the same best error, and it is exactly because the floor is shared that the tails are where the rules differ.

Where this goes from here #

The other rules’ tails. This essay measured one rule’s input over four hundred draws. The two rules that are told nothing were scored in the earlier essay over sixteen, and the question that transfers directly is whether their worst draws look like the principle’s cliff or like something else. One draw in twenty takes that to a thousand draws per noise level and adds the two rules the first essay named and did not measure.

The same choice under a different penalty. Everything here penalises ‖x‖. The principle reads only a residual, so a derivative penalty should leave its cliff where it is; the rules that read the solution have no such guarantee. The corner reads the norm it is drawn in measures the rules on the general form.

An estimate of the noise without a decomposition. The projected problem inside a Krylov method has its own coefficients, and the transfer identity for the residual suggests that its trailing ones might carry the noise too. Whether they do, and how many there are at the step where the parameter is chosen, is the next measurement this essay leaves open.

And coloured noise, where the premise of every estimator above — equal variance in every direction — is false by construction, and a whitening transformation has to come before any of this can be done.