More samples take the floor and leave the dip

The minimum on the right repaired generalised cross-validation on fine grids with a rule that has no parameter in it: take the local minimum of GCV’s function at the largest λ, not the global one. Over 528 draws it removed every miss worse than ten times the oracle’s error, and it cost nothing on the coarse grids where the smallest λ was the right answer. The essay also said where the trap came from. GCV’s function is

$$G(\lambda) = \frac{\|b - Ax_\lambda\|^2}{(m - t(\lambda))^2}, \qquad t(\lambda) = \sum_k \frac{\sigma_k^2}{\sigma_k^2 + \lambda^2},$$

with m the number of data and t the trace of the influence matrix — the number of directions the filter has admitted. On an n × n system both the residual and $m - t$ go to zero as λ does, so the ratio is a zero over a zero at the left end of the scale, and on a fine grid whose smallest singular values are tiny it can dip there below its real minimum.

That account made a prediction with a sign, and the essay named it as the cheapest test available. With more samples than unknowns, $m > n$, neither term reaches zero. The residual tends to the least-squares residual, which carries $m - n$ dimensions of noise, and $m - t$ tends to $m - n$. The left end of G is then a finite number of about the size the noise sets, and no longer a ratio of two vanishing quantities. If the trap was the squareness, it should be gone; if it was the tiny singular values, which a taller matrix still has, it should not.

It is half gone, and the half that stays is the one that did the damage.

Five ratios of samples to unknowns #

The problem is the continuous blur the grid essays used. The unknowns are nodal values of a signal on n equispaced points; the operator is the row-normalised sampled kernel; the data are the continuous blur of the continuous signal, computed on a fine quadrature so that no grid is handed data generated by its own operator; the error is read as a function against the signal at two thousand points. The one change is that the data are sampled at $m = rn$ equispaced points, for $r = 1$, 1.25, 1.5, 2 and 4. At $r = 1$ this is the grid essays’ problem exactly. The noise per sample is fixed at 1%, 0.1% or 0.01% of the data’s root mean square, so four samples per unknown is four times as much information about the same unknowns, not a lower noise level.

On each of five grids — 24, 40, 48, 64 and 96 unknowns — at each noise level, sixteen seeded draws are solved with Tikhonov at 121 values of λ from $10^{-8}$ to one, and each draw’s λ from plain GCV, from the rightmost local minimum and from the discrepancy principle is scored by its error over the best error on the same draw. That is 240 draws at each ratio.

The floor goes at once #

The prediction’s own quantity is the left end of the function, and it behaves exactly as predicted. On the square systems the lowest draw on the 40-point grid has its left end at 0.28 of the real minimum and on the 48-point grid at 0.64: the zero over a zero came out small. With 1.25 samples per unknown the lowest over every grid and every draw is 0.88; at two per unknown it is 0.97, and at four it is 1.00. The left end has become the least-squares answer’s GCV value, and that value sits at or above the real minimum.

So the minimum at the floor of the scale disappears. On the square systems 21 of the 240 draws have their global minimum at the smallest λ on the scale — nineteen on the 24-point grid, where the unregularised solve is the right answer, and two on the fine grids, where it is catastrophic. At every ratio above one, that count is zero.

How high the left end sits, predicted #

The left end does more than change sign, and its height can be computed before any curve is drawn. Near the floor of the scale every direction the filter has not yet admitted carries only noise, so the residual there is about $\delta^2(m - t_0)$, where $t_0$ is the trace at the smallest λ, and $G$ there is about $\delta^2/(m - t_0)$. At the real minimum the same argument, with the residual per remaining degree of freedom ρ close to one, gives about $\rho\,\delta^2/(m - t_*)$. Their ratio is

$$\frac{G(\lambda_{\text{floor}})}{G(\lambda_*)} \approx \frac{m - t_*}{m - t_0},$$

the trace term at the real minimum over the trace term at the floor. On a square system the denominator goes to zero with λ and the ratio is anything at all, which is the zero over a zero. With more samples it is a number bigger than one by exactly the directions the floor has admitted and the minimum has not, in units of the directions left over.

It is also the number the curves show. On 48 unknowns at 1.25 samples per unknown and 0.1% noise the median left end over the real minimum is 2.66 and the ratio of trace terms is 2.65; on 96 unknowns at four per unknown and 0.01% noise both are 1.06. Across all 48 fine-grid cells with more samples than unknowns — four grids, four ratios, three noise levels — the median measured height is the predicted one to within 8.5 per cent, and most are within three. The prediction also says why the left end drops towards one as the ratio grows: m grows and the number of directions between the floor and the minimum does not, so the ratio of the two trace terms is pushed towards one from above. At four samples per unknown the left end sits only 6 to 19 per cent above the minimum, which is still above it and, as the next section shows, not far enough above to matter much.

The one assumption in that argument is that ρ is near one on the draw in hand, and the rest of this essay is about the draws on which it is not.

The dip does not #

