The step the two rows owe

The answer the last window left asked where a sliding least-squares window should start each step’s correction. The window keeps a triangular factor of its 24 rows, updated as a row enters and downdated as one leaves, and corrects its answer once per step by one pass of residual against the rows it holds. Two windows a step apart share all but one row, so the previous step’s corrected answer looked like the natural start. On any stream with noise in it, it was the worst one: at κ(A) = 3·10⁶ the window’s exact answer moved by 0.79 of itself in a single step, a fresh seminormal solve was wrong by only $1.8 \cdot 10^{-4}$, and one correction contracted either start by the same factor, so the fresh start ended at $2.2 \cdot 10^{-8}$ and the carried one at $3.7 \cdot 10^{-5}$. Only when the data agreed exactly, and the answer did not move, did carrying win.

Its last section proposed a start between the two. 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 the coefficients, 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, was the measurement.

Two rows carry the whole change #

A window’s answer β solves $A^{\mathsf T}A\beta = A^{\mathsf T}y$. Slide the window: row $a_t$ enters with response $y_t$, row $a_s$ leaves with $y_s$. If $\beta_o$ solved the old window exactly, its normal-equations residual on the old rows was zero, and on the new rows it is exactly what the two changed rows contribute:

$$A_{\text{new}}^{\mathsf T}(y - A_{\text{new}}\beta_o) = a_t\,(y_t - a_t^{\mathsf T}\beta_o) - a_s\,(y_s - a_s^{\mathsf T}\beta_o).$$

One solve with the new window’s factor turns that into the new answer:

$$\beta_{\text{pred}} = \beta_o + R^{-1}R^{-\mathsf T}\big[a_t r_t - a_s r_s\big],$$

with $r_t$ and $r_s$ the two rows’ residuals at the old answer. The identity is nothing more than the normal equations written twice: the old answer satisfied them on 24 rows, 23 of those rows are still there, so whatever the new window’s normal equations fail by at the old answer must come from the one row that arrived and the one that left. In exact arithmetic $\beta_{\text{pred}}$ is the new window’s exact answer. It costs two inner products and two triangular solves — it reads two rows, where a correction reads all twenty-four. In floating point it inherits the old answer’s error and adds its own rounding, and on a window with κ(A) in the millions a triangular solve with R is a solve with a matrix whose square is badly conditioned.

The measurement runs the collection’s collinear stream: rows of six nearly parallel integer columns, a response that is a fixed combination of them plus noise of a stated size relative to the rows, a window of 24 rows sliding over a thousand steps. At every fiftieth step the three answers — fresh, carried, predicted, each corrected once — are compared with the window’s exact rational answer, and the median over the run of the largest relative coefficient error is reported. The predicted start is carried from step to step, like the carried answer, and moved by the update at each one.

Better than both starts #

At κ(A) = 3.2 · 10⁶ and noise as large as the rows, the predicted start ends at $3.3 \cdot 10^{-9}$ — below the fresh start’s $2.2 \cdot 10^{-8}$ by a factor of seven, and below the carried answer’s $3.7 \cdot 10^{-5}$ by ten thousand. At noise $10^{-2}$ the same: $3.4 \cdot 10^{-9}$. At $10^{-4}$, $6.1 \cdot 10^{-9}$ against $1.8 \cdot 10^{-8}$; at $10^{-6}$, $2.7 \cdot 10^{-10}$ against $5.6 \cdot 10^{-9}$. And on the consistent stream, where the answer does not move, $1.4 \cdot 10^{-11}$ — the carried answer’s $1.3 \cdot 10^{-11}$, where the fresh start is stuck at $6.2 \cdot 10^{-9}$. The predicted start takes the better of the two on every stream, and on every noisy one it is better than the better of them.

The worry was the update’s rounding, and it is not what decides the result. Turn the dial to columns a hundred times further apart, κ(A) = 3.2 · 10⁴, and every route is corrected almost to the same place: the predicted and fresh starts end within a factor of 1.4 of each other at every noise level, $2.2 \cdot 10^{-12}$ against $2.7 \cdot 10^{-12}$ at noise 1. What separates the starts is how much work the one correction has left to do, and at a hundred times better conditioning a correction does nearly all of it from any start.

The update is a correction #

