The step that stops mattering

A parameter that counts steps established the awkward fact this essay removes. On an ill-posed problem an iterative method’s error falls, reaches a minimum, and then climbs by orders of magnitude — and the residual, the only quantity a solver can see, falls at every step throughout. The step count is the regularisation parameter, and getting it wrong in the safe-looking direction is expensive.

Everything about that is a statement about where the penalty is not. The iteration builds a subspace, projects the problem onto it, and solves the projection exactly. Nothing regularises the projected problem, because the projection was supposed to be the regularisation.

So put a penalty there too.

What is being built #

The Golub–Kahan bidiagonalisation generates two orthonormal bases at once — one for the row space and one for the column space — and between them a matrix Bₖ that is (k+1)×k and has entries on only two diagonals, satisfying A Vₖ = U_{k+1} Bₖ exactly. Least squares over the subspace spanned by the columns of Vₖ is then a least-squares problem in k unknowns with a bidiagonal matrix, which is what LSQR solves at every step. Its answer is the projected problem’s exact one.

A hybrid method changes one line. Instead of minimising ‖Bₖ y − β₁e₁‖ it minimises ‖Bₖ y − β₁e₁‖² + λ²‖y‖², and takes the same x = Vₖ y. There are now two parameters — the step count k on the outside and the penalty λ on the inside — and the whole question is what having both does.

The construction is not a hybrid of two methods in the sense of alternating between them. It is one iteration with a second decision taken inside every step of it, and the reason that is worth a name is that the two decisions are about the same quantity: how much of the data to believe.

Two identities make the small problem the same problem #

A penalty applied to a projection is only meaningful if the projection has kept what the penalty is supposed to act on. Two facts settle that, and both are asserted rather than quoted.

The residual is preserved exactly. U_{k+1} has orthonormal columns, so ‖b − A Vₖ y‖ equals ‖β₁e₁ − Bₖ y‖ for every y. Not approximately: the residual of the (k+1)×k problem is the residual of the 64×64 one. Checked at four subspace sizes and three penalties — twelve pairs — the worst relative disagreement is 7.7·10⁻¹⁵, on a basis whose own orthogonality error is 1.8·10⁻¹⁵.

That is what makes the small problem worth choosing a parameter on. A rule that reads a residual is reading the same number either way, and the next essay is about what happens to a rule that reads something else.

And the projected problem is solved twice. The stacked route hands the (2k+1)×k system [B; λI] y ≈ [β₁e₁; 0] to this site’s own Householder least squares; the second route takes the singular value decomposition of B and applies the filter σ²/(σ² + λ²) to each projected component, which is the regularisation field’s own filter applied to a 17×16 matrix instead of a 64×64 one. At three penalties the two agree to 1.4·10⁻¹⁵.

The measurement #

Forty steps, sixty-four unknowns, 1% noise, and the inner λ chosen at every step by generalised cross-validation on the projected problem.

The unregularised run is the one this site has drawn before under another name — that column is LSQR, and its shape is semi-convergence. Twenty steps in it is at its best; twenty steps later it is wrong by a factor of a thousand, and its residual has fallen monotonically the whole way.

The regularised run reaches a floor 0.2% higher and then does not move. The last twelve steps change the answer in the twelfth significant figure.

What is bought is not accuracy. The two floors are within a fifth of a per cent of each other, which is the combination field’s own finding arriving again: the floor belongs to the problem, four knobs find it, and a fifth arrangement of two of them finds the same one. What is bought is that the floor is reached and held, so the outer parameter can be set by a budget rather than by a rule.

Why the curve turned in the first place #

The obvious explanation for semi-convergence is that the projected problem inherits the ill-posedness: more steps, more of the small singular values, more amplified noise. The first half of that is true and the arithmetic in it is not.

The singular values of B_k are the Ritz values of the bidiagonalisation, and they converge to the largest singular values of A first — the top four agree with A’s to 10⁻⁶ by the end of the run. So the projected condition number does climb:

And κ(A) is 5.7·10¹². At forty-eight steps the projected problem is a million times better conditioned than the problem, and the unregularised answer there is wrong by a factor of 14,300. A condition number six orders of magnitude short of the one being blamed is not the explanation.

The quantity that moves with the error is the last column of that table. Each step admits one more direction, each new direction has a smaller singular value than the last, the noise has a component along it, and that component is divided by the singular value. So the cost of a step is ‖e‖/σ_min, and from twenty-four steps on the error is a fixed fraction of it:

The error moves by a factor of 62,000 and the fraction moves by a factor of 1.5. The numerator of a condition number — the largest singular value — has nothing to do with any of it, which is why the ratio is the quantity worth drawing and κ is not.

