A correction that reads every row

The step the two rows owe built a sliding least-squares window’s answer from the previous one. When the window drops its oldest row and takes a new one, the exact answer moves by $(A^{\mathsf T}A)^{-1}$ times the change those two rows make to the normal equations’ right-hand side, and that update costs two triangular solves with the factor the window keeps. It was not enough on its own: an update alone, corrected only every second step, sat a thousand times above the answer it could have had. One correction after it — compute the residual of all 24 rows, solve with the factor, add — ended 2.9 to 440 times below a fresh solve’s.

The essay asked whether the correction needs all 24 rows. “Between the two is a correction against the rows most likely to carry the error — the rows of highest leverage in the window … 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 quarter of the rows would make the correction a quarter of the cost, and the update and the quarter together would read eight rows a step instead of twenty-six.

It recovers none of it. On every stream with noise in it, a correction against a quarter of the rows leaves an answer worse than no correction at all, by three orders of magnitude. The reason has nothing to do with which quarter.

The window and its reference #

The streams are the earlier essays’: six columns of large integers, every column the first plus a perturbation of a chosen size, so that the columns are nearly collinear — $\kappa(A) = 3 \cdot 10^6$ at the smaller perturbation and $3 \cdot 10^4$ at the larger — and a response formed from the columns plus integer noise at a stated level relative to the rows. A window of 24 rows slides along 1,024 of them. It keeps a Cholesky factor of $A^{\mathsf T}A$ updated and downdated a row at a time, moves its answer by the two-row update at every step, and then corrects it: compute the residual $r = y - A\beta$ of the rows chosen, form $A_S^{\mathsf T}r_S$, solve with the factor, add. Every fiftieth step the answer is compared with the window’s exact coefficients, computed in rational arithmetic from the integer data, and the error is the largest relative error over the six coefficients.

This figure reads the rows of highest leverage — each row’s $a^{\mathsf T}(A^{\mathsf T}A)^{-1}a$, computed from the factor the window already has, which the factor a sparse code keeps anyway showed is free — and varies how many: 6, 12, 18, 23 or all 24.

Three orders worse than doing nothing #

At a noise level of one, reading 6 rows of highest leverage leaves a median error of 2.80; 12 rows, 1.71; 18 rows, 1.55; 23 rows, 0.286. Reading all 24 leaves $3.30 \cdot 10^{-9}$. Not correcting at all leaves $9.39 \cdot 10^{-4}$. So every partial correction measured is worse than none, and the last row is worth nine decades: from 23 rows to 24 the error falls from 0.286 to $3.3 \cdot 10^{-9}$.

The noise level barely matters until it is very small. At $10^{-4}$ the partial errors are 3.07, 2.35, 0.902 and 0.284 — still of order one — against $6.06 \cdot 10^{-9}$ for all 24. At $10^{-6}$ they are 0.144, 0.108, 0.039 and 0.013, still ten million times the full correction’s $2.7 \cdot 10^{-10}$. Only with no noise at all do they come down, to $3.0 \cdot 10^{-11}$, $1.9 \cdot 10^{-11}$, $1.6 \cdot 10^{-11}$ and $1.6 \cdot 10^{-11}$ — level with the full correction’s $1.4 \cdot 10^{-11}$.

The leverage was not the problem either. Choosing the 6 newest rows leaves 3.32 at noise one, 6 at random 1.52, and a rotating quarter — the rows whose index falls in the step’s residue class modulo four, so that every row is read once in four steps — 1.77. With no noise every one of them lands between $2.0 \cdot 10^{-11}$ and $4.8 \cdot 10^{-11}$. Which rows are read changes the error by a factor of two. Whether all of them are read changes it by eight orders of magnitude, and whether there is noise by eleven.

Where a partial correction points #

A correction is one step of Newton’s method on the window’s least-squares problem. With $G = A^{\mathsf T}A$ and the current answer $\beta$, it adds $d = G^{-1}A^{\mathsf T}(y - A\beta)$. At the exact answer $\beta^\ast$ the residual $r^\ast = y - A\beta^\ast$ is orthogonal to every column — that is the definition of the least-squares answer, the right angle the projection and the right angle measured to $10^{-16}$ — so $A^{\mathsf T}r^\ast = 0$, $d = 0$, and the exact answer is the correction’s fixed point.

Read from a subset $S$ of the rows, the correction adds $G^{-1}A_S^{\mathsf T}(y_S - A_S\beta)$ instead. At the exact answer that is $G^{-1}A_S^{\mathsf T}r_S^\ast$, and it is not zero. The sum $A^{\mathsf T}r^\ast$ vanishes because the rows’ contributions cancel, and a subset of them does not cancel. So the partial correction’s fixed point is not the answer: it is wherever $A_S^{\mathsf T}r_S$ vanishes, and the window, corrected every step, settles there.

