A tail from Tikhonov and a corner from truncation

The overshoot was the lead found that the gap between conjugate gradients and the two fixed filters above the answer was bookkeeping. Count the directions a filter admits, with every factor clipped to lie between zero and one, and the iteration’s lead past the top disappears — Tikhonov’s error at 1.3 of the answer went from 2.35 times the iteration’s to 0.96. The same recount did nothing below half the answer. There, matched on the clipped sum, Tikhonov’s error still ran up to 1.69 times the iteration’s, the truncated SVD’s up to 1.33, and neither number moved when the coordinate changed, because at a third of the answer the iteration has not yet begun to overshoot.

The essay named what was left as a difference in shape. Tikhonov’s factor $\sigma^2/(\sigma^2+\lambda^2)$ rolls off over two decades of σ — the smooth shoulder a second blur, narrower than the first drew as a resolution kernel with side lobes — and the iteration’s polynomial, it said, is steeper. And it proposed a direct measurement. The family

$$f_k(\lambda, p) = \frac{\sigma_k^{2p}}{\sigma_k^{2p} + \lambda^{2p}} = \frac{1}{1 + (\lambda/\sigma_k)^{2p}}$$

is Tikhonov at $p = 1$ and tends to truncation at $\sigma = \lambda$ as $p$ grows, with its half-point pinned at $\sigma = \lambda$ for every p. Slide p from one upwards, find the value at which the family matches the iteration below half the answer, and that value would say how steep the iteration effectively is.

The first half of that works better than the proposal expected. The second half does not survive contact with the iteration’s own factors, and why it does not is the more useful result.

Sharpening closes the band, and the limit reopens it #

The comparison is the one the previous two essays made, in the clipped coordinate they settled on. Six problems — Gaussian blurs 1.5, 2.5 and 4 grid points wide on a 64-point signal, each at 1% and at 0.1% noise — and twelve draws of each. Every conjugate-gradients iterate is placed by the clipped sum of its factors; the best iterate’s position is the answer’s; at each fraction of it from 0.3 to 1.3 the nearest iterate is taken, and a member of the family is placed at the same clipped sum by solving for λ. Every member’s factors lie strictly between zero and one, so its clipped sum is its sum and nothing about the coordinate favours one p over another. The number reported is the median over draws of the member’s error divided by the iterate’s.

At $p = 1$ the figure is Tikhonov’s band from the previous essay: 1.04 to 1.69 at 0.3 of the answer, pinched between 0.7 and 1.0, and slightly below one past the top. Turn the dial. At $p = 1.5$ the band at 0.3 runs from 1.00 to 1.32; at $p = 2$ from 0.93 to 1.11; at $p = 3$ from 0.89 to 1.03; at $p = 8$ from 0.85 to 1.09. The left of the picture closes quickly and then stops closing, and past about three it begins to open again — not upwards, as Tikhonov’s did, but on both sides, with the narrow blur now better than the iteration and the wide blur worse.

Read as a single number per sharpness, the widest departure from one over the stretch from 0.3 to 0.5 of the answer is 0.693 at $p = 1$, 0.320 at 1.5, 0.113 at 2, 0.106 at 3, 0.126 at 4 and 0.150 at 8. The truncated SVD, which is where the family is going, sits at 0.335 — worse than every member from $p = 2$ on and a little worse even than $p = 1.5$. So the gap below half is closed by sharpening the roll-off and not by reaching the limit of sharpening. Any p between two and four brings every problem within about a tenth of the iteration, and the floor is broad: nothing in that range is distinguishable from its neighbours by more than two hundredths.

Near the answer, between 0.7 and 1.0, the choice hardly matters. Every member is within 0.054 of the iteration there and $p = 2$ is within 0.018; truncation is within 0.089. That is the stretch in which one arc, and what each filter pays to be on it found the three filters on one curve, and a family between two of them is on it too. Past the top, from 1.1 to 1.3, every member’s widest departure is between 0.12 and 0.17, almost all of it below one, which is the reversal the clipped count produced in the previous essay: at an equal count of admitted directions past the top, any fixed filter carries less noise than an iteration that has started to overshoot.

What “below half the answer” is, measured in steps #

Before reading the sharpness off these numbers it is worth knowing what the stretch below half the answer actually contains, because the fractions hide it.

