A preconditioner that arrives past the answer

Everything this collection says about preconditioning rests on one sentence, and the sentence is true on the problems it was written for. Changing the condition number on purpose puts it plainly: a preconditioner replaces Ax = b by an equivalent system with the same solution and a better spectrum, so the iteration arrives at the same answer in fewer steps. The answer does not move because the system was solved to convergence, and convergence is defined by the answer.

An ill-posed problem regularised by stopping is not solved to convergence. A parameter that counts steps stopped conjugate gradients at step 20 on the 64-point deconvolution, because continuing to the converged answer would have reconstructed the noise, and the converged answer is worse than useless. The answer that matters is an iterate part-way along the run.

So the sentence changes meaning. A preconditioner that changes the path changes the iterate at step 20, and step 12, and step 1 — which is to say it changes the answer the method is actually used for. This essay measures two preconditioners on the same problem and finds both effects the sentence rules out: one that is good by the standard measure and reaches a worse answer, and one that reaches a better answer only if it is built in a way the standard construction does not suggest.

The preconditioner a textbook would recommend #

The iteration is CGLS, conjugate gradients on AᵀAx = Aᵀb without forming the product, exactly as in an expiry date the noise does not move. Its operator is AᵀA, and the obvious preconditioner for AᵀA is AᵀA itself made invertible: P = AᵀA + αI.

By the measure preconditioners are ordinarily judged on, it is excellent. The preconditioned operator has eigenvalues σ²/(σ² + α), which are close to one wherever σ² is well above α and close to zero wherever it is well below. The larger α, the fewer eigenvalues are gathered near one; the smaller α, the more. The rate the condition number predicts is the account of why a cluster near one is what conjugate gradients rewards, and by that account shrinking α makes P better at every step.

It is also a preconditioner nobody would use for a well-posed solve, because applying P⁻¹ is a Tikhonov solve and a Tikhonov solve is as expensive as the problem. The reason to run it here is not economy. It is that its effect on the iteration can be read off exactly, and what it does is a clean instance of what any preconditioner that clusters the leading spectrum does to a stopped run.

At α = 0.1 the sentence holds. The preconditioned run reaches 0.1426 — the unpreconditioned floor, to four figures — at step 12 instead of step 20. At α = 0.01 it reaches 0.1425 at step 4. Fewer steps to the same answer, which is what a preconditioner is for.

The first iterate is the part worth watching, because it is where the trouble arrives. Its error is 0.2289 with no shift worth the name at α = 1, 0.1595 at α = 0.1, 0.1461 at α = 0.01. The first step is getting better at every stop as the preconditioner improves, and it is catching up with the best iterate.

The first step is a Tikhonov solution, to twelve digits #

The first step can be written down, and writing it down explains everything that follows. CGLS starts from zero, so its first residual is b and its first search direction, after preconditioning, is

z₀ = (AᵀA + αI)⁻¹ Aᵀb

which is word for word the Tikhonov solution at λ² = α. The first iterate is z₀ times a step length.

That is a claim with two routes available, and the figure computes both: the iteration’s own first iterate, and the filter-factor sum σ²/(σ² + α) · uₖᵀb/σₖ through the singular value decomposition, which shares nothing with the iteration but the matrix. They agree to 1.5·10⁻¹⁴ at α = 0.1, 1.3·10⁻¹³ at 0.01, 1.2·10⁻¹² at 10⁻³, and 6.2·10⁻¹⁰ at 10⁻⁶. The agreement loosens by a factor of ten for every factor of ten in α, which is the conditioning of the shifted matrix growing like 1/α and multiplying the rounding — the product of the gap and α sits between 6·10⁻¹⁶ and 1.5·10⁻¹⁵ at every stop. The step length is 1.111 at α = 0.1, 1.011 at 0.01, 1.001 at 10⁻³, and 1.000 to four figures at every smaller shift.

So the preconditioned iteration’s first answer is not an approximation to anything. It is a regularised solution, with a regularisation parameter the preconditioner chose, delivered before the iteration has done any iterating.

At α = 10⁻³ the best preconditioned iterate is step one, at 0.1412. That is a better answer than the unpreconditioned run’s best, and it is so for a reason that has nothing to do with iteration: the oracle Tikhonov λ on this problem is 0.0224, λ² = 5.0·10⁻⁴, and a shift of 10⁻³ sits close to it. The first step is nearly the best Tikhonov solution, 0.1405, and the half per cent between them is the distance between 10⁻³ and 5·10⁻⁴ on a flat stretch of the Tikhonov error curve.

Past the right shift there is no early enough step #

Keep improving the preconditioner.

At α = 10⁻⁶ the first iterate’s error is 1.3533 and every iterate after it is larger. There is no step to stop at that recovers the plain run’s 0.1426, because the first step has already gone past it. The preconditioner has clustered 32 eigenvalues at one — ten more than at 10⁻³ — and the iteration cannot stop early enough to use it.