The displacement can be measured directly: take the exact answer, apply one partial correction to it, and see how far it moves. Across all sixteen noisy cells — two conditionings, two noise levels, four subset sizes — the window’s median error is within a factor of 2.5 of that displacement, and on nine of them within a factor of 1.3. At $\kappa(A) = 3 \cdot 10^6$, noise one and 23 rows, the displacement is 0.287 and the window sits at 0.286. The window is not drifting. It has converged, to the wrong fixed point, and stays there.

The size of the displacement is $G^{-1}$ applied to the omitted rows’ share of $A^{\mathsf T}r^\ast$, which is to say the residual those rows carry, amplified by the inverse of a Gram matrix whose condition number is the square of $3 \cdot 10^6$. On a stream with noise of the size of the data, the omitted rows’ residual is of the size of the data too, and nine to twelve orders of amplification take it far past the size of the answer — which is why the error saturates at order one rather than growing further. A relative error of one is an answer of the wrong size altogether, and every noise level down to $10^{-4}$ produces one.

The fixed point is the subset’s own answer #

The displacement has a simpler description than the formula, and it is worth measuring rather than deriving. A correction from rows $S$ with the whole window’s Gram matrix as its step is a linear iteration, $\beta \leftarrow \beta + G^{-1}A_S^{\mathsf T}(y_S - A_S\beta)$, and since $A_S^{\mathsf T}A_S$ is a part of $G$ the iteration contracts: its limit is the $\beta$ that makes $A_S^{\mathsf T}(y_S - A_S\beta)$ vanish, which is the least-squares answer of the rows in $S$ alone. A window corrected from a subset is solving a smaller problem — the subset’s — and solving it well.

So the drift should be the distance from the subset’s answer to the window’s, and both can be computed exactly in rationals from the integer data. At $\kappa(A) = 3 \cdot 10^6$ and noise one, the 23-row subset’s answer is 0.303 from the window’s, and the window sits at 0.286; the 18-row subset’s is 1.63 away and the window at 1.55; the 12-row subset’s 2.37 and the window 1.71. At noise $10^{-4}$, 0.283, 0.868 and 2.47 against 0.284, 0.902 and 2.35; at $\kappa(A) = 3 \cdot 10^4$, 0.0158, 0.0363 and 0.115 against 0.0157, 0.0341 and 0.0998. On all nine the window is within a factor of 1.4 of the subset’s own answer. Leaving out the row of least leverage is asking for the least-squares fit of the other 23. The observation that cannot be removed found the quantity that governs taking one row out of a fit, $1 - h$ for a row of leverage $h$, as both a factorisation’s breakdown condition and a statistician’s warning, and one minus a leverage is a subtraction wrote the deletion’s effect on the answer as the omitted row’s residual divided by $1 - h$ and carried through $G^{-1}$. A small leverage makes that denominator close to one; it does not make the move small, because the move’s size is set by the residual and by $G^{-1}$, and here $G^{-1}$ carries a condition number of $10^{13}$.

That is also why choosing rows by leverage, which sounded like the careful choice, is no better than choosing them at random. Leverage ranks rows by how much each pulls the fit; the subset’s answer differs from the window’s by how much the omitted rows pull, and on noisy collinear data even the gentlest pull, amplified that much, moves the answer by a sizeable fraction of itself. The quarter of highest leverage omits the three quarters of lowest, and three quarters of small pulls add to a large one.

No noise forgives everything #

The exception is exact. On a stream with no noise, every window’s rows are consistent: there is a $\beta$ with $y = A\beta$ exactly, and at it every row’s residual is zero, not merely their weighted sum. Then $A_S^{\mathsf T}r_S^\ast = 0$ for every subset, the partial correction’s fixed point is the answer, and the only difference between reading 6 rows and 24 is how fast the window gets there — which, step after step, it does. The answer the last window left met the same divide from the other side: carrying the previous step’s answer forward won only on data that agreed exactly, because only there did the exact answer stand still.

It is a sharp line rather than a gradual one. Between no noise and noise $10^{-6}$ the 18-row correction’s error goes from $1.6 \cdot 10^{-11}$ to $3.9 \cdot 10^{-2}$, nine and a half decades, while the full correction’s moves from $1.4 \cdot 10^{-11}$ to $2.7 \cdot 10^{-10}$. Any residual at all, amplified by $G^{-1}$, is too much.

One row is not optional #