On all six problems the iterate nearest 0.3 of the answer is the first one. At 1% noise the first iterate already sits at about four tenths of the answer’s clipped sum, so the points at 0.3 and 0.4 are the same iterate; at 0.1% noise 0.4 of the answer is the second step. By 0.5 the iteration has taken between two and five steps. The answer itself is reached at step 12 on the wide blur at 1% noise and at step 60 on the narrow one at 0.1%. The whole of the region where Tikhonov misses by 69 per cent is therefore the iteration’s first handful of steps — and the first step is a filter whose shape can be written down exactly.

After k steps, conjugate gradients on the normal equations applies the filter

$$f(\sigma) = 1 - \prod_{j=1}^{k}\left(1 - \frac{\sigma^2}{\theta_j}\right),$$

where the $\theta_j$ are the Ritz values of $A^{\mathsf T}A$ after k steps — the identity a parameter that counts steps drew beside the measured factors and found the two routes agreeing until orthogonality was lost. At one step there is one Ritz value, the Rayleigh quotient of the first search direction, and the filter is

$$f(\sigma) = \frac{\sigma^2}{\theta_1}.$$

That is a ramp in $\sigma^2$. It has Tikhonov’s slope for small σ, it reaches one at $\sigma = \sqrt{\theta_1}$, and past that it exceeds one, which the clipped coordinate cuts back to one. Its half-point is at $\sqrt{\theta_1/2}$.

Drawn against σ over its own half-point, one draw of the middle blur shows what that means next to the other two. Below the half-point the iteration’s factors lie under Tikhonov’s by a factor of two — the ramp’s tail is $\sigma^2/\theta_1$ and a Tikhonov filter with the same half-point has a tail of $2\sigma^2/\theta_1$. Above it the iteration climbs to one by a factor of $\sqrt{2}$ in σ, where a Tikhonov filter crossing one half at the same place has reached two thirds. The second power, the dashed curve, is between them on both sides: its tail falls as $\sigma^4$, faster than either, and a second-power filter with the iteration’s half-point reaches 0.8 at the iteration’s corner.

That is the mechanism of the band, and it explains why p = 2 is the right neighbourhood without p = 2 being the right answer. Tikhonov lets through twice the iteration’s share of every direction below the half-point, which on these problems is noise, and keeps a third less of every direction above it, which is signal. Where the one turns into the other is the index where the answer stops being in the data located from the Picard plot, and at the first step every one of these filters has its half-point well above it. A sharper member of the family does less of both.

One filter, several sharpnesses #

The family’s p has a precise local meaning, and it is the one that settles the question. For every member,

$$\log\frac{f}{1-f} = 2p\,\log\frac{\sigma}{\lambda},$$

so half the slope of the log-odds of the factor against $\log\sigma$ is p at every height of the filter — in the tail, at the half-point and on the shoulder alike. Measuring that slope between neighbouring directions of the iteration’s own factors therefore asks directly whether the iteration has a sharpness. If it were a Tikhonov with a steeper roll-off, the slope would read the same number all the way up.

Two steps are needed before the measurement is clean. The iteration’s factors are not always monotone: past a few steps a direction whose data coefficient is small can sit well below its neighbours — the second one-draw figure below shows one at 0.7 among factors of one. No member of the family can skip a direction, so a slope taken across the skip reads a steepness that is not a shape at all. The factors are read through their monotone envelope, each one raised to the largest factor below it in the spectrum, and the skips are counted separately. On none of the six problems is there a skip before 0.7 of the answer; at 1.3 of the answer there is one on between one and ten of the twelve draws.

It does not read one number. At the answer, the iteration’s local sharpness is 1.02 to 1.03 where its factors are between two and five per cent, climbs through 1.4 to 2.1 around the half-point, and reaches 2.2 to 2.9 where they are between 65 and 80 per cent. At the first step the rise is steeper still — 1.03 in the tail and 3.7 to 4.9 on the shoulder — because the ramp has a corner. Across every problem and every fraction up to the answer the tail reads 1.01 to 1.09 and the shoulder 2.0 to 4.9.

So the iteration has Tikhonov’s slope in its tail, to within a tenth, and a sharpness of two to five on its shoulder. It is not a steeper Tikhonov. It is a Tikhonov tail joined to something close to a truncation’s corner, and the question “what p is it” has an answer only after deciding which part of the filter to ask.

Where the tail is set #

The Ritz-value formula says more than that the tail has Tikhonov’s slope. It says where. For σ below every Ritz value the product can be expanded to first order, and

$$f(\sigma) \approx \sigma^2 \sum_{j=1}^{k} \frac{1}{\theta_j},$$

