A power the spectrum does not set

The first step’s filter, kept for the whole run found a way to write conjugate gradients’ filter with two numbers. After $k$ steps the filter is $1 - \prod_j (1 - \sigma^2/ \theta_j)$ over its Ritz values $\theta_j$. Its tail is $\sigma^2 \sum_j 1/\theta_j$ and it first reaches one at the smallest Ritz value, $\theta_{\min}$. The power ramp

$$f(\sigma) = 1 - \left(1 - \frac{\sigma^2}{\theta_{\min}}\right)^{m}, \qquad m = \theta_{\min} \sum_j \frac{1}{\theta_j},$$

has exactly that tail and exactly that corner, and stands in for the whole polynomial. The power $m$ is one at the first step, where the iteration is a plain ramp, rises to about two in the middle of the run, and settles between 1.27 and 1.50 at 1.3 of the answer on all six problems.

A corner chosen without the iteration then placed the plain ramp with the iteration’s own stopping rules and found it, under GCV’s first minimum from the regularised end, within a tenth of its best on 64 draws of 72. It ended by asking whether the power could be had the same way. “If $m$ is set by the decay rate of the singular values — which for a Gaussian blur is known in closed form — the power ramp can be built from a predicted $m$ and a corner placed by GCV’s first minimum … The prediction is that $m$ predicted from the blur width alone lands within 0.1 of the iteration’s on every problem, and that the power ramp placed this way is within a tenth of its best on as many draws as the ramp.”

The second half is right, for a reason that makes the first half unnecessary. The first half is wrong, and why it is wrong says what $m$ actually measures.

What the prediction assumed #

The prediction has a mechanism behind it, and it is the textbook picture of a Krylov method. After enough steps the Ritz values converge to the extreme eigenvalues of the operator, one for each, from the largest down. If the Ritz values above $\theta_{\min}$ are the squared singular values above it, then

$$m \;\approx\; \sum_{\sigma_j^2 \,\ge\, \theta_{\min}} \frac{\theta_{\min}}{\sigma_j^2},$$

a sum the operator supplies once the corner is known. For a Gaussian blur of width $s$ samples on $n$ points the singular values fall like $\exp(-(\pi j s/n)^2/2)$, so the same sum can be written down from the blur width alone. A wider blur decays faster, the terms below the corner shrink faster, and $m$ falls toward one; a narrower blur keeps more terms near one and pushes $m$ up.

Both routes are computable and both are computed here, at the iterate nearest the answer and at 1.3 of it, on the same six problems — blurs 1.5, 2.5 and 4 samples wide, noise of one per cent and a tenth of one per cent — and the same twelve draws.

The operator does not set it #

The figure at the top of the page sets the iteration’s $m$ beside both sums, as medians over twelve draws, with the prediction’s band of 0.1 shaded around the iteration’s value. Out of twelve problem-and-fraction rows, the operator’s sum falls inside the prediction’s band of 0.1 on two and the closed form on one. Draw by draw it is worse: the closed form misses the iteration’s $m$ by more than 0.1 on 62 of 72 draws at the answer and 68 at 1.3 of it, and the computed singular values miss on 65 and 63. The worst single draw is off by 3.2.

The misses do not even go one way. On the narrowest blur the operator’s sum is far above the iteration’s $m$: 4.3 against 2.0 at the answer with one per cent noise. On the widest blur at a tenth of one per cent it is below: 0.76 against 1.32 at 1.3 of the answer — less than one, which no power ramp can have, because the smallest Ritz value sits between two squared singular values and the term that would have been one is missing. The closed form tracks the computed singular values where the blur is narrow and drifts below them where it is wide, as a formula for a blur on an unbounded line might be expected to on a matrix of sixty-four rows. Neither tracks the iteration.

So the iteration’s $m$ is not a property of the blur. It settles near 1.3 to 1.5 on problems whose singular values fall at rates seven times apart, which is the first sign that the quantity being predicted was never the one the prediction described.

Ritz values are not the spectrum, in either direction #

The assumption under the prediction is that each Ritz value above the corner is one squared singular value. Counting them tests it directly.

At half the answer this draw has taken four steps and holds four Ritz values. Eighteen squared singular values lie above the smallest of them. Each Ritz value is standing for a cluster — the leading singular values of a Gaussian blur are packed within a factor of two of each other — and the sum over the operator’s eighteen gives 7.0 where the iteration’s four give 1.7.