On 48 unknowns at 0.1% noise, the square system has two draws whose deepest minimum lies far to the left of the real one: at λ of $10^{-6.67}$, where plain GCV’s error is 1,229 times the oracle’s, and at $10^{-7.93}$, 2,941 times. Turn the dial to 1.25 samples per unknown. Every curve’s left end lifts above one. But two draws still dip below their rightmost minimum — one harmlessly, at $10^{-3.0}$ beside the real minimum at $10^{-2.4}$, and one at $10^{-6.53}$, where plain GCV’s error is 2,158 times the oracle’s. The left end is no longer a trap; a minimum a decade to its right is, and it is just as deep. At 1.5 per unknown one draw dips, at $10^{-3.4}$, and costs 3.1 times the oracle’s error; at two and four, on this grid, none does.

Counted over all five grids and three noise levels, those dips — the draws whose deepest minimum is an interior one, to the left of the rightmost — fall steadily and do not stop. There are 28 on the square systems, 20 at 1.25 samples per unknown, 13 at 1.5, eight at two and four at four. The draws on which plain GCV misses by more than ten times follow them down, 16, 11, 5, 3, 1, and those by more than a hundred times go 11, 5, 1, 0 and then back to one.

The survivor at four samples per unknown is on the finest grid at the lowest noise. Of sixteen draws on 96 unknowns sampled at 384 points, two dip: one a decade and a bit to the left, at $10^{-4.2}$, where GCV’s error is 2.1 times the oracle’s, and one at $10^{-6.93}$, four decades to the left of the real minimum, where it is 877 times. Every curve’s left end sits above one, as the prediction said it would. The trap is simply not at the left end.

What the prediction got wrong about the mechanism #

The account in the previous essay was right that squareness produced a minimum at λ = 0 and wrong that this was where the fine-grid failures lived. On the square fine grids — 40, 48, 64 and 96 unknowns — the interior dips outnumber the floor minima fourteen to one: thirty dips in 192 draws, two of them at the floor. The figure of sixteen curves in the minimum on the right already showed this and nobody read it that way; its catastrophic picks sat at $10^{-6.67}$ and below, which on a scale ending at $10^{-8}$ looked like “near zero” and was in fact an interior point with a rise on its left.

What produces an interior dip is visible in the derivative. As λ falls past a singular value, one more direction is admitted: t rises by about one and the residual loses that direction’s coefficient squared. If the direction carries only noise, with coefficient $z\delta$ for δ the noise level per sample and z a standard normal draw, then

$$\Delta \log G \approx \frac{2}{m - t} - \frac{z^2\delta^2}{\|r\|^2} = \frac{1}{m-t}\left(2 - \frac{z^2}{\rho}\right), \qquad \rho = \frac{\|r\|^2}{\delta^2 (m - t)}.$$

Admitting that direction lowers G whenever $z^2$ exceeds $2\rho$. The number ρ is the residual per remaining degree of freedom in units of the noise variance. In expectation it is one and the bar is two — about one direction in six clears it by chance — and between the real minimum and the floor G does a walk whose steps are mostly upward and occasionally down. A dip is a stretch of that walk that goes down further than the real minimum’s own margin.

Why more samples still help #

The expansion says what more samples change, and it is not the left end. It is ρ.

At the real minimum the median of ρ is about one at every ratio — 0.97, 1.00, 0.98, 0.98, 0.98 — which is what an honest residual should be. Its spread is what moves. On the square systems its tenth percentile is 0.56: on one draw in ten, the residual at the real minimum is little more than half what the remaining degrees of freedom should carry, so the bar a lucky coefficient must clear is halved, and a dip can be built from directions whose noise is not large at all. With 1.25 samples per unknown the tenth percentile is 0.73; at two, 0.84; at four, 0.85. The ninetieth percentile comes down from 1.46 to 1.15 in the same way.

The reason is the count behind ρ. It is an average of squared noise over $m - t$ directions, and on a square system that count is the unknowns the filter has not admitted, which near the real minimum on a fine grid is a few dozen. With four samples per unknown it has three times n more directions in it, each a pure noise direction orthogonal to the range, and an average over more terms is steadier. It is the same reason the road that squares the problem’s least-squares fits have a residual worth reading at all: with more equations than unknowns the misfit has room to be a sample of the noise. The dips that remain are then made of directions whose noise really was large: the directions a surviving dip admits have a mean squared noise coefficient of 1.6 to 1.9 on the oversampled systems, against an expectation of one, where on the square systems the median was 1.19 — the square dips did not need luck in the coefficients, only a low residual.

That is a partial account and it is labelled as one. It explains why the dips thin with the ratio and why they do not reach zero: the walk still has downward steps, each with probability about one in six, and a long enough stretch of small singular values gives it room. It does not predict the counts.

The repair still repairs, and nothing else moved #

