The copies cost steps, not the filter

A power the spectrum does not set wrote conjugate gradients’ filter past the answer as a ramp raised to a power, $1 - (1 - \sigma^2/\theta_{\min})^m$ with $m = \theta_{\min}\sum_j 1/\theta_j$ over the Ritz values $\theta_j$, and tested the prediction that $m$ could be read off the operator: the same sum taken over the squared singular values at or above the iteration’s own corner. It could not. The operator’s sum missed the iteration’s $m$ by more than 0.1 on 65 draws of 72 at the answer, by up to 3.2, and in both directions.

Behind the miss it found two departures from the picture the prediction relied on — one Ritz value for each squared singular value, converging from the top down — and they pull opposite ways. Early in the run there are fewer Ritz values than singular values above the corner, each standing for a cluster of them; four Ritz values against eighteen at half the answer on one draw. Late in the run there are more: 139 against 51 at 1.3 of the answer on the same draw, because the leading singular values were found four, six and ten times over. The essay could not say which of the two had broken the prediction, and it predicted with a sign how to tell. With full reorthogonalisation there are no copies. At 1.3 of the answer the count of Ritz values should then fall to within two of the singular values above the corner on every draw; $m$ should move by less than 0.1, because a copy of a leading value contributes almost nothing to the sum; and the operator’s sum should still miss by more than 0.1. If all three held, the clusters and not the copies were the reason.

Two of the three hold. The one that fails is the count, and it fails in the direction that answers the question anyway.

The same iterate, computed without copies #

Conjugate gradients applied to the normal equations of a blurring matrix is a short recurrence: each step uses the previous two directions and forgets the rest. In exact arithmetic the directions it forgets stay orthogonal to the new ones by construction. In floating point they do not. An eigenvalue that arrives twice measured the mechanism on Lanczos: once a Ritz value has converged, rounding reintroduces a trace of its direction into the basis, the trace grows, and the recurrence converges to the same eigenvalue a second time — a correct Ritz value of the computed recurrence that duplicates one it already holds.

The same iterates can be computed another way. Golub–Kahan bidiagonalisation builds an orthonormal basis for the same Krylov space, one vector at a time, and the iterate after $k$ steps is the least-squares solution over the first $k$ basis vectors. Reorthogonalise each new vector against every earlier one, explicitly, and no direction can come back. The projected matrix is a small bidiagonal $B_k$, and its squared singular values are the Ritz values of the run. In exact arithmetic this and the short recurrence are one method producing one sequence of iterates; in floating point the second is what the first would have been if orthogonality had held.

Both are run here on the problems the earlier essay used: a Gaussian blur 1.5, 2.5 or 4 samples wide on sixty-four points, with noise of one per cent or a tenth of one per cent, twelve draws of each. Each run’s position is the sum of its clipped filter factors, “the answer” is the iterate with the least error, and 1.3 of the answer is the iterate whose position is nearest 1.3 times the answer’s. That is the position at which the earlier essay counted 139 Ritz values against 51.

Without copies, still not one each #

The copies are gone. On no draw does the reorthogonalised run hold two Ritz values on one squared singular value; the short recurrence holds a median of between eight and 108 copies at 1.3 of the answer, depending on the problem. But the count does not land on the diagonal either. It is within two of the singular values above the corner on 49 draws of 72, and more than two short on 23 — five short at the median on the narrowest blur at one per cent noise, and nine short on one draw of the widest blur.

So the prediction’s first clause fails, and it fails toward the other departure. The earlier essay saw too few Ritz values early in the run and too many late, and supposed that, without the second effect, the count past the answer would be about right. Without the second effect the first one is still there at 1.3 of the answer. A Ritz value that stands for a cluster does not resolve into one Ritz value per member just because the run has gone on long enough to reach a given position. On one draw of the narrowest blur at one per cent noise, thirty-nine squared singular values lie above the corner, the first twelve of them within a factor of two of each other, and thirty-four steps of a reorthogonalised run hold thirty-four Ritz values: five short, and every one of the five inside a cluster.

That is not a failure of the method. A Ritz value converges to an isolated eigenvalue at a rate set by the gap to its neighbours, and a cluster of squared singular values within a few per cent of each other has gaps the run has no reason to resolve: its iterate is already accurate in every direction the cluster spans. The filter factor of each member is one to plotting accuracy whether the run has one Ritz value on the cluster or several.

What the copies cost #

If the copies are not what made the count wrong, what were they doing?

