How far a carried triangular factor drifts from the data, over 2976 steps of a sliding window
At its defaults it draws how far a carried triangular factor drifts from the data, over 2976 steps of a sliding window. A window of 24 rows on 6 columns, moved one row at a time: each step folds a row in with Givens rotations and removes one with hyperbolic rotations, and the factor is never rebuilt from the rows. The rows are integers times powers of two, so AᵀA is exact in a double and the vertical axis is a distance from the answer. No single step amplifies by more than 2.72, no downdate fails, and after 2976 steps the factor is 3.87·10⁻¹⁴ from the matrix it is supposed to factor — a fitted slope of 0.554 in the step count, against a bound whose slope is 1.
window-drift is one function in lib/figures/seqstab.js —
accumulation — what a carried factor collects, and why it is a walk rather than a sum. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
A window of 24 rows on 6 columns, moved one row at a time: each step folds a row in with Givens rotations and removes one with hyperbolic rotations, and the factor is never rebuilt from the rows. The rows are integers times powers of two, so AᵀA is exact in a double and the vertical axis is a distance from the answer. No single step amplifies by more than 2.72, no downdate fails, and after 2976 steps the factor is 3.87·10⁻¹⁴ from the matrix it is supposed to factor — a fitted slope of 0.554 in the step count, against a bound whose slope is 1.
show: "partial-kept"
The arguments are the ones A correction that reads every row passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
noise 1: 6 rows 2.8, 12 rows 1.71, 18 rows 1.55, 23 rows 0.286, 24 rows 3.3·10⁻⁹; noise 10⁻⁴: 6 rows 3.07, 12 rows 2.35, 18 rows 0.902, 23 rows 0.284, 24 rows 6.06·10⁻⁹; noise 10⁻⁶: 6 rows 0.144, 12 rows 0.108, 18 rows 0.0393, 23 rows 0.0131, 24 rows 2.74·10⁻¹⁰; no noise: 6 rows 2.95·10⁻¹¹, 12 rows 1.88·10⁻¹¹, 18 rows 1.59·10⁻¹¹, 23 rows 1.58·10⁻¹¹, 24 rows 1.39·10⁻¹¹. With no correction at all, at noise 1, the error is 9.39·10⁻⁴.
show: "partial-modes"
The arguments are the ones A correction that reads every row passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
no correction: noise 1 9.39·10⁻⁴, no noise 1.17·10⁻⁸; all 24 rows: noise 1 3.3·10⁻⁹, no noise 1.39·10⁻¹¹; 6 of highest leverage: noise 1 2.8, no noise 2.95·10⁻¹¹; 6 newest: noise 1 3.32, no noise 4.77·10⁻¹¹; 6 at random: noise 1 1.52, no noise 2.4·10⁻¹¹; a rotating quarter: noise 1 1.77, no noise 1.99·10⁻¹¹.
show: "partial-bias"
The arguments are the ones A correction that reads every row passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
κ 3·10⁶, noise 1, 6 rows: drift 2.8, displacement 1.36; κ 3·10⁶, noise 1, 12 rows: drift 1.71, displacement 1.46; κ 3·10⁶, noise 1, 18 rows: drift 1.55, displacement 1.43; κ 3·10⁶, noise 1, 23 rows: drift 0.286, displacement 0.287; κ 3·10⁶, noise 0.0001, 6 rows: drift 3.07, displacement 1.24; κ 3·10⁶, noise 0.0001, 12 rows: drift 2.35, displacement 1.17; κ 3·10⁶, noise 0.0001, 18 rows: drift 0.902, displacement 0.911; κ 3·10⁶, noise 0.0001, 23 rows: drift 0.284, displacement 0.269; κ 3·10⁴, noise 1, 6 rows: drift 3.61, displacement 1.83; κ 3·10⁴, noise 1, 12 rows: drift 2.82, displacement 2.32; κ 3·10⁴, noise 1, 18 rows: drift 1.6, displacement 1.12; κ 3·10⁴, noise 1, 23 rows: drift 0.269, displacement 0.268; κ 3·10⁴, noise 0.0001, 6 rows: drift 0.129, displacement 0.0629; κ 3·10⁴, noise 0.0001, 12 rows: drift 0.0998, displacement 0.0593; κ 3·10⁴, noise 0.0001, 18 rows: drift 0.0341, displacement 0.0307; κ 3·10⁴, noise 0.0001, 23 rows: drift 0.0157, displacement 0.0149.
show: "partial-noise"
The arguments are the ones A correction that reads every row passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
no correction: 1: 9.39·10⁻⁴, 0.01: 9.44·10⁻⁴, 0.0001: 7.11·10⁻⁴, 0.000001: 3.45·10⁻⁵; 18 rows of highest leverage: 1: 1.55, 0.01: 1.57, 0.0001: 0.902, 0.000001: 0.0393; all 24 rows: 1: 3.3·10⁻⁹, 0.01: 3.42·10⁻⁹, 0.0001: 6.06·10⁻⁹, 0.000001: 2.74·10⁻¹⁰. With no noise at all: no correction 1.17·10⁻⁸, 18 rows of highest leverage 1.59·10⁻¹¹, all 24 rows 1.39·10⁻¹¹.
show: "partial-cond"
The arguments are the ones A correction that reads every row passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
23 of 24, κ 3·10⁶: 1: 0.286, 0.01: 0.287, 0.0001: 0.284, 0.000001: 0.0131; all 24, κ 3·10⁶: 1: 3.3·10⁻⁹, 0.01: 3.42·10⁻⁹, 0.0001: 6.06·10⁻⁹, 0.000001: 2.74·10⁻¹⁰; 23 of 24, κ 3·10⁴: 1: 0.269, 0.01: 0.335, 0.0001: 0.0157, 0.000001: 1.65·10⁻⁴; all 24, κ 3·10⁴: 1: 2.15·10⁻¹², 0.01: 1.65·10⁻¹², 0.0001: 1.64·10⁻¹³, 0.000001: 1.37·10⁻¹³.
What it checked while drawing
Every figure above checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
88 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
the scaled stream's coefficients are right to twelve digits at step 25 — checked 24 times
and one is enough at κ(A) = 21 — checked 3 times
two corrections reach what QR on the rows returns at κ(A) = 21 — checked 3 times
and at the same bits as with no scaling, at κ(AᵀA) = 4.2 — checked 2 times
and recomputing the factor does not at κ(A) = 202 — checked 2 times
the scaled stream's coefficients stay at rounding at κ(AᵀA) = 4.2 — checked 2 times
a column count the exact Gram matrix stays inside a double for
a column count the integer Gram matrix stays exact for
a column spread the prediction sweep draws
a correction period in whole steps
a noise level the carry sweep measures
a noise level the dial draws
a noise level the sweep draws
a number of rows the window holds
a perturbation between one unit and a tenth of the base
a reading of the window this generator draws
a refresh period inside the range the run is drawn over
a run long enough to fit a slope
a spread of scales the integers survive
a spread of scales the powers of two can carry
a stream this reading draws
a way of choosing the rows this file defines
a window the exact Gram entries stay integral for
a window wider than the columns and narrow enough to stay exact
a window wider than the number of columns
a window wider than the number of columns, or the factor is singular
and at the same bits as with no scaling, at κ(AᵀA) = 1.1·10⁶
and at the same bits as with no scaling, at κ(AᵀA) = 1.2·10¹²
and at the same bits as with no scaling, at κ(AᵀA) = 1.7·10⁴
and at the same bits as with no scaling, at κ(AᵀA) = 1.8·10¹⁰
and at the same bits as with no scaling, at κ(AᵀA) = 7.1·10⁷
and grows as the square root of the number of steps rather than in proportion to it
and one is enough at κ(A) = 2·10⁴
and one is enough at κ(A) = 2·10⁵
and one is enough while κ(A)³·u is below one
and recomputing the factor does not at κ(A) = 2·10⁴
and recomputing the factor does not at κ(A) = 2·10⁵
and recomputing the factor does not at κ(A) = 2·10⁶
and recomputing the factor leaves the error where the carried factor had it, over the run
and the conversion κ(AᵀA)·drift overstates the error by three orders or more
and the drift stays inside the bound that is linear in the steps
every Gram entry of the window is an integer a double holds exactly
matmul shapes agree
no downdate along the run fails
no downdate in the run fails
on a consistent stream the carried start wins
on a noisy stream the fresh start wins
the badge sits clear of every line
the carried start wins only where the stream has no noise
the scaled stream's coefficients stay at rounding at κ(AᵀA) = 1.1·10⁶
the scaled stream's coefficients stay at rounding at κ(AᵀA) = 1.2·10¹²
the scaled stream's coefficients stay at rounding at κ(AᵀA) = 1.7·10⁴
the scaled stream's coefficients stay at rounding at κ(AᵀA) = 1.8·10¹⁰
the scaled stream's coefficients stay at rounding at κ(AᵀA) = 7.1·10⁷
two corrections from the rows reach what Householder QR on the same rows returns
two corrections reach what QR on the rows returns at κ(A) = 2·10⁴
two corrections reach what QR on the rows returns at κ(A) = 2·10⁵
two corrections reach what QR on the rows returns at κ(A) = 2·10⁶
Against the rule
The rule does not apply to it. It factorises nothing, so there is no residual it could be withholding. That is worth stating rather than leaving blank: a site that reported the rule as satisfied by every generator would be counting mostly generators the rule never reached.
Across the library: the rule bites on 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
A correction that reads every row
A sliding least-squares window moves its answer by the update its entering and leaving rows imply and then corrects it once against all 24 rows it holds. The proposal was to read only the rows of highest leverage, a quarter of them, predicted to recover most of the full correction on a stationary stream. On every noisy stream it does the opposite: the answer ends with a relative error of order one — 2.8 at a noise level of one, where reading every row leaves 3.3·10⁻⁹ and not correcting at all leaves 9.4·10⁻⁴. Choosing the rows at random, by age or in rotation changes nothing. Leaving out one row of 24, the one of least leverage, still leaves 0.29. A correction is a Newton step whose fixed point is the answer only because the residual is orthogonal to all the columns summed over every row; read from some of the rows, its fixed point moves by the omitted rows' share of the residual, and the window settles there. Only on a stream with no noise, where every row's residual is zero at the answer, does a partial correction work.
When the problem arrives againStable once, and three thousand times
A sliding window adds a row and removes one at every step and never looks at the data again. No single step of it amplifies by more than 2.72, no downdate fails, and after three thousand steps the triangular factor in memory is 3.9·10⁻¹⁴ from the matrix it is supposed to be a factor of — six hundred times growth from a per-step bound that says nothing about chains.
When the problem arrives againThe answer the last window left
A sliding window that corrects its least-squares answer at every step could start each correction from the previous step's corrected answer instead of from a fresh solve: the two windows share all but one row. On a stream with any noise in it, that start is three orders worse. The window's exact answer moves by 0.79 of itself in one step at κ(A) = 3·10⁶, a fresh seminormal solve is wrong by only 1.8·10⁻⁴, and one correction contracts either start by the same factor — so the fresh start ends at 2.2·10⁻⁸ and the carried one at 3.7·10⁻⁵. Only on data that agree exactly does carrying win.
When the problem arrives againThe repair the drift did not need
A sliding window's carried Cholesky factor drifts 3.9·10⁻¹⁴ from its data, and multiplying by κ(AᵀA) predicts eight lost digits in the coefficients, a stream conditioned at 10¹² losing the answer, and a periodic refresh of the factor as the default repair. Measured against coefficients computed exactly in rationals, all three come out differently. On a stream made ill-conditioned by scaling, the conditioning never reaches the coefficients. On a collinear stream, a freshly recomputed factor is as wrong as the drifted one. And one correction from the window's own rows reaches Householder's accuracy for a fraction of a refresh's cost.
When the problem arrives againThe step the two rows owe
A sliding least-squares window can start each step's correction from a fresh solve or from the answer it already has. The answer it has is three orders worse on noisy data, because the exact answer moves by most of itself in a step. The proposal was a start that moves too: the previous answer plus the change the entering and leaving rows imply, two triangular solves from the factor the window keeps. Its start lands exactly where one correction of the carried answer lands — the update is that correction, computed from two rows instead of twenty-four — and one correction after it ends 2.9 to 440 times below the fresh start at κ(A) = 3·10⁶, and level with the carried answer when the data agree exactly.