The mechanism is the filter again, and it is the mechanism of the method that cannot use a smooth answer turned the other way. The first step keeps the fraction σ²/(σ² + α) of each component. With α far below the right λ², that fraction is nearly one for every component whose σ² exceeds α, and many of those components are noise divided by a small σ. The unpreconditioned iteration builds its answer from the top of the spectrum down, one polynomial degree at a time, and stopping it at step 20 is stopping it before it reaches the noisy components. The preconditioned iteration hands it all of them at once. Every subsequent step can only refine within a space that already contains the damage.

The whole sweep, over eleven decades of α:

The second column rises at every stop, which is the preconditioner improving. The fourth column is flat at the floor down to 10⁻², dips to the Tikhonov value at 10⁻³, and then rises by roughly a factor of three for every decade after — 0.16, 0.33, 1.35, and on to 719 at 10⁻¹². From 10⁻³ down, the third and fifth columns are the same number, because the best step is the first.

Read as a statement about preconditioners, the table says that on a stopped iteration “better” has an optimum, and the optimum is not where the spectrum is best clustered. Past it, the preconditioner’s quality and the answer’s quality move in opposite directions, and they move there monotonically.

The shift is the regularisation parameter, renamed #

The optimum sits at a recognisable place. The best preconditioned error is least at α = 10⁻³, next to the oracle Tikhonov λ² of 5·10⁻⁴, and the sweep’s own boundary between “same floor, fewer steps” and “first step, worse” falls between 10⁻³ and 10⁻⁴ — straddling the same number.

That is not a coincidence to be admired but an identity to be read. A preconditioned stopped iteration has two parameters where the plain one had one: the step count and the shift. The shift fixes a Tikhonov filter the iteration cannot undo, and the step count refines within it. Above the right λ², the filter is too strong for the first step to be enough, and the steps do the rest of the regularising in the ordinary way. Below it the filter is too weak, and no number of steps — including zero extra steps — puts back what it let through.

So a preconditioner for a stopped iteration is a second regularisation parameter, and choosing it well means knowing roughly where the first one should be. That is circular in exactly the way choosing without knowing describes: the right λ² requires a rule, and the rules each cost something against an oracle that is not available. A preconditioner tuned by the usual spectral measure has quietly chosen λ² with a rule nobody examined, and the rule always says “smaller”.

At a tenth of the noise the boundary moves by the factor the oracle moves: λ² goes from 5·10⁻⁴ to 1.3·10⁻⁵, and the shift below which the first step is already too far goes down with it. The worst case at 10⁻¹² is 71.9 rather than 719 — exactly ten times smaller for ten times less noise, which is what a first step that is purely a Tikhonov solution with too small a λ must do, since its error at such a λ is the noise divided by the smallest singular values it keeps, and nothing else. So the preconditioner’s safe range depends on the data’s noise level as well as on the operator — the same preconditioner is safe on one measurement and destructive on a better one.

A smoothing operator as a preconditioner #

The second preconditioner changes the answer in the other direction, and it needs a different problem to show it.

A derivative penalty ‖Lx‖ does not charge for vectors in the null space of L. For the first difference that null space is the constant vectors, and a parameter that counts steps measured what that is worth on a signal raised by a constant offset: at an offset of ten, the derivative penalty’s best error is 1.85 times better than the norm penalty’s, because a penalty on ‖x‖ shrinks the offset and a penalty on ‖Lx‖ does not see it.

The iterative counterpart of a general-form penalty is to run the iteration in the variable the penalty measures: set y = Lx, so x = L⁻¹y, and run CGLS on A L⁻¹. Stopping early keeps y modest, which is what a derivative penalty asks for. The difficulty is that L is not invertible — its null space is precisely the thing the construction is for — and the iteration needs something to multiply by.

There are two ways to supply it. The obvious one completes L to an invertible matrix by adding one boundary row; its inverse is then the matrix of cumulative sums, so x is y integrated. The other, standard in the regularisation literature and not obvious at all, fits the null space component of the answer outright first — one number here, the mean — and runs the iteration only on what is left, through an oblique projector that keeps the iteration from ever moving the fitted constant.

The completion that charges for the offset #

The obvious construction makes things worse. At an offset of ten and 10% noise, plain CGLS reaches 0.3243; the same iteration through the invertible completion reaches 0.6528, twice the error. The preconditioner that was supposed to make the offset free has made it dearer.

Part of the reason is visible in the construction. The completion’s boundary row turns the answer’s first entry into a coordinate of y on its own, and the first entry of an offset signal is the offset. In the variable y the constant vector of height ten is not a smooth nothing; it is a spike of height ten in the first coordinate. A stopped iteration keeps y small, and a spike of ten is not small, so the iteration charges for the offset in full — the one direction the general form was built to exempt is the direction the completion made most expensive. That accounts for the charge. It does not account for the factor of two against the plain run, which charges for the offset through ‖x‖ over all sixty-four entries; the size of that difference is measured and not explained.