They were costing steps. At one per cent noise the two runs reach the answer in the same number of steps on every problem — 15.5, 19 and 12 at the median — because the answer comes early, before any Ritz value has converged far enough for rounding to bring it back. Past the answer they part: 44.5 against 35.5 steps to 1.3 of it on the narrowest blur, 43 against 27 on the middle one. At a tenth of one per cent noise the runs are longer and the copies arrive before the answer: the short recurrence needs 60.5 steps to reach it on the narrowest blur where the reorthogonalised run needs 39, and 145 steps to reach 1.3 of the answer on the middle blur where reorthogonalisation needs 36 — four times as many.

And the steps buy nothing. The best error over the run is the same both ways, to within 1.4 per cent on every draw and to the fourth digit on most. A copy is a step the short recurrence spends re-finding a direction it already has, in a basis that has quietly stopped being a basis; the iterate meanwhile moves exactly as it would have, more slowly. A step that is not a unit of work measured the same trade between Landweber’s iteration and conjugate gradients — the same best answer at step 1,778 instead of step 20 — and the lesson carries over in a weaker form: a step count describes a run’s position only when every step adds a new direction.

Whether reorthogonalisation is worth it is a separate question, and on these problems it is close. Each reorthogonalised step costs a pass over every earlier basis vector, twice — work that grows with the step number, where the short recurrence’s does not — and the two products with the blurring matrix are the same. For a dense matrix of sixty-four rows, counting multiplications and additions, thirty-six reorthogonalised steps cost about as much as fifty-five short ones, so the hundred and forty-five short steps the middle blur needs cost two and a half times as much as the reorthogonalised run that replaces them. For a large sparse matrix the balance moves toward the short recurrence, and the standard compromise, reorthogonalising only against the Ritz vectors that have converged, is the first question below.

When the copies arrive #

The steps the copies cost are not spread evenly over the six problems, and where they fall says something about when loss of orthogonality matters to a regularising run at all. At one per cent noise the short recurrence holds no copies at the answer on the median draw of any of the three blurs: the answer comes after twelve to nineteen steps, and in that time no Ritz value has converged far enough for rounding to bring its direction back. By 1.3 of the answer it holds a median of eight, fifteen and seven. At a tenth of one per cent the answer itself comes later — 60, 43 and 20 steps on the short recurrence — and the copies are already there when it arrives: a median of twenty on the narrowest blur and sixteen on the middle one. By 1.3 of the answer the short recurrence holds 92, 108 and 25 of them.

That is the arithmetic orthogonal is a number put in general form: the loss of orthogonality is a quantity that grows with the work done, and it matters once it is no longer small against the quantity being computed. A run stopped at the answer on noisy data is short enough that the copies never arrive, and on these problems the two runs then return the same iterate at the same step. A run on cleaner data, or a run allowed past its answer, is long enough to pay for them. The first step’s filter, kept for the whole run and a corner chosen without the iteration both read the filter at and past the answer, which is exactly the stretch where the step count stops meaning what it says.

Keeping the vectors and losing the bound found the eigenvalue side of the same distinction: a restarted Lanczos run whose residual bound became meaningless while its eigenvalues stayed correct to rounding. Here the iterate stays correct and the step count becomes meaningless. In both, what loss of orthogonality damages is the bookkeeping around the answer, not the answer.

The power the copies did not carry #

The second clause was that the copies carry almost nothing of $m$. The argument is in the sum’s terms: $m$ is $\theta_{\min}$ times the sum of reciprocal Ritz values, and a copy of a leading squared singular value near one adds about $\theta_{\min}$ — a few thousandths, at the corners these runs reach.

At the medians it holds. Per problem the two runs’ median $m$ at 1.3 of the answer agree to within 0.1 on five problems of six — 1.50 against 1.50, 1.46 against 1.47, 1.41 against 1.38, 1.40 against 1.37, 1.23 against 1.32 — and the sixth, the middle blur at a tenth of one per cent, differs by 0.17. Draw by draw it does not hold: 46 draws of 72 fall inside the band, and the worst is 0.49 apart.

The reason is not the copies’ contribution to the sum, which is as small as argued. It is that the two runs reach “1.3 of the answer” at different iterates. The position is a sum of filter factors, and two runs that arrive at the same sum by different paths can arrive with their smallest Ritz value in a different place relative to its neighbours. The earlier essay found that almost all of $m - 1$ lies in the ratios of the smallest Ritz value to its two nearest neighbours, and that the smallest ratio runs from 0.05 to 0.47. A quantity made of the spacing at the bottom of the Ritz spectrum is sensitive to which step the measurement is taken at, and the two runs take different steps. Across a problem’s twelve draws the scatter cancels; on any one draw it does not.

