The data count their dimensions, not the step's

Every measurement in the grid essays was made with the answer in hand. The grid was the first filter chose the best grid by comparing each grid’s error against the continuous signal. Where the grid hands over to λ chose the best λ on each grid the same way, and found it to be one number on every grid of forty points and more. The grid on which the discretisation stops mattering chose among discretisations with the same oracle. None of that is available to anybody with an instrument, and two questions were left for the data.

The first is whether the λ rules that choosing without knowing scored on one 64-point problem behave the same way on every grid, or whether a rule’s cost against the oracle grows or shrinks as the grid is refined. The second is harder: whether anything computed from the data can say which grid is enough. The grid essays found forty points to be the grid past which nothing improves at the lowest noise level, and a corner the penalty can afford found that most of what those forty points buy is the step in the signal. Whether the data can see that is the test of whether a grid is a parameter a user can choose or one that has to come from somewhere else.

Three rules on eleven grids #

The measurement is simple to state. On grids of 16 to 96 points, at 1%, 0.1% and 0.01% noise per sample, over sixteen seeded draws, solve Tikhonov at 121 values of λ fifteen to a decade, find the λ that is best against the continuous signal on that draw — the oracle — and score each rule’s choice as its error over the oracle’s.

The discrepancy principle — choose the largest λ whose residual is no bigger than the noise — is the steady one. At 0.1% noise its worst draw on any of the eleven grids is 1.133 times the oracle; at 1% it is 1.159; at 0.01%, 1.087. Its median sits between 1.00 and 1.09 on every grid at every level. Refining the grid does not make it better or worse in any direction a figure can show.

Generalised cross-validation is better on the median draw — 1.00 to 1.04 on every grid — and on grids of thirty points and more its worst draw leaves the frame. At 0.1% noise the worst of sixteen draws on the 48-point grid is 2,944 times the oracle, and on the 64-point grid 40,046 times. At 1% the worst anywhere is 25,680 times; at 0.01%, 4,209. On the 96-point grid at 0.1% it is back to 1.09. The L-curve is not a rule on this problem at all: its median runs from 1.28 to 3.84 at 0.1% noise and is never below 1.18 at any level on any grid.

So the first question has a clean answer for two rules and a complicated one for the third. The discrepancy principle’s cost does not depend on the grid. The L-curve’s does not matter because it is always large. GCV’s typical cost does not depend on the grid and its tail depends on it completely — which is the one property a user choosing a grid would most need to know and the one a median hides.

Where GCV’s tail lives #

Counting the draws on which GCV is more than twice the oracle, grid by grid, places the failures precisely.

There are none on any grid of 28 points or fewer, at any noise level. There are fifteen in all at 1% noise, ten at 0.1% and eight at 0.01%, every one of them on a grid of 30 points or more — six of sixteen draws on the 40-point grid at 0.1%. The discrepancy principle has none on any grid at any level, which is the same shape noise that spares the answer and fools the rules found with correlated noise on a fixed grid: the two rules miss in opposite directions, and GCV’s misses are the large ones.

The reason is in GCV’s own function of λ. GCV minimises the residual squared over $(n - t)^2$, where t is the trace of the influence matrix — the effective dimension of the solution — and n the number of data. On these problems the system is square, so as λ falls toward zero the solution fits the data ever more exactly: the residual falls, and so does n − t, the count of directions the solution leaves unfitted. Over the last few decades of λ the two fall together, and whether their ratio rises or dips there depends on how many of the grid’s singular values lie in those decades.

On the 24-point grid the smallest singular value is 0.034 of the largest, the unregularised solve is well-behaved, and every draw’s GCV function falls toward small λ and stays low. That minimum at λ near zero is the right one: the grid is its own filter, as the grid was the first filter measured, and the oracle’s λ on this grid is the smallest on the scale, ten to the minus eight, on every draw.

On the 48-point grid the smallest singular value is $9.6 \times 10^{-8}$ of the largest, and the same limit is now a trap. Most draws’ GCV functions have their minimum near λ = $10^{-2.3}$, where the oracle’s is, and rise steeply either side. On two of the eight drawn, the function also dips at λ below $10^{-6}$, where the grid’s smallest singular values are, and the dip is deeper: GCV picks $10^{-6.67}$ on one and $10^{-8}$ on the other, and the answers there are 147 and 365 in relative error against an oracle of 0.12. The degenerate minimum that was right on the coarse grid is still there on the fine one, and whether it beats the real minimum is a matter of the draw.