which is a Tikhonov tail $\sigma^2/\lambda^2$ with $\lambda_{\text{tail}}^2 = 1/\sum_j \theta_j^{-1}$. For Tikhonov itself the tail’s λ and the half-point are the same number. For the iteration they need not be, and the ratio between them measures how much lower its tail is than the Tikhonov filter that would cross one half at the same place.

At the first step the ratio is the square root of two, 1.414 on every problem — the ramp’s tail constant is $\sqrt{\theta_1}$ and its half-point is $\sqrt{\theta_1/2}$. Afterwards it settles, and stays between 1.26 and 1.40 on every problem from the second step to 1.3 of the answer. The tail is computed from the Ritz values and the half-point from the measured factors, so the two sides of that ratio are independent routes: one reads the Lanczos tridiagonal and one reads the solution. A ratio of 1.3 means the iteration’s tail sits at $1/1.3^2$, about 0.6, of the matching Tikhonov tail at every σ below the half-point — a steady forty-per-cent reduction in what the smallest singular directions let through.

The open dots are where the corner is. The factor is exactly one at every Ritz value, and the smallest Ritz value sits between 1.4 and 1.95 times the half-point. Above it the product’s factors are all negative or small and the filter is at one to within its overshoot; below it, between the corner and the tail, is the stretch the local sharpness climbs through.

A single sharpness drifts along the run #

Asked for one number anyway, the family gives one, and it drifts.

Fitted by least squares to the enveloped factors, with λ tied to the iterate’s clipped sum, the sharpness is 2.26 to 2.29 at the first step on every problem, falls to between 1.73 and 2.00 at half the answer, and sits between 1.71 and 1.88 at the answer. It falls because the corner softens as Ritz values accumulate: with one Ritz value the corner is a kink, and with fifteen the product rounds it off over several directions. The tail, which the fit also has to accommodate, does not change.

The sharpness that matches the error is a different number and a less stable one. Where it exists — where some member of the family crosses the iteration’s error as p runs from one to twelve — it is 2.48 on the narrow blur at the first step, 1.58 on the middle one, and on the wide blur it does not exist at all: there, at the first step, every member of the family is worse than the iteration, the closest at $p = 1.5$ by 0.4 per cent. Between the first step and the answer it scatters from 1.02 to 5.3 across problems, and at ten of the forty-eight points no p matches on as many as half of the draws.

Neither number is a property of the iteration. The fitted one is a compromise between a tail that wants $p = 1$ and a shoulder that wants three or four, weighted by how many directions each part happens to contain; the error-matched one is the same compromise weighted by where the data’s content happens to sit. On the narrow blur the signal occupies more of the directions near the half-point, so the shoulder decides and the match is sharp; on the wide blur the directions near the corner carry little signal and much less of the error, and no symmetric roll-off reproduces a filter that is Tikhonov below and nearly truncation above.

The same shape, near the answer #

The first-step figure is the extreme case, and the shape persists after the corner has softened.

At step 17, on the same draw of the middle blur, the fitted sharpness is 1.92. The iteration’s tail is still under Tikhonov’s, by the factor the Ritz values predict — its tail constant is 1.35 times its half-point — and above the half-point it rises to one faster than the second power does, reaching it at about twice the half-point where the dashed curve is still short of 0.95. The picture also shows the skip that made the envelope necessary: a direction at about five times the half-point where the factor falls to 0.70 among neighbours at one. That direction’s data coefficient is small, so the Krylov space built from the data has barely found it. Tikhonov and every member of the family would have passed it whole. It is the only place in the picture where the iteration’s filter visibly depends on the right-hand side rather than on σ, and it costs almost nothing, because a direction the data barely contains is one whose recovery hardly matters to the error.

Why a family that does not describe the iteration still matches it #

The result has two halves that sound contradictory. A member at $p = 2$ matches the iteration’s error below half the answer to within 0.11 on every problem, which is what a good model would do. And the iteration has no p, which is what a bad model would imply. Both are true because the error is an integral over directions and the shape is a function of σ.

The second power errs in both directions against the iteration. In the tail its factors fall as $\sigma^4$ against the iteration’s $\sigma^2$, so it passes less of each small direction than the iteration does; on the shoulder it has reached 0.8 where the iteration has reached one, so it keeps less of each large direction. The first is less noise and the second is more bias, and on these problems at these noise levels the two net to within a tenth of zero. Tikhonov errs in only one direction on each side — more tail, less shoulder — and both of those cost error, which is why it misses by 69 per cent. Truncation errs the other way on both — no tail at all, a full shoulder — and on the wide blur, where the tail directions carry real signal, it misses by a third.