The rightmost minimum’s worst draw, over every grid and noise level, is 7.31 times the oracle on the square systems and 3.70, 2.98, 2.68 and 2.57 at the four higher ratios. It misses by more than twice on two or three draws at every ratio, and those misses do not move with the sampling; they are the misses the previous essay could not rescue, draws on which the function has no minimum near the oracle’s λ at all. Oversampling neither creates them nor cures them.

The discrepancy principle, told the noise, is within 1.16 of the oracle on its worst draw at every ratio — 1.159, 1.163, 1.162, 1.155 and 1.164 — the same number the data count their dimensions, not the step’s found on the square grids. Choosing without knowing first set the published rules against an oracle on the collection’s own problem, and the discrepancy principle’s steadiness here is the same kind of number, bought with the same piece of information. Its target is the noise norm over all m samples, and a taller matrix changes nothing about how the residual crosses it.

So the rule that fixed GCV on square systems is still needed at every ratio and still sufficient at every ratio. A code that takes the rightmost minimum is unaffected by whether its matrix is square. A code that takes the global minimum and relies on having more data than unknowns is relying on something that cuts the catastrophic failures from eleven in 240 to one.

Why the floor was never the point #

It is worth being clear about what the square systems’ floor minima were, because they looked like the whole problem. On the 24-point grid all nineteen are the right answer: a grid that coarse is its own regulariser, the unregularised solve is best, and GCV’s left end being lowest is GCV working. The grid was the first filter measured that hand-over, and where the grid hands over to λ located it near 28 points at these noise levels. With more samples the coarse grid’s GCV function acquires an interior minimum instead, near $10^{-2.2}$ at 0.1% noise on every draw, while the oracle stays at the bottom of the scale — and the error barely notices, because a grid that coarse filters before λ does. At four samples per unknown GCV on the 24-point grid is within 1.05 of the oracle at every noise level, and the discrepancy principle within 1.13.

On the fine grids the floor minima were two draws. The damage was done by the other twenty-eight, and they were interior from the start.

What a taller matrix is for #

The result reads naturally as a disappointment and it is better read as a measurement of what the extra data buy. Four times the samples do three things here. They remove the floor minimum, which on a fine grid was a rare and catastrophic failure and on a coarse one was the right answer. They cut the interior dips by seven and the tenfold misses by sixteen, because they steady the residual that GCV divides by. And they do nothing for the rightmost minimum’s residual misses or for the discrepancy principle, neither of which depended on the thing that changed.

That is the pattern one draw in twenty found among the parameter rules generally: a rule’s median draw and its worst draw answer different questions, and a change that improves one need not touch the other. Here the median draw of GCV and of its rightmost minimum is within four per cent of the oracle on every grid at every ratio, and the discrepancy principle’s within ten, and none of the three medians moves with the sampling. Oversampling works on GCV’s tail, and in the tail it helps a great deal without making it safe. A rule that has to be told how good its answer will be priced the other side of that: the discrepancy principle’s safety is paid for with the noise level, which GCV declines to ask for and oversampling does not supply.

Equispaced samples of one kernel under white noise #

Five grids, one kernel, one signal and white noise at three levels. The samples are equispaced and the extra samples fall between the unknowns; an instrument that sampled more densely in one region would weight the residual unevenly, and the ρ argument would have to be made per region. The blur is Gaussian and its smallest singular values fall off a cliff; an operator whose spectrum decays slowly would give the walk fewer small-σ directions to go down, and should have fewer dips at every ratio.

The account of the dips is a first-order expansion. It treats each admitted direction as pure noise, which is true well to the left of the real minimum and not near it, and it treats the steps as independent, which they are not quite, since ρ itself changes as the walk proceeds. It explains the direction of every trend in the figures and the size of none of them.

Still open: the dip’s depth, and a rule that reads ρ #

A dip’s depth from its walk. The expansion predicts each step of $\log G$ from one noise coefficient and the current ρ. Summing those predictions from the rightmost minimum leftwards, draw by draw, and comparing the predicted walk with the computed function would say whether the first-order account is the whole of the dip or whether the signal left in the small-σ directions matters too. The prediction with a sign is that the predicted walk crosses below zero on the same draws the computed one does, and on few others.

A guard that reads ρ. The dips form most easily where ρ at the real minimum is low, and ρ needs the noise level, which GCV does not have. But the least-squares residual, available whenever $m > n$, is an estimate of the noise with $m - n$ degrees of freedom. A rule that estimated δ from it, computed ρ at each candidate minimum and refused a dip when ρ at the real minimum was implausibly low would be GCV told the noise by its own data. Whether it removes the four survivors at four samples per unknown without becoming the discrepancy principle is the measurement.

The misses on the right. Two or three draws at every ratio are missed by the rightmost minimum by two to seven times, and oversampling does not touch them. The minimum on the right proposed looking for them through the mean square of the coefficients near the chosen λ, which one draw in twenty found 1.49 times its expectation on interior failures. With a taller matrix that statistic has a noise estimate to be compared against for free, which is the same idea as the guard above applied at the other end of the function.