A parameter chosen on a smaller problem

Choosing without knowing scored the published rules for picking a regularisation parameter against an oracle that requires the exact answer, and none of them reached it. That was a comparison between rules, on one problem, all of them looking at the same 64×64 matrix.

The previous essay put a penalty inside a Krylov method, and in doing so moved the choice somewhere else. The parameter is now chosen on the projected problem — a bidiagonal matrix of twenty-five rows and twenty-four columns, built by the iteration itself out of the problem it was handed. Every rule from the regularisation field can be run on it, because it is a least-squares problem with a matrix and a right-hand side like any other.

The question is what a rule is reading when it reads a projection.

The rule that transfers by an identity #

The discrepancy principle asks for the largest λ whose residual is still no larger than the noise. It is the only rule in the field that has to be told ‖e‖, and the standard objection is that nobody knows ‖e‖.

Under projection it has a property none of the others do. The left basis U_{k+1} is orthonormal, so ‖b − A Vₖ y‖ equals ‖β₁e₁ − Bₖ y‖ for every y — the residual of the small problem is the residual of the large one. A rule that consults nothing but a residual and a noise level is therefore consulting identical numbers on both problems, and must return the same answer.

It does, and “the same” is meant literally:

The same grid point, ten times out of ten. Nothing is being approximated: an identity holds, and the rule inherits it.

The rule that does not #

Generalised cross-validation is the rule that needs nothing but the data. It minimises the residual squared over the square of trace(I − AA⁺), and that trace is the part that does not survive.

The trace of the influence matrix counts the data the fit did not consume — n minus the effective number of parameters. On the projected problem there is no n. There are k + 1 projected rows, and the denominator is bounded by k + 1 whatever the problem’s dimensions were:

On a problem with sixty-four rows. The criterion at four steps and the criterion at forty-eight are two different criteria, and neither is the criterion the rule was derived for.

The interesting part is what that does, which is much less than it sounds like and in a very particular way.

The λ it selects hardly moves. Across the whole run, at 1% noise, it stays between 3.2·10⁻² and 6.8·10⁻² — a factor of 2.15 while its own denominator moves by a factor of 27. GCV is a ratio, its numerator is a residual that changes by orders of magnitude as λ crosses the noise level, and a denominator wandering by a factor of twenty-seven cannot move the minimum of something that steep.

But it is biased, and the bias has a size. Against the same rule applied to the full problem:

The λ grid steps by a factor of 1.468. So the bias is two grid steps at twenty-four, one grid step at forty, at every noise level across two decades, with a single exception at the smallest noise and the smallest subspace where it is three.

A bias that depends on the subspace size and not at all on the data is exactly what “the denominator counts the subspace” predicts, and it is the strongest available evidence that the mechanism named above is the mechanism operating. It is also always in the same direction: the projected rule chooses more regularisation than the full one, because a smaller denominator makes small λ look worse than it is.

What the bias costs, which is almost nothing #

At 1% noise the oracle’s λ is 2.15·10⁻² and returns 0.1406. The full problem’s GCV picks 3.16·10⁻² and returns 0.1413. The projected GCV at k = 32 picks 4.64·10⁻² and returns 0.1429.

Two grid steps of over-regularisation, and 1.6% of error.

That is not a defence of the bias so much as a statement about the terrain. This site’s combination field has spent two essays establishing that a wide band of sensible parameters lands on one floor, and a rule biased by two grid steps is still inside the band. The bias would matter on a problem whose error curve had a sharp minimum, and the reason this one does not is the same reason regularisation is necessary at all: the singular values decay smoothly with no gap, so nothing about the answer changes abruptly with the cut-off.

The rule that declines #

There is a third behaviour, and this site has an established preference about it.

Below eight steps the discrepancy principle returns nothing at all. Not a bad λ — no λ. In a six-dimensional subspace, the residual at λ = 0 is still above the noise level, because the projection has not yet let in enough of the problem for the data to be fitted that well. The rule asks for the largest λ whose residual is under the noise, and there is no such λ.

GCV answers everywhere, including where the answer means nothing. The verified-bound essays made the argument for the other behaviour directly: an interval method’s three outcomes are there is a root here, there is no root here, and nothing can be said, and the third is what makes the first two worth having. A rule that always returns a number cannot distinguish between a problem it has understood and one it has not.

In practice the distinction is small here, because the errors at k ≤ 6 are close together whatever λ is used — 0.175 and 0.150 at two and four steps, from either rule. But the reason they are close is that the subspace is doing the regularising at that size, which the previous essay’s condition numbers show directly: at two steps the projected problem has κ = 1.38 and there is nothing for a penalty to suppress.

The third rule, and why it half transfers #