The starts themselves explain the ordering, and one coincidence in them is not a coincidence. The fresh solve starts at $1.8 \cdot 10^{-4}$ on noisy streams, the rounding of a seminormal solve at κ(A) = 3·10⁶. The exact answer moves by 0.79 to 1.2 of itself in a step, so an answer merely carried starts that far away. The updated start lands at $3.7 \cdot 10^{-5}$ at noise 1 — and so does the carried answer after its correction. At every noise level and at both conditionings, the update’s start and the carried answer’s corrected value agree to within a tenth: $7.5 \cdot 10^{-5}$ and $7.5 \cdot 10^{-5}$ at noise $10^{-4}$, $2.4 \cdot 10^{-6}$ and $2.4 \cdot 10^{-6}$ at $10^{-6}$.

They agree because they are the same computation. A correction forms the residual of the whole window at the current answer and solves with R. If the current answer solved the previous window, its residual on the 23 shared rows contributes nothing to the normal equations — the old window’s normal equations were satisfied — and the whole of the correction comes from the two rows that changed. The update computes exactly that, from those two rows, without touching the other 22. So the update is one correction’s worth of progress, taken from the two rows that owe it, and the predicted route gets that correction for the price of two inner products and then spends its one real correction on top of it.

That also says why it lands where it does and no further. One correction contracts any start by about the same factor — $10^{-4}$ here, set by how much the seminormal solve squares κ — so every route’s final error is its start times that factor. The fresh route starts at $1.8 \cdot 10^{-4}$ and ends at $2.2 \cdot 10^{-8}$; the carried route starts at the move, about one, and ends at $3.7 \cdot 10^{-5}$; the predicted route starts at $3.7 \cdot 10^{-5}$ and ends at $3.3 \cdot 10^{-9}$. The ordering of the starts is the ordering of the ends.

A run, step by step #

The medians are not hiding a mixed picture. Along the whole run at noise 1, the carried route sits between $10^{-6}$ and $10^{-3}$, the fresh route between $10^{-9}$ and $10^{-7}$, and the predicted route below the fresh one at nearly every sampled step, by a factor that wanders with the stream. The predicted route does not drift away: stable once, and three thousand times found the window’s factor itself drifting slowly over thousands of steps, and the predicted answer, corrected at every step against the rows themselves rather than against the factor’s memory of them, carries none of that drift.

What it costs, and what it buys #

Counting the work per step as passes over the window’s 24 rows — each correction is one, forming a fresh right-hand side is one — the carried route costs one pass and ends at $3.7 \cdot 10^{-5}$; the predicted route costs one pass plus two rows and ends at $3.3 \cdot 10^{-9}$; the fresh route costs two passes and ends at $2.2 \cdot 10^{-8}$; two corrections from a fresh start cost three passes and end at $1.9 \cdot 10^{-10}$, and a Householder QR of the whole window reaches $3.0 \cdot 10^{-10}$. The update does not beat a second correction. It buys one: at the cost of the cheapest route it ends below the next one up, and a code that can afford a second pass per step should spend it correcting the predicted answer rather than a fresh one.

A correction cheaper than the problem priced the classical form of this economy, Sherman and Morrison’s update of a solved system for a rank-one change, and found that exact algebra is not the same as an accurate update: the update inherits whatever error the old answer carried and can amplify it. Here what it inherits is the previous answer’s distance from satisfying the previous window, which one correction per step keeps at one correction’s error; the update’s rounding then adds nothing the next correction does not remove.

The update cannot run alone #

If the update is a correction computed from two rows, it is tempting to let it do the corrections: update at every step, and correct against all 24 rows only every tenth. The previous essay measured the carried answer held between corrections and found the drift ruinous, because a held answer does not move while the data do. An updated answer moves.

It moves, and it does not stay accurate. At κ(A) = 3·10⁶ and noise 1, correcting every step gives $3.3 \cdot 10^{-9}$; correcting every second step, sampled between the two corrections, gives $7.9 \cdot 10^{-5}$ — the carried answer’s level, twenty thousand times worse. Every fifth step, every tenth, every twenty-fifth and every hundredth give $8.3 \cdot 10^{-5}$, $1.1 \cdot 10^{-4}$, $3.9 \cdot 10^{-4}$ and $5.6 \cdot 10^{-5}$. The error does not grow with the period, but it is at its ceiling after a single unaided step. At noise $10^{-4}$ the picture is the same. On the consistent stream the update runs alone happily — $1.4 \cdot 10^{-11}$ at every step, $2.3 \cdot 10^{-11}$ every tenth, $4.8 \cdot 10^{-11}$ every twenty-fifth — because there the answer does not move and the update has nothing to compute.