At 1.3 of the answer it has taken 139 steps and holds 139 Ritz values, against 51 singular values above its corner. The leading ones are found again and again: each of the dozen largest squared singular values, from one down to 0.45, four to six times, and the cluster at the very top — where several singular values lie within one per cent of each other — ten. Every one of those copies is a correct Ritz value of the computed recurrence. They are the effect an eigenvalue that arrives twice measured on a matrix with forty distinct eigenvalues, where eighty Lanczos steps returned twenty-five extra copies of thirteen of them: once a Ritz value has converged, rounding reintroduces its direction into the basis, and the recurrence converges to it again.

Turn the dial and both regimes appear on one draw. At 0.7 of the answer there are 14 Ritz values against 27 singular values above the corner; at the answer, 59 against 42. Somewhere just before the answer the count crosses from too few to too many, and nowhere along the run is it one each.

Across all seventy-two draws, at the answer, 37 hold more Ritz values than singular values above the corner and 33 hold fewer. At 1.3 of the answer 67 hold more and four fewer. The textbook picture is true of exact arithmetic run for fewer steps than there are well-separated eigenvalues. A regularising run is neither: the leading singular values of a blur are not well separated, and a run that has to reach the noise level takes more steps than there are singular values above it. The prediction assumed the one stretch of the run that this problem does not have.

What the power measures instead #

If $m$ is not a sum over the spectrum, what is it? It is a sum over the Ritz values, $1 + \theta_{\min}/\theta_2 + \theta_{\min}/\theta_3 + \dots$, and the terms fall fast: the Ritz values above the corner are spread out, and a copy of a leading singular value near one contributes $\theta_{\min}$, which is tiny. So almost all of $m - 1$ should be in the first two terms.

They carry between 52 and 94 per cent of it on every draw. The ratio of the smallest Ritz value to the next runs from 0.05 to 0.47; the iteration puts its smallest root of the polynomial well below the others, and $m$ is mostly how far below. That is a property of the polynomial conjugate gradients chooses, not of the operator it is applied to: the polynomial is the one that minimises the residual over the Krylov space, and the spacing of its smallest roots is whatever that minimisation produces on this right-hand side.

Which is also why $m$ settles. Past the answer the polynomial’s smallest root sits in the noise-dominated part of the spectrum, where the data’s coefficients are flat — the stretch of the Picard plot where the answer stops being in the data — and the minimisation there has nothing to distinguish one direction from another. The spacing it settles to — between a seventh and a quarter of the next root, at the median of every problem — is set by that flatness more than by how fast the singular values fall. Whether that can be made into a prediction is the first question below. It is not the prediction this essay was asked to test.

The second half of the prediction #

The other half asked whether the power ramp, built from a predicted $m$ and placed by GCV’s first minimum, would land within a tenth of its best as often as the ramp. That can be tested without predicting anything: place the power ramp at fixed powers, from $m = 1$ (the ramp itself) to $m = 3$, by every rule, over the same 161 corners the ramp was evaluated at.

Under GCV’s first minimum the power ramp is within a tenth of its best on 64, 64, 66, 63, 65 and 65 draws of 72 at powers 1, 1.2, 1.4, 1.6, 2 and 3. Its worst draw is 1.25 to 1.29 times its best at every power. The discrepancy principle’s median price is 1.075 to 1.087 at every power, within three hundredths of the ramp’s. The L-curve is as poor at every power as on the ramp, 1.42 to 1.57 at the median. And every one of these filters’ best is within a quarter of a per cent of the iteration’s best: the oracle ratio is 0.997 to 0.998 at all six.

So “as many draws as the ramp” holds — at the power the iteration settles to, and at every other power from one to three. The prediction needed $m$ to be predicted because it assumed the power mattered. It does not, at the corner the rules choose, for the reason the first-step essay gave for the ramp’s match near the answer: where the filters differ, the data’s coefficients are at the noise level, and letting a little more or less of a direction through trades signal against noise in nearly equal amounts. A power changes the shape of the shoulder, and the shoulder is exactly where nothing is at stake.

One difference the power does make, and why it is not the power’s #

There is one row in that figure that moves. Under GCV’s global minimum, without the repair, the ramp fails on four draws of the narrowest blur at 83, 100, 607 and 696 times its best — the far-end failure the corner essay found, where the ramp discards three quarters of the last direction and nothing else, and GCV’s value there is the last noise coefficient squared. That failure persists unchanged at $m$ = 1.2, 1.4, 1.6 and 2, and vanishes at $m = 3$: the worst draw falls to 15.4 and the share within a tenth rises from 53 to 60.

It looks like a reason to prefer a higher power. It is not the power doing it.

