The answer the last window left

The repair the drift did not need found that a sliding window’s carried Cholesky factor, however far it had drifted, delivered a backward-stable answer after one correction from the window’s own rows: form the residual y − Aβ from the rows, solve with the carried factor, add. Every solve in that essay started from scratch — a seminormal solve with the carried factor, whose error is of order κ(A)²u, followed by the correction, which contracts it by about the same factor again. It left the natural economy as an open question: “A code solving at every step could correct at every kth, carrying the corrected coefficients forward as the starting point, and whether the correction’s benefit decays along the chain as the drift grows — or holds, because it reads the rows each time — is unmeasured.”

The economy rests on a picture that looks too obvious to test. Two consecutive windows share all but one of their rows, so their answers ought to be close, and the previous step’s corrected answer — already at Householder’s accuracy — ought to be a far better start for the next correction than a seminormal solve at κ(A)²u. It is a far worse one, on every stream with noise in it, by two to four orders of magnitude.

Two starts, one correction each #

The stream is the collinear one the preceding essay used: six integer columns that are a common base plus small independent perturbations, so that the window’s κ(A) is set by the perturbations’ size. With the smallest perturbations drawn, κ(A) is 3.2·10⁶. The window is 24 rows wide and slides a thousand steps, adding a row and removing one each time, and its factor is carried by rotations. Every fiftieth step its coefficients are compared, one by one, with the window’s exact least-squares answer computed in rationals.

Both routes do exactly one correction per step, at exactly the same cost. The fresh route forms the seminormal answer from the carried factor and the window’s cross-products, then corrects it once. The carried route corrects the previous step’s already-corrected answer once. With the response’s noise as large as the rows, the fresh route reaches a median error of 2.2·10⁻⁸ over the run and the carried route 3.7·10⁻⁵. A second correction of the fresh start reaches 1.9·10⁻¹⁰, and Householder on the same rows 3.0·10⁻¹⁰.

The preceding essay’s own figure at this conditioning is the fresh route in full, and it is the baseline the carried route has to beat. Its carried factor, uncorrected, is wrong by about 10⁻⁴; a factor recomputed from the rows does no better, because the error is the seminormal solve’s and not the factor’s; one correction brings it to about 10⁻⁸ and a second to Householder’s level. Nothing in that picture used the previous window’s answer. The question is whether using it could have saved the first of those steps.

The carried line on that figure is not unstable and does not grow. It wanders between 10⁻⁶ and 10⁻³ for the whole run, pinned there by a mechanism that the next figure makes plain.

How far the answer moves in one step #

The correction is a contraction. From a start whose error is e, one correction with the carried factor returns an answer whose error is about e times a constant of order κ(A)²u, plus the rounding of the correction itself. The constant does not care where the start came from. So the carried route’s error after one correction is the contraction times the distance from the previous window’s answer to this window’s answer, and the fresh route’s is the contraction times the seminormal error.

The window’s exact answer moves by a median of 0.79 of itself in one step, with the noise as large as the rows; a fresh seminormal solve is wrong by 1.8·10⁻⁴. The carried start is four thousand times further from the answer than the fresh one, and it stays four thousand times further after the correction: 3.7·10⁻⁵ against 2.2·10⁻⁸ is a factor of 1,700.

That the exact answer should move by most of itself when one row of twenty-four is exchanged is the part that runs against intuition, and it is the conditioning at work on the problem rather than on the arithmetic. A window with κ(A) = 3·10⁶ has coefficients determined to about κ(A) times the noise in the response; replace one row, and the noise that row carried is replaced by another draw, and the coefficients move by an amount of the same order as their own uncertainty. The two windows share twenty-three rows and their answers agree to no digit. The picture that made carrying look free is a picture of the data; the coefficients answer to the data through κ(A), and κ(A) is large.

Reduce the noise and the step shrinks with it. At noise 10⁻⁶ of the rows’ size — a response off by a unit in integers of a million — the answer moves by 0.026 of itself a step, still a hundred times the fresh solve’s 5·10⁻⁵. Across both condition numbers measured, the step is about a hundredth of the noise times κ(A) until it saturates near the answer’s own size, and a fresh seminormal solve is wrong by a twentieth to a quarter of κ(A)²u. The carried start is the nearer one when the first is smaller than the second: when the response’s relative noise is below about ten times κ(A)u. At κ(A) = 3·10⁶ that is 3·10⁻⁹. On a stream of integers of a million, the smallest noise there is — one unit — is three hundred times too large.