Over all three noise levels, eleven draws miss by more than a hundred times, and every one of them is at λ of $10^{-6.67}$ or below — the degenerate dip. The other twenty-two misses are milder, two to fifty-four times, and are the same shape at smaller amplitude: a λ one to four decades below the oracle’s, chosen from a dip that is shallow rather than deep. That is why the tail depends on the grid and the median does not. Coarse grids have no real minimum to lose, fine grids have one that usually wins, and the grids in between have both.

What each rule’s λ is #

The λ each rule picks shows the same structure from the other side.

On grids of 40 points and more the oracle’s λ lies between $10^{-2.47}$ and $10^{-2.33}$ at 0.1% noise, which is the grid essay’s finding that the best λ on fine grids is one number, confirmed per draw. GCV’s median λ follows the oracle’s closely there, which is why its median error is so good. The discrepancy principle’s sits between $10^{-2.0}$ and $10^{-1.8}$ — 0.4 to 0.6 of a decade above the oracle’s on every fine grid — the habitual overshoot the rule that is wrong in the right direction found and turned into a virtue. Here the overshoot costs three to nine per cent on the median draw and buys a worst draw that never leaves 1.16.

On the coarse grids the pictures separate. The oracle’s λ drops to the bottom of the scale below 30 points, because there the grid regularises and λ should not. GCV follows it part of the way, erratically. The discrepancy principle does not follow at all: it keeps its λ near $10^{-1.6}$, because the residual it reads is the same whether the grid or λ is doing the filtering. It costs almost nothing, since on those grids a λ that small or large barely changes the answer. The L-curve’s median sits at the very top of the scale, λ near one, on every grid of 34 points or fewer: the curve’s corner is at its end, and a rule that finds a corner at the end of a curve has not found one.

What the data can say about the grid #

The second question needs a quantity the data can compute and the grid essays could not see. The discrepancy principle’s λ is chosen from the data alone, and the Tikhonov solution at that λ has an effective dimension — the sum of its filter factors — which is again a function of the data alone. It says how many directions of the data the rule admits.

On coarse grids it follows the grid: at 0.01% noise, 16.0 on 16 points, 20.0 on 20, 23.9 on 24, 25.8 on 26. The rule wants every dimension the grid offers and there are not enough. Then it stops. From 34 points upward at 0.01% noise it is 28.8, 28.9, 29.3, 29.3 and 29.6 — one number to within a direction, whatever the grid. At 0.1% it stops at 24.5 to 25.5, at 1% at 19.6 to 20.1. That number is the count of directions the data carry above their noise, and the grid cannot change it once the grid has more to offer. It is the same count where the answer stops being in the data read off the Picard plot as the index where the data’s coefficients sink into the noise, reached here by a different route: the discrepancy principle stops admitting directions when the residual reaches the noise, which is the point where the remaining directions are noise. A finer grid adds directions, and every one it adds is below the noise, so the count does not move.

This is a genuine grid signal and it costs nothing to compute. A rule follows from it directly: refine until the discrepancy principle’s solution stops using the grid — say, until it uses no more than 85% of the grid’s dimension — and stop there. It chooses 24 points at 1% noise, 30 at 0.1% and 34 at 0.01%.

The grid that count chooses #

At 1% noise the grid it chooses is 5.4 per cent worse than forty points: 0.1472 against 0.1397. At 0.1% noise it is 18.6 per cent worse, 0.1378 against 0.1162, and at 0.01% it is 13.7 per cent worse, 0.1274 against 0.1121. The error keeps falling after the ring, and falls by more at the lower noise levels, where the rule’s grid is closest to the forty that the answer wanted.

The data have not changed their count between the ring and forty points. At 0.01% noise the effective dimension is 28.8 on 34 points and 28.9 on 40: a tenth of a direction, for a fall in the best error of 14 per cent. Whatever the extra six points are buying, it is not directions of the data. It is representation — the ability of the grid’s reading to put the answer the data describe into a function close to the signal — and the corner essay measured exactly what it is: with the step given one coefficient of its own, 26 points reach 0.0215 at 0.1% noise and 0.0119 at 0.01%, both far below anything the smooth reading reaches on any grid. The six points past the ring are the smooth reading’s attempt to draw a corner, and the data cannot tell a corner drawn at 34 points from one drawn at 40, because the blur has already removed the difference.