So the power is a property of the polynomial the minimisation chooses at a given position, as the earlier essay concluded, and not of the copies. The copies change which step lands at that position, and so which polynomial is being read.

The sum still misses #

The third clause is the one the whole test was for.

It does. At 1.3 of the answer the operator’s sum, computed at the reorthogonalised run’s own smallest Ritz value, misses that run’s $m$ by more than 0.1 on 62 draws of 72 — on all twelve of the narrowest blur at one per cent and of the widest at one per cent, on eight to ten of the others. The misses go both ways, as before: 2.63 against 1.50 on the narrowest blur, where the sum counts eighteen singular values packed near the corner as eighteen terms near one; 0.82 against 1.41 on the widest, where the smallest Ritz value sits between two squared singular values and the sum loses the term that would have been one. At the answer the picture is the same, with misses on 64 draws.

With copies removed, every disagreement between the sum and the iteration is a disagreement between one Ritz value standing for a cluster and the cluster’s members counted one by one, or between a Ritz value sitting between two singular values and a sum that assumes it sits on one. Those are the clusters. The copies were real, they cost the short recurrence up to four times the steps, and they had nothing to do with the prediction failing.

A dial along one run #

The dial shows the two runs agree for as long as they can. At half the answer both have taken four steps and hold the same four Ritz values, against eighteen squared singular values above the corner; at 0.7 of it they have taken fourteen and fifteen steps and still agree to the eye. At the answer the short recurrence has taken 59 steps and holds eighteen copies, while the reorthogonalised run has taken 39 and holds none — 39 Ritz values against 42 singular values above its corner. At 1.3 of the answer the short recurrence has taken 139 steps and holds 89 copies; the reorthogonalised run has taken 55 steps, holds 55 Ritz values against 57 above its corner, and its $m$ is 1.41 where the short recurrence’s is 1.33 and the operator’s sum at the same corner is 2.00.

Every Ritz value on the lowest row is a single value standing on the ticks; the clusters show as ticks with no dot directly over each of them. Nothing about the reorthogonalised row is irregular. It is simply what a Krylov space of this dimension resolves of a spectrum this crowded.

What the test settles, and what it leaves #

The earlier essay’s conclusion survives with its cause narrowed. The power of conjugate gradients’ filter past the answer is not a property of the operator, and the reason is that Ritz values stand for clusters of singular values, not for singular values one each — a statement about Krylov spaces in exact arithmetic, which a reorthogonalised run approximates to rounding. The copies that loss of orthogonality adds are a cost in steps. They change which iterate sits at a given position, and so change the power read there on any one draw, but not on the median of a problem.

Three things the test does not show. Every problem here is a dense blur on sixty-four points, where reorthogonalising against the whole basis costs about as much as the products and the run can never take more steps than there are points. It does not show how restarting or a hybrid method’s projected penalty interact with copies. And the scatter of $m$ draw by draw is attributed to the two runs’ different steps by the argument above, and not by a measurement that fixes the step and compares the two polynomials directly.

Still open: copies removed for less, and the spacing measured at one step #

Selective reorthogonalisation. Reorthogonalising only against the Ritz vectors that have converged — the directions rounding brings back — removes copies at a fraction of the cost of full reorthogonalisation, and the semi-orthogonality it maintains is known to keep the projected problem’s Ritz values accurate. The prediction with a sign is that on these seventy-two draws it reaches 1.3 of the answer within two steps of full reorthogonalisation on every draw, with no copies, while reorthogonalising against fewer than one vector in five on the median step of the tenth-of-a-per-cent problems.

The same step, both ways. If the draw-by-draw scatter in $m$ is the two runs reaching the position at different steps, comparing them at the same step should remove it until the first copy appears. The prediction is that at equal step counts the two runs’ $m$ agree to within 0.01 on every draw up to the step at which the short recurrence acquires its first copy, and diverge only after it — so that a copy, while it carries none of the power, changes it at once by moving the smallest Ritz value.

The flat stretch, still. The earlier essay’s open question about what sets the spacing can now be asked of a run with no copies to confuse it. The prediction is that the reorthogonalised run’s ratio of its two smallest Ritz values at 1.3 of the answer is predicted, to within a factor of 1.5 on five problems of six, by the number of squared singular values between its corner and the noise floor of the data’s Picard plot, where the answer stops being in the data.