This fits the account above exactly. The update’s start lands at one correction’s error from a start that was off by the move, $3.7 \cdot 10^{-5}$ here, and without a following correction that is where it stays. The next update starts from that and lands there again: the error is set by the move and the conditioning at every step, not accumulated from the steps before, which is why it neither grows nor shrinks with the period. The update is worth a correction only as a start for a correction. As a replacement for one it is worth the carried answer, no more.

Why the obvious picture was half right #

The proposal’s picture had two halves. It was right that the update would be as good as carrying on consistent data: the move is zero, the update adds nothing, and both routes end at $1.3$–$1.4 \cdot 10^{-11}$. It was right, more strongly than it predicted, about noisy data. What it did not predict is why: the update is not “near the fresh start” in the way a well-conditioned estimate is near the truth, it is one full correction ahead of the carried answer, and a start one correction ahead ends one correction’s contraction below. At κ(A) = 3·10⁶ that contraction is four orders of magnitude, which is why the predicted route passes the fresh one; at 3·10⁴ it is so strong that no start matters.

A warm start is degree zero and a fit wins where the steps were few found, for a sequence of solves along a path, that a start built from the history — a line through the last two answers, a fitted polynomial — could beat the last answer when the path was smooth. The window’s path is not smooth: the answer jumps by most of itself in a step, which is why the line through the last two answers, tracked in the same run, ends no better than carrying — $7.4 \cdot 10^{-5}$ against $3.7 \cdot 10^{-5}$ at noise 1. The update is not an extrapolation of the path. It is the path’s next step computed from the data that moved it.

What a streaming code should do #

Put together, the measurements give a short procedure for a window that keeps its factor current. At every step, compute the two changed rows’ residuals at the answer in hand, move the answer by the update, and correct it once against the window’s rows. That costs one pass over the window, the same as correcting the carried answer, and it ends a factor of three to twenty below correcting a fresh solve, which costs two passes. If a second pass is affordable, spend it on a second correction of the same answer rather than on a fresh right-hand side. And never let the update stand in for the correction: the error it leaves when unaided is the carried answer’s, from the first unaided step.

The procedure needs nothing the window does not already keep. It needs the factor, which it updates and downdates anyway; the answer, which it has; and the two rows, which it has just read. What a rebuild is worth priced the other maintenance a long-running sequence of solves faces — how often to rebuild what the sequence reuses, a period set by what a rebuild costs — and on this stream, where the factor stays accurate for thousands of steps without one, the rebuild never comes due, which leaves the correction’s starting point as the only per-step decision and the update as the cheapest good answer to it.

The one place the procedure gains nothing is a well-conditioned window. At κ(A) = 3·10⁴ every start is corrected to within a factor of 1.4 of every other, and a code could keep whichever is cheapest to form. The advantage lives exactly where the correction’s contraction is weakest, which is where a streaming least-squares code needs it.

One stationary stream, one window width #

One stream family — six nearly parallel integer columns — at two conditionings, five noise levels and one window width. The response’s noise is Gaussian and stationary; a stream whose conditioning changes along the way, the previous essay’s second open question, would move the contraction factor from step to step, and whether the predicted route’s lead survives a stretch of near-collinearity is not measured.

The update is carried from step to step and never refreshed. Its error does not grow over a thousand steps here, because every step’s correction is against the rows; with corrections skipped, the section above found the error pinned at the carried answer’s level rather than growing, over periods up to a hundred steps. The repair the drift did not need found the window’s factor itself surviving three thousand steps without a refresh, which is what lets every one of these routes keep using it.

Still open: updating without correcting, and a stream whose conditioning moves #

A correction that reads only some of the rows. The update reads two rows and a correction reads all 24, and the section above found the update alone insufficient and one full correction after it enough. Between the two is a correction against the rows most likely to carry the error — the rows of highest leverage in the window, which the factor a sparse code keeps anyway showed a code already has. Whether a correction against a quarter of the rows, after the update, recovers most of the full correction’s contraction is the measurement, and the prediction with a sign is that it recovers most of it on a stationary stream and little of it where the leverage moves.

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 the correction’s contraction. The predicted route’s advantage is a product of that contraction and its start; whether it holds its lead through the stretch, or loses it to the update’s rounding where κ is largest, is the case a real sensor stream presents.