So the answer to the question the discretisation essay left — whether any data-driven rule can see the difference between a 26-point and a 40-point grid at 0.1% noise — is that the data can see the part of it that is theirs and not the part that is the step’s. A grid is too coarse, in the data’s own terms, while the discrepancy principle wants every dimension it offers; past that, every further improvement is in how the answer is drawn, which the data do not constrain and cannot report.

The other discretisation, and what a user would actually get #

Every number above is for the sampled kernel read as hat functions, the discretisation the grid essays measured first. A better discretisation is a weaker filter found that integrating the kernel against the hats changes the coarse grids and not the fine ones, and it is worth knowing whether either finding here belongs to the sampled operator alone.

Neither does. With the kernel integrated, the discrepancy principle’s worst draw on any grid is 1.144, 1.138 and 1.040 times the oracle at the three noise levels. GCV’s worst is 55,601, 64,592 and 6,776 times, with 21, 13 and 10 draws more than twice the oracle — and at 1% noise four of those are on grids of 28 points or fewer, so the clean boundary of the sampled operator’s failure count is a property of that operator rather than of GCV. The effective dimension at the discrepancy principle’s λ saturates at 18.7 to 19.8, 24.1 to 25.2 and 28.7 to 29.7, within half a direction of the sampled operator’s counts, which is what a count of the data’s own directions should do when only the operator changed. The grid it chooses is 20, 28 and 34 points, and the best error there is 11.4, 13.4 and 16.0 per cent above forty points’.

The oracle’s error on the chosen grid is what the grid can do, and a user does not get the oracle. What a user with only the data gets is the discrepancy principle’s λ on the grid the data’s count chose, and that can be set against the same rule on the forty-point grid. On the sampled operator the two are 0.1555 and 0.1470 at 1% noise, 0.1420 and 0.1269 at 0.1%, and 0.1276 and 0.1142 at 0.01%: the fully data-driven procedure is 6 per cent worse than the same rule on the forty-point grid at the highest noise and 12 per cent worse at the two lower levels. On the integrated operator the figures are 7, 9 and 15 per cent. That is the price of choosing the grid from the data on this problem, and nearly all of it is the step: the data-driven procedure stops refining at exactly the point where refining starts to help only the corner.

It is worth being clear about what the price is not. It is not a failure of the discrepancy principle, which on either grid is within a few per cent of the best λ that grid allows. It is not noise in the count, which is flat to a tenth of a direction across the grids where it matters. It is the gap between the two things a grid does — carry the data’s directions and draw the answer — of which the data can report on only the first.

What this does not settle #

One blur, one signal and its step, three noise levels, sixteen draws, the sampled discretisation throughout. The failure counts for GCV are counts of a few draws in sixteen on each grid, and a rate of one in ten or one in five on a given grid is all they support; that the failures are confined to grids of thirty points and more held at every level, and the degenerate minimum that explains it is a property of square systems, but a problem with more data than unknowns would not have it.

The 85 per cent threshold in the grid rule is a choice, and a different choice moves the grid it picks by a few points. It does not change the finding, because the effective dimension is flat past the ring: no threshold on a flat curve can tell 34 points from 40.

The oracle is per draw and the scores are medians and worst cases of ratios to it. The grid essays used a single λ for all draws, chosen from the medians; their best-λ errors are slightly above the per-draw oracle’s here, and the rankings agree.

Still open: rules for the representation, and GCV with its trap removed #

A rule that sees the representation. The data cannot see the step’s cost because the blur has removed it. A rule that compares two readings of the same data — the smooth one and one with a breakpoint placed where the residual scan puts it — can see the difference the breakpoint makes to the residual at matched effective dimension. Whether that difference, which the data can compute, tracks the error difference the data cannot, is the direct test of whether a representation can be chosen from the data where a grid cannot.

GCV with the degenerate minimum excluded. GCV’s worst failures on fine grids are all at λ of $10^{-6.67}$ or below. A search that refused λ below the point where the residual falls under some fraction of its value at the real minimum would remove the trap on these grids; whether it removes it without also removing the right answer on the coarse grids, where the oracle’s λ is at the same place, is a measurement of one threshold — and it spends GCV’s one advantage, which is needing no statement about the noise.

More data than unknowns. Every system here is square, because the grid essays sampled the data and placed the unknowns on one grid. An instrument that measures at many points and a reconstruction on fewer is the more usual case, and there the residual cannot go to zero: the degenerate minimum vanishes, the misfit of a too-coarse grid becomes visible in the residual itself, and the grid rule above may have a second, sharper signal to read.