This also says exactly what the penalty is doing. σ²/(σ² + λ²) is small where σ is small, so the directions the subspace has just admitted are the ones it suppresses, and it suppresses more of them the further the run goes. The inner knob tracks the outer one because both are functions of the same thing.

It is the penalty, not the rule #

The reading the table above invites is that the rule is doing the work: GCV watches the projected problem grow ill-posed and raises λ to match. That reading is wrong, and the check is cheap — fix λ once, never revisit it, and run the same forty steps.

Any λ of about 0.02 or above removes the turn completely, and every one of them lands on the floor — the best of the fixed runs, at λ = 0.02, reaches 0.1400, which is better than both the adaptive run and the best unregularised iterate. A penalty chosen once and left alone is enough.

What a fixed penalty does not survive is being too small. At λ = 0.01 the run turns again, gently; at λ = 0.001 it turns properly and ends 9.5 times above its own best. A penalty an order of magnitude below what the subspace has just admitted suppresses nothing that the subspace has just admitted, which is the same sentence as the σ_min table one paragraph up.

So the inner rule’s job is not to remove the turn. It is to remove the need to know in advance which λ is large enough — and that is the outer rule’s job moved one level down rather than abolished. This construction redistributes the difficulty; it does not eliminate it. The redistribution is worth having because the new question has a much flatter answer: a factor of ten in λ is the difference between working and not, where a factor of two in the step count was.

The projection is a truncation until it stops being one #

There is a reading of the table above that makes the whole construction unsurprising, and it is worth stating because it is nearly right.

At small k the projected problem is well conditioned because the subspace has not let the difficult part of the problem in. That is a truncation — the same object the rank essay is about, arrived at without anybody choosing a cut-off. It is why stopping early was ever a regularisation, and it is why the two knobs land on the same floor.

What the table shows is where that reading expires. By thirty-two steps the projected problem is ill-conditioned in its own right, and the projection has stopped being a truncation and become a faithful reproduction of a problem that has no answer in it. From there, only the inner penalty is regularising anything.

The one thing the construction cannot skip #

The bases have to stay orthogonal, and on this problem the plain three-term recurrence does not keep them.

The right-hand column is the Lanczos field’s ghost arriving in a regularisation method. A lost basis produces a projected matrix with two singular values where the problem has one, and every quantity computed from that matrix — the filter, the trace GCV divides by, the residual the discrepancy principle reads — is then computed on a problem the method is not solving.

What makes it worth stating as a rule rather than a caution is that the error is often barely affected. A method can be choosing its parameter on a fictional spectrum and returning a reasonable answer, which is the condition under which nobody investigates.

What it costs #

Per step, the hybrid method adds one sweep over a grid of forty-three penalties, each of which is a least-squares solve of a (2k+1)×k bidiagonal-plus-diagonal system. At k = 28 that is forty-three solves of a 57×28 system against one solve of a 29×28 system — arithmetically trivial beside the two products with A that the step itself costs once the matrix is large, and not trivial at all at the sizes drawn here, where A is 64×64 and dense.

That is the honest scaling statement and it runs in the method’s favour: the inner problem’s cost depends on k and the outer problem’s on n, so the arrangement gets cheaper relative to the iteration exactly as the problem gets big enough for an iterative method to be the right choice.

What it does not cost is a decision. The comparison that matters is against running LSQR and stopping well, and stopping well requires a rule, and the rules do not reach the oracle.

Two knobs, and only one of them is now a knob #

The step count has not disappeared. It still decides how much arithmetic is done, and it still has to be large enough for the subspace to contain the answer — below twelve steps the error is visibly worse whatever λ is chosen, because no penalty can recover a component the subspace does not have.

What it has stopped being is a modelling decision. Past the point where the subspace holds the answer, running longer changes nothing that matters, and the parameter that decides how much of the data to believe is the inner one. The outer loop can then stop on a budget, on a residual, or on the wall clock, and none of those choices is wrong by a factor of a thousand.

What the drag does #

The slider is the noise level. Less noise moves the floor down and the unregularised turn later, in exactly the way the step-count essay’s figure does — at 0.1% noise the unregularised run’s best sits further right and lower, and its overrun by the end of the run is larger rather than smaller, because a smaller σ_min is reached before the run ends and the noise is divided by it just the same.

What does not change at any position of the slider is which of the two curves has a minimum in it. That is the claim the figure is drawn to be falsifiable about, and it is asserted at every frame: the unregularised run must end at least five times above its own best, and the regularised one must end within 50% of its own.