The corner essay gave GCV a floor: it only considers candidates that discard at least half a direction, because its ratio is undefined at a filter that discards nothing. A lone direction’s discarded share is $(1 - \sigma^2/\theta)^m$, and it reaches a half at $\theta = \sigma^2/(1 - 2^{-1/m})$: twice the squared singular value at $m = 1$, 3.41 times at $m = 2$, 4.85 times at $m = 3$. On the narrowest blur the next four squared singular values sit at 1.41, 2.30, 4.10 and 7.56 times the smallest. At $m = 1$ and 2 there are corners that meet the floor while discarding only the last direction, and the failure lives there. At $m = 3$ any corner that meets the floor is already past the fourth-smallest singular value and discards a share of all four; the one-coefficient cancellation that makes the failure cannot occur.

So the immunity is the floor’s, reached by a different route. A floor of one direction instead of half, or a grid of corners placed on the singular values, would move it again. The repair that does not depend on any of this — GCV’s first minimum walking in from the regularised end, which the minimum on the right arrived at for Tikhonov on fine grids — was already within a tenth on 64 draws at $m = 1$ and is at every power.

What this leaves of the method #

The method the prediction was building is a filter that behaves like conjugate gradients past the top, with no iteration: a corner from a rule, a power from the operator. The measurement keeps the first part and removes the need for the second. A ramp placed by GCV’s first minimum is within a tenth of its best on 64 draws of 72; a power ramp at 1.4 — the middle of the iteration’s settled range — on 66; at 3 on 65. Any of them is within two per cent of the iteration’s own best error at the median.

What the power was supposed to buy, keeping the iteration’s behaviour past the top, is a statement about filters compared at a matched position, which is how the first-step essay measured it. Placed by a rule, a filter is not at the iteration’s position; it is at the rule’s, and at the rule’s position the shape barely registers. That is the general form of the finding, and the parameter neither knob is met a relative of it earlier: a preconditioner’s cutoff changed how fast a run reached its best and not where the best sat, which stayed at the same effective dimension for every cutoff that worked. A change of shape that the best does not see is a change a rule will not see either.

It also explains a pattern in the earlier results on regularisation. One arc, and what each filter pays to be on it found every filter on a single curve near the answer; a stopping rule that follows the run it is given found the discrepancy principle’s price the same few per cent on every run; and here six powers sit within three hundredths of each other under every rule. The filters differ most where the data and the noise are most nearly equal, which is where a well-placed filter’s corner always is.

What seventy-two draws do not show #

The problems are the six used throughout: a Gaussian blur of a piecewise-smooth signal of 64 samples, white noise, twelve draws. The power is read at two points of the run; the full trajectory between them is in the first-step essay and is not re-measured. The Ritz values are those of plain conjugate gradients on the normal equations, computed from the recurrence’s own coefficients, with no reorthogonalisation; a run that reorthogonalised would have no copies and would hold at most one Ritz value per converged singular value, and the count half of this essay would read differently. Whether its $m$ would then be closer to the operator’s sum is a fair question with a likely answer — the early-run regime, where Ritz values stand for clusters, would be unchanged — that has not been measured. The fixed powers are placed on 161 corners from $10^{-8}$ to one; a finer grid near the far end would change which corners meet GCV’s floor at each power and would change the unrepaired row, not the repaired one.

Still open: the flat stretch, a reorthogonalised run, and a floor stated in directions #

What settles the spacing. The ratio of the smallest Ritz value to the next is 0.05 to 0.47, and past the answer it is where the data’s coefficients are flat. A residual-minimising polynomial on a flat stretch of the Picard plot has a known extremal shape. The prediction with a sign is that the ratio $\theta_{\min}/\theta_2$ at 1.3 of the answer is predicted by the number of singular values between the corner and the noise floor of the Picard plot — fewer of them giving a smaller ratio — to within a factor of 1.5 on five of six problems, and that the blur width enters only through that count.

A reorthogonalised run. With full reorthogonalisation there are no copies. The prediction is that at 1.3 of the answer the count of Ritz values then falls to within two of the singular values above the corner on every draw, that $m$ moves by less than 0.1 because the copies contribute almost nothing to the sum, and that the operator’s sum still misses it by more than 0.1 — which would make the clusters early in the run, and not the copies, the reason the prediction failed.

A floor stated in directions. GCV’s floor of half a direction decides where its far-end failure can live, and the cubed ramp escaped it only because the floor sits at a share rather than at a singular value. The prediction is that restricting GCV to corners at least one squared singular value above the smallest — a floor stated in directions rather than shares — removes the far-end failure at every power, and costs no draw that GCV’s first minimum gets right.