Where carrying wins #

Set the noise to zero and the picture reverses completely. Every window of a consistent stream has the same exact answer — the response is an exact combination of the columns — so the window’s answer does not move at all, and the previous step’s corrected answer is already the next step’s answer up to its own error. At κ(A) = 3.2·10⁶ the carried route then reaches 1.3·10⁻¹¹, against the fresh route’s 6.2·10⁻⁹ — five hundred times better, and better than Householder on the same rows, at 2.4·10⁻¹¹. At κ(A) = 3.2·10⁴ the two routes tie at the level of the rounding, 1.3·10⁻¹³ against 1.4·10⁻¹³.

Every other cell of the ratio figure is above one: 20 at the smallest nonzero noise and the smaller condition number, 436 at the larger, and between a thousand and four thousand everywhere the noise is 10⁻⁴ of the rows or more. The carried start is a real economy on exactly one kind of data, the kind whose residual is zero, and a real loss on every other.

That result has a close cousin in the gap refinement can close, where refinement at the working precision repaired a solve through a computed inverse in one step at every conditioning measured. There, as here, the step contracted its start by the error of the solve it reused. What that essay did not have to ask is where the start came from, because every solve was of a fixed system. A sequence of systems adds that question, and the answer is that a start is only as good as its distance from the new answer — which for a sequence is the sequence’s own step, not the old answer’s accuracy.

Against the sequences that did reward the last answer #

The previous answer has been measured as a start before, in sequences of linear systems, and found it wanting for a different reason. A warm start is degree zero solved a family of systems whose matrices drift smoothly and found the previous member’s answer a poor start compared with the line through the last two: the path of answers was smooth, the previous answer lagged it by one step of the path, and a line extrapolated it. A guess worth two per cent found the previous Newton step worth nothing as a guess for the next inner solve, because its scale was wrong rather than its direction.

A sliding window on noisy data has neither kind of path. Its answers do not lie along a smooth curve that a line could follow; they jump, from one window to the next, by the noise the exchanged row carried, amplified by κ(A). A line through two such answers extrapolates a random step, and a random step extrapolated is another random step roughly as large. Measured on the same stream, the start two times the last answer minus the one before it, corrected once, ends at a median 7.4·10⁻⁵ — twice the carried start’s 3.7·10⁻⁵ and three thousand times the fresh start’s. On the consistent stream the line ends at 1.7·10⁻¹¹, as good as the carried answer, because there is no path at all and a line through two copies of one point is that point.

So the sequence essays’ lesson — use the history, and fit it with the degree its path supports — has a boundary here. The history of a sliding window’s answers is not a path the next answer lies on. It is a record of how the noise in the rows went, and the next answer is as far from all of it as the next row’s noise makes it. A factorisation kept past its date is the part of that lesson that does transfer, because a factor, unlike an answer, is a property of the rows alone: the window keeps its factor for the whole run and loses nothing by it, as the factor’s own measured drift shows.

Correcting every kth step #

The preceding essay’s open question had a second half: correct only every kth step and hold the answer in between.

On the noisy stream the held answer is wrong by the whole of the drift since its last correction, which is the answer’s step accumulated: 0.79 of itself after one step, 2.6 after two to three, 3.4 at a period of ten. From a period of two on, it is not an approximation to the current window’s answer in any digit. On the consistent stream the held answer is wrong by 1.6·10⁻¹¹ at a period of two and 1.9·10⁻¹¹ at twenty-five, indistinguishable from correcting every step, because there is no drift to hold against.

So the question the preceding essay asked — “whether the correction’s benefit decays along the chain as the drift grows” — has an answer that is not about the drift of the factor at all. The factor’s drift, which stable once, and three thousand times measured at 3.9·10⁻¹⁴ after three thousand steps, is invisible in every figure here. What decays is the answer’s relevance, and it decays at the rate the window’s exact answer moves, which is a property of the data’s noise and the problem’s conditioning and not of anything the solver does.

Why the obvious picture fails, and when it holds #