So the family’s best member is not an estimate of the iteration’s sharpness. It is the member whose two misfits cancel, and the cancellation depends on the problem. That is also why the floor is broad: between $p = 2$ and $p = 4$ the tail misfit grows and the shoulder misfit shrinks, and the sum barely moves.

What the comparison was asking #

The parameter neither knob is proposed the effective dimension as the regularisation parameter the whole field shares, and the two essays since have been refining what “the same position” means. The overshoot was the lead found that above the answer the position had to count directions, not weight. This essay finds that below half the answer no reweighting of position will make Tikhonov look like the iteration, because the difference is not how far the filter has gone but what shape it went in. A position is one number and a filter shape has at least two — here, a tail constant and a corner — so no single coordinate can match two filters whose shapes differ.

The Ritz-value formula gives the two numbers the iteration actually has. The tail is Tikhonov’s, with $\lambda_{\text{tail}}^2 = 1/\sum_j\theta_j^{-1}$; the corner is at $\sqrt{\theta_{\min}}$. A fixed filter with a Tikhonov tail and a corner — the ramp $\min(1, \sigma^2/\lambda^2)$, which is exactly the iteration’s first step — would have both, and it is a one-parameter family that nobody uses, because its λ does double duty as tail and corner, which the iteration after one step does not. An expiry date the noise does not move watched the iteration’s factors swing past one as steps accumulated; what is visible here is the other end of the same polynomial, holding a Tikhonov slope in the tail at every step while the corner above it softens.

Where the evidence runs out #

Six problems, all Gaussian blurs of one 64-point signal, and conjugate gradients on the normal equations without a preconditioner. The tail identity is exact for any operator — it is a first-order expansion of the product — but the size of the ratio of the tail to the half-point, 1.26 to 1.40 here, depends on how the Ritz values spread, and a preconditioned run that clusters them would change it. The shift had an edge, and the approximation moved it measured preconditioned runs on these problems and would be where to look. So would restarting is a filter, which wrote a restart’s polynomial with its roots at chosen Ritz values: a filter whose corner is placed deliberately rather than where the iteration’s Rayleigh quotients happen to fall.

The local sharpness is binned at ten heights and read from neighbouring directions, so on the shoulder, where the factors change by a few per cent between neighbours, individual slopes are noisy and some bins are empty on the wide blur. The claim rests on the medians and on their range across problems, and the range — 2.0 to 4.9 on the shoulder against 1.01 to 1.09 in the tail — is wide enough that the noise does not decide it.

The error-matched sharpness scattering from 1.0 to 2.8 is reported, not explained, beyond the account above. A decomposition of each member’s error into the part from directions below the half-point and the part from directions above would put numbers on the two misfits and test whether they cancel as described; it was not made.

Still open: a ramp filter, and the directions the data skips #

The ramp as a method. The first step’s filter, $\min(1, \sigma^2/\lambda^2)$, has the iteration’s tail and a corner, and one parameter. As a fixed filter chosen by the same rules as Tikhonov it would sit between Tikhonov and truncation in a way the family above does not. The prediction with a sign is that it matches the iteration below half the answer better than every member of the family — the widest departure falling under the 0.106 that $p = 3$ reaches — and that it loses the match near the answer, where the iteration’s corner has softened. The same six problems settle it, and the stopping rules would have to be re-read on it: a count that marks the edge and not the pace used the number of directions past a threshold, which for a ramp is the number of singular values above its corner.

A two-parameter fixed filter. The iteration’s filter after k steps is described to first order by two numbers, a tail constant and a corner. A fixed filter with those two — a Tikhonov tail joined to a clipped ramp at a separate corner — could be fitted to each iterate and asked whether it reproduces the error everywhere, including at the answer. If it does, the iteration’s advantage over fixed filters is entirely one of shape and none of it comes from reading the data.

The skipped directions. Past 0.7 of the answer the iteration leaves a direction behind on some draws, and by 1.3 of the answer on most of them on the narrow blur. Whether the skipped direction is always one whose data coefficient is below the noise — so that skipping it is the iteration reading the data correctly — or whether signal is ever skipped, is a count over the same runs, and it is the one place in these comparisons where a filter that depends on the right-hand side could be doing something no fixed filter can.