The error is also measured as an absolute distance over the norm of the offset-free signal rather than as a relative error, and that choice is not cosmetic. A relative error divides by ‖x‖, and ‖x‖ grows with the offset, so a relative error would report every method improving as the offset rises — the plain run included — when every method is either getting worse or standing still.

Splitting the null space off first #

The split behaves as a derivative penalty should. At offsets of 0, 2, 5 and 10 its best errors are 0.1653, 0.1654, 0.1657 and 0.1655 — flat to three figures while the offset grows from nothing to five times the signal’s own peak. Plain CGLS goes 0.1675, 0.1768, 0.2248, 0.3243; the completion goes 0.1653, 0.2367, 0.3887, 0.6528. At an offset of zero all three agree within 1.3%, as they should, since then there is nothing in the null space to treat differently.

The mechanism is the projector. The fitted constant is the least-squares fit of b by A times the constant vector, and the operator the iteration then runs on is built so that every vector it produces is orthogonal, after multiplication by A, to that fitted direction. Nothing the iteration does can move the constant, and the constant is never inside the stopped iteration’s accounting at all. That is the exemption the penalty grants, delivered to an iteration.

At 10% noise the split is below the general-form Tikhonov penalty’s 0.1704 — by 3%, the same kind of margin by which a stopped iteration beat or trailed a penalty in four knobs and one floor. At 1% noise the ordering reverses by a similar amount: the split holds 0.1434 at every offset against the penalty’s 0.1410, while plain CGLS rises from 0.1426 to 0.1797 and the completion from 0.1433 to 0.3657. So the split matches the general form, in the sense that neither beats the other by more than a few per cent at either noise level; it does not improve on it. What it adds is the iteration’s economy — products with A and a cheap oblique projection, instead of a factorisation of a stacked matrix for every λ.

What changes when a preconditioner meets a stopped iteration #

Put the two preconditioners side by side and the familiar account of preconditioning needs three amendments on problems regularised by stopping.

Quality is not monotone. The shifted preconditioner improves by every spectral measure as α falls, and the answer improves until α reaches the right regularisation parameter and deteriorates without limit after it. A preconditioner can be too good, and it is too good exactly when it clusters components the stopping was supposed to exclude.

A preconditioner is a filter the steps cannot undo. The first shifted step is a Tikhonov solution to twelve digits, and a later step can refine within the space it opened but cannot close it. That is why the right way to choose such a preconditioner is as a regularisation parameter — and why, if the iteration’s cost matters, a shift chosen a little too large is safe and a little too small is not.

What a preconditioner treats as cheap is part of the answer. Two constructions from one derivative operator, identical on every vector outside the null space, differ by a factor of four at an offset of ten: 0.6528 against 0.1655. The difference is entirely in what each makes expensive, and the obvious construction made the null space the most expensive direction there is.

None of this contradicts the well-posed account, and it is worth saying why so it is not read as though it did. On a solve run to convergence, the shifted preconditioner at any α reaches the same converged answer; only the path differs. The step that stops mattering removed the need to stop by regularising the projected problem inside the iteration, and on that method the preconditioner question returns to its usual form. The amendments bind only where the stopping is the regularisation.

What this has not measured #

Both preconditioners here are functions of AᵀA or of a derivative, which makes their effect on the filter exactly computable and is why they were chosen. A practical preconditioner for a large deconvolution is more often an incomplete factorisation or a cheap approximation of the blur, which does not commute with AᵀA; its first step is not a Tikhonov solution, the filter-factor account does not apply, and the basis decides what a filter is is the collection’s warning about reading spectral vocabulary into a method whose basis is not the singular vectors. Whether such a preconditioner shows the same optimum, and whether it sits near the right λ², is not measured.

The shift sweep uses the oracle’s error to find each best step. A stopping rule would stop elsewhere, and at shifts below the right λ² the discrepancy principle has little to read — the first step’s residual is already small because the first step has already fitted the noise. What that rule does on the preconditioned run is unmeasured.

And the smoothing preconditioner was tested with one derivative, one kind of offset and two noise levels. A second-difference operator has a two-dimensional null space — constants and linear trends — and the completion would then have two boundary rows to make expensive; the measurement would be the same construction one dimension up.

Where this goes from here #

A preconditioner that does not commute with the operator. An incomplete factorisation of the blur, or a circulant approximation of it, changes the Krylov space in a way no filter factor describes. The measurement is whether its stopped iteration has an optimum in the preconditioner’s own parameter, and whether that optimum still tracks the oracle’s λ² as it does for the shift.

A stopping rule on the preconditioned run. The shift sweep above chose each best step against the truth. The discrepancy principle reads the residual, and on a run whose first step has already fitted the noise the residual has nothing left to say; the next measurement is how much a rule loses on each side of the optimum shift, and whether the loss is bounded above α = λ² as the table suggests it should be.

And the step count in the right unit. A step that is not a unit of work found Landweber’s parameter to be ωk rather than k. A preconditioned iteration’s parameter is a pair — shift and step — and whether a single combined quantity plays the role ωk played is the question that pairs the two measurements.