The better-conditioned stream softens this and does not remove it. At $\kappa(A) = 3 \cdot 10^4$ the full correction reaches $10^{-12}$ to $10^{-13}$, and leaving out the single row of least leverage leaves 0.269 at noise one, 0.335 at $10^{-2}$, $1.6 \cdot 10^{-2}$ at $10^{-4}$ and $1.65 \cdot 10^{-4}$ at $10^{-6}$ — falling with the noise now, because the amplification is a hundred times smaller and the displacement no longer saturates, but nine orders above the full correction at every level.

Leverage cannot rescue a single omission because leverage measures how much a row moves the fit, and the displacement is the omitted row’s residual moved by the inverse Gram matrix. A row of low leverage with an ordinary residual still contributes $a\,r^\ast$ to a sum that has to cancel exactly. Influence is decided before the data showed that leverage is a property of the design and not of the response; a correction’s target is a property of the response, row by row.

Three ways to economise, and the one that does not exist #

A correction against every row at every step costs 24 row reads a step. There are three ways to read fewer. Read none, and the update’s own rounding is never removed: $9.4 \cdot 10^{-4}$ at noise one. Read all of them less often, as the step the two rows owe measured: correcting every second step leaves $7.9 \cdot 10^{-5}$ between corrections, twenty thousand times the every-step error, because the update’s rounding returns after a single unaided step. Or read some of them every step, as here, and the window solves a different problem: 0.29 to 3.3. The second is the least bad and the third is the worst, worse than doing nothing, because the first two leave the right answer’s error uncorrected while the third replaces the answer.

The rotating quarter shows that reading every row eventually is not the same as reading every row at once. Over four steps it reads all of them, and its error is 1.77. Each step moves the answer toward one quarter’s answer, the next step toward another’s, and the window chases four different fixed points in turn without ever being asked to satisfy all the rows at the same time. The cancellation that defines the answer happens inside one sum, and a sum split across steps has an answer that moves between its parts.

What the window was asking for #

Along the stream at noise one the three corrections never cross. All 24 rows hold the error between $4 \cdot 10^{-11}$ and $1.7 \cdot 10^{-7}$; no correction lets the update’s rounding sit between $1.3 \cdot 10^{-4}$ and $5.1 \cdot 10^{-3}$; 18 rows hold it between 0.145 and 6.85. The partial correction’s error is not accumulating — it is as large at the hundredth step as the thousandth — which is what a displaced fixed point looks like and what a drift does not.

So the earlier essay’s cost comparison was the wrong way round. The update reads two rows and is cheap and insufficient; the correction reads every row and that is what it is for. It is the step that checks the answer against all the data the window holds, and the repair the drift did not need found the same single correction from the window’s own rows reaching Householder’s accuracy because it read them all. A cheaper correction has to find its economy elsewhere — less often, as the earlier essay measured and found costly too, or in cheaper arithmetic for the residual — but not in fewer rows.

What one stream family does not show #

One family of streams, collinear integer rows with a single response, at two conditionings and five noise levels, with a window of 24 rows over six columns. A window much wider than its column count holds more rows per unknown, and a quarter of a wider window is still many rows; the cancellation in $A^{\mathsf T}r^\ast$ is still exact only over all of them, but the displacement from omitting a few would be relatively smaller. The noise here is independent from row to row; noise correlated along the stream would make neighbouring rows’ residuals cancel partly among themselves, and a correction against the newest rows might do less badly. The error is the largest relative error over the six coefficients against an exact reference, so it reports the worst coefficient; on these streams the coefficients are of similar size and the worst is representative. And the subsets are chosen by leverage, age, chance or rotation; a subset chosen by the size of each row’s current residual would be a different rule, though its fixed point would still be a subset’s answer.

Still open: a residual that is cheaper, and a window that is wider #

A residual computed in lower precision. A correction’s cost is reading every row and forming the residual. Computed in single precision and accumulated in double, the residual costs less to form and still sums over every row. The prediction with a sign is that a full correction with a single-precision residual ends within a factor of ten of the double-precision one at $\kappa(A) = 3 \cdot 10^4$ and more than a hundred times above it at $3 \cdot 10^6$, where the residual’s own rounding, amplified by $G^{-1}$, is the larger term.

A wider window. With 96 rows over the same six columns, the omitted rows’ share of $A^{\mathsf T}r^\ast$ is a smaller fraction of a sum with more terms. The prediction is that a correction reading 72 of the 96 rows still ends at least a thousand times above the full correction at noise one and $\kappa(A) = 3 \cdot 10^6$, because the displacement shrinks only like the square root of the omitted rows’ count while the amplification stays at the square of the conditioning.