The intuition that consecutive windows have close answers is correct about the fitted values and wrong about the coefficients. Two windows sharing twenty-three rows produce fitted values Aβ that agree closely on those rows, because least squares controls the residual; the coefficients β that produce them can differ by their whole size along the directions A barely sees. A correction step computes its residual from the rows and so is anchored to the fitted values, but its start is a coefficient vector, and a coefficient vector from the previous window lies far out along the ill-determined direction.

That is also why the fresh start is good. A seminormal solve with the carried factor and this window’s cross-products has its error in the ill-determined direction too, but its size is set by rounding, κ(A)²u, rather than by the data’s noise. On ill-conditioned noisy data rounding is the smaller of the two, by orders.

The removal of a row is not what the move is made of, though it is tempting to look there. The observation that cannot be removed found that deleting a row of large leverage is where a downdate’s arithmetic degrades, and a window removes one row at every step. But the move measured above is the exact answer’s, computed in rationals, and it is the same whether the factor is downdated well or badly. On this stream the largest leverage any removed row carried was 0.68, no downdate amplified by more than 2.5, and the carried factor ended 6.2·10⁻¹⁵ from its window’s Gram matrix — the same drift the earlier essays measured on their streams. The move is a fact about the data.

It holds, then, when the exact answer genuinely does not move — consistent data, or a window so long relative to its noise that the coefficients are well determined. The second case is not measured here: every window is twenty-four rows, and with the noise as large as the rows the step was 0.28 to 0.49 of the answer at 96 and 384 rows as well, so width alone does not rescue it on this stream.

What it costs, and what to do #

Both routes cost the same: one pass over the window’s rows for the residual and one pair of triangular solves. The fresh route adds the seminormal right-hand side — the window’s cross-products, which a sliding solver maintains anyway — and a pair of triangular solves, about $p^2$ more operations. At six columns that is thirty-six multiply-adds against the correction’s three hundred. Carrying saves about a tenth of the step and loses three orders of accuracy on noisy data.

The comparison that decides a real code is with the second correction, since at κ(A) = 3·10⁶ the preceding essay’s rule — one correction is enough while κ(A)³u is below one — says one is not enough, and the product here is about 3,600. A fresh start corrected twice costs two passes over the rows and reaches 1.9·10⁻¹⁰ on the noisy stream. A carried start corrected once costs one pass and reaches 3.7·10⁻⁵ there, and 1.3·10⁻¹¹ on the consistent stream, where the fresh start corrected twice reaches 1.6·10⁻¹¹. So on consistent data carrying buys exactly the second pass, and on noisy data it buys nothing and costs five orders against the two-pass route. A code that does not know which kind of data it has should pay for the second pass.

The practical rule is short. Start every step’s correction from a fresh seminormal solve with the carried factor, which the problem that arrives again would call reusing the factor and not the answer. Carry the answer only when the stream is known to be consistent — an identity being tracked, a model with no noise — and there it is worth doing, since it reaches Householder’s accuracy with one correction where the fresh start needs two. And never hold an answer between corrections on noisy data: a held answer is last window’s answer, and last window’s answer is not this one’s.

What this does not settle #

One stream family, six columns, one window width, one seed, a thousand steps; medians over twenty samples along the run. The integer construction makes the exact answers exact and makes the smallest nonzero noise one unit, so the crossover the argument predicts — noise near ten times κ(A)u — is inferred from the two quantities on either side of it and not measured at it.

The contraction constant is taken from the fresh route’s own ratio, one correction’s output over its input, and assumed to be the same for the carried start. That both routes shrink their start by the same factor is what the argument needs, and the carried route’s measured error agrees with it to about a factor of ten, not closely.

Still open: a start between the two, and a stream whose answer drifts #

A predicted start. The carried answer fails because the answer moves; the fresh answer succeeds because rounding is small. A start that updated the previous answer by the change the new row implies — a rank-one correction to β, which recursive least squares computes as a matter of course — would be as near as the fresh start on noisy data and as good as the carried one on consistent data, if the update’s own rounding is small. Whether it is, on a collinear window, is the measurement.

A stream whose conditioning changes. Every stream here is stationary. A stream that passes through a stretch of near-collinearity and out again would move κ(A) under the window, and with it both the answer’s step and the fresh solve’s error, and the solver would have to know where on the rule it stood as it went. The preceding essay asked the same question of the κ(A)³u boundary for a second correction, and it is the same measurement.