The L-curve reads two coordinates — the residual and the norm of the solution — and looks for the corner where the curve bends. Both coordinates survive projection, and the second does so for the same reason as the first: Vₖ has orthonormal columns, so ‖Vₖ y‖ equals ‖y‖ exactly, measured here at 8.9·10⁻¹⁶ and at zero.

So every point of the projected L-curve is a genuine point of an L-curve. And at forty steps the projected corner is the same grid point as the full problem’s — 6.813·10⁻³, error 0.1944, which is the corner’s own known shortfall and not a projection effect.

At twenty-four steps it is not. The projected rule returns 1.468·10⁻⁶ — the far end of the grid, nowhere near a corner anybody would draw — and an error of 0.2297.

The reason is worth separating from the trace story, because it is a different failure. Every point transfers exactly; the corner does not, because a corner is a property of the whole curve, and the projected curve is truncated. With twenty-four directions available, driving λ towards zero cannot make ‖x‖ large, since the solution cannot leave the subspace — so the vertical arm of the L, which is the thing the corner is the corner of, is simply absent. The rule then finds the largest curvature somewhere else and reports it with no indication that the feature it was looking for was not there.

That is the third behaviour on this page: a rule that is exactly right pointwise and wrong globally. GCV is biased by a knowable amount, the discrepancy principle is exact or undefined, and the L-curve is correct at every point and looking for something the small problem does not contain.

What a lie costs inside a subspace #

The discrepancy principle’s fragility is that it has to be told ‖e‖. The transfer identity means the projected rule inherits the fragility exactly — the same λ is chosen from the same lie — and the answers are not the same at all.

Understating the noise by a factor of ten costs a factor of 5,000 on the full problem and a factor of 28 inside the subspace. The rule made the identical mistake in both cases; what differs is how much damage the mistake could do, and the subspace has only thirty-two directions to be wrong in.

This is krylovreg.js’s own finding one construction along. There, the integer knob degraded gently where the continuous one did not, because a run has an end. Here the continuous knob degrades gently too, for the same reason and by a different mechanism: a run has an end, and so does a subspace.

Overstating the noise costs 12% either way, which is the asymmetry the regularisation field already measured, unchanged by projection.

Choosing on a small problem is not choosing cheaply #

The obvious reason to want the parameter chosen on the projection is cost. A sweep over forty-three penalties on a 25×24 bidiagonal system is nothing; the same sweep on the full problem needs a factorisation or a singular value decomposition per parameter, which is what the regularisation field pays and why its figures are drawn at n = 64.

That is real, and it is not the interesting half. The interesting half is that the projected problem is available and the full problem may not be. An iterative method is chosen when A is too large to factorise or is only known through its action on a vector; in that setting the full problem’s GCV cannot be computed at all, because its trace needs the singular values. The projected trace needs the singular values of a 25×24 bidiagonal matrix, which cost nothing.

So the comparison drawn above — projected rule against full rule — is a diagnostic rather than a choice anybody has. It exists because the problem was constructed small enough for both to be run, which is the same reason the oracle exists on this site at all.

What is being asserted, and what would break it #

The identity is asserted at four subspace sizes and three penalties, with the worst relative disagreement 7.7·10⁻¹⁵; the transfer is asserted as equality of the chosen grid point at five noise levels and two subspace sizes; and the trace bound — that the denominator cannot exceed k + 1 — is asserted at every k drawn.

That last one is the refusal. Feeding the build a claim that the projected trace counts the problem’s degrees of freedom, at k = 8 on a 64-row problem, has to fail: the trace there is 1.03 and the claim says it exceeds thirty-two. If someone later replaced the projected trace with a scaled version pretending to be the problem’s — which is one of the published repairs for this exact bias — the refusal would stop accepting the counterexample and the build would say so.

What the drag does #

The slider is the noise level, and it moves one thing that matters: the subspace size at which the discrepancy principle becomes available. With less noise the residual has further to fall before it reaches the noise level, so a larger subspace is needed before any parameter can bring it down.

The trace curve does not move at all under the slider. It is a property of the subspace and of λ, and the data does not enter it — which is the whole argument of this essay drawn as an absence.

Below half a per cent of noise something else appears: GCV’s λ starts to move with k in earnest, a factor of 6.8 at 0.2% noise and 14.7 at 0.1%. That is not the trace catching up. It is the problem: at low noise the components the subspace admits late are still worth keeping, so the right λ genuinely falls as k grows, and the rule is following the answer rather than its own denominator. The assertion is therefore written in two halves either side of that noise level, in the precedent this site set at the mixed-precision threshold — a claim stated unconditionally where it is false over a third of the slider is a claim the figure would be quietly wrong about.