How close Hager's estimate is to the true κ₁, over 200 seeded 8×8 matrices
At its defaults it draws how close hager's estimate is to the true κ₁, over 200 seeded 8×8 matrices. Five bars. The estimate is exactly the true condition number on 81% of the sample and inside ten per cent on 87%; the worst underestimate in the whole sample returns 38% of the truth. The last bar is the matrix built to defeat it, at 7.7%, well below anything the random sample reached.
estimate-spread is one function in lib/figures/condest.js —
condition estimation — the number a library prints, and the matrix it flatters. 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.
Five bars. The estimate is exactly the true condition number on 81% of the sample and inside ten per cent on 87%; the worst underestimate in the whole sample returns 38% of the truth. The last bar is the matrix built to defeat it, at 7.7%, well below anything the random sample reached.
show: "start-shares"
The arguments are the ones A first vector nobody can build against passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
On seeded Gaussian matrices, 400 of size 8 and 200 of size 16: the share of matrices on which each estimator's 1-norm condition number is exact, with the mean number of products with the inverse or its transpose beside each bar. At size 8: LAPACK's walk 83.0 per cent for 5.2 products, one walk from all ones 84.0 per cent for 4.4 products, one walk from random signs 86.5 per cent for 4.3 products, block of two 96.5 per cent for 8.5 products; At size 16: LAPACK's walk 83.5 per cent for 5.3 products, one walk from all ones 83.5 per cent for 4.4 products, one walk from random signs 83.0 per cent for 4.3 products, block of two 96.0 per cent for 8.5 products.
show: "start-tail"
The arguments are the ones A first vector nobody can build against passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
On seeded Gaussian matrices of size 8 and 16, the smallest ratio of estimate to true condition number among the first 50, 100, 200, 400, 800 and 1600 draws. At size 8, after 1600: from all ones 0.377 with 6 draws below a half, from random signs 0.324 with 8; At size 16, after 1600: from all ones 0.301 with 11 draws below a half, from random signs 0.348 with 12. The start that has the worse tail at size 8 has the better one at size 16.
show: "start-fooling", n: 16
The arguments are the ones A first vector nobody can build against passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The construction whose inverse has a decoy column of ones and a hidden column alternating in sign, at size 16. On each of forty seeds of the walks' random replacement vectors: the walk from all ones returns 35 exact estimates and is fooled to 0.077 on the other 5; the walk from random signs is exact on all forty. LAPACK's walk, which has no random vector, returns 0.077.
show: "start-concentrated"
The arguments are the ones A first vector nobody can build against passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The inverse has a decoy column of ones and a hidden column with k nonzero entries of alternating sign, as large as the construction allows. LAPACK's walk returns 0.607 of the truth at k = 2 and 0.051 at k = 24. A model in which a random start misses the hidden column whenever its signs split evenly over the column's k rows predicts misses on 50 to 16 per cent of seeds. Measured over 100 seeds at every k, the random start's worst estimate is exact.
show: "start-pull"
The arguments are the ones A first vector nobody can build against passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
For the size-24 construction with the hidden column on k rows: the magnitude of the hidden column's entry in z, the transpose applied to the first sign vector, over the largest other entry. From all ones it is exactly zero at every k, so the walk never turns to the hidden column. From random signs the smallest value over 100 seeds is 1.80 at k = 2 and 395 at k = 24: above one on every seed, so the first step goes straight to it.
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.
18 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 t1 estimate is a lower bound — checked 3 times
a block of between one and n vectors
a first vector the walk knows
a multiplier the construction supports
a sample large enough for the shares to mean something
a size the construction is drawn at
a size the sample can afford
an even number of nonzero entries in the hidden column
an even size, so the alternating column sums to zero
and not on all of them
and the constructed matrix below the worst the sample found
LU is for square matrices
the constructed inverse is invertible
the estimator returns the exact condition number on most random matrices
the lapack estimate is a lower bound
with a worst case in the sample below the truth
Against the rule
It draws a decomposition and prints its residual. It calls
condEstimate1, condTrue1,
and every figure above carries the badge — which residualcheck verifies by looking
for it in the emitted SVG rather than by finding the call that builds one. A badge that is
constructed and then left out of the body is the failure that check exists for.
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 first vector nobody can build against
The matrix built to fool a condition estimator is built against one vector, the all-ones vector its walk starts from, and the block estimator escaped it by adding a second, random one. Starting the single walk from random signs instead escapes it on every one of forty seeds at every size from 8 to 48, for the same 4.3 products, and loses nothing on random matrices — 86.5 per cent exact at size 8 against 84.0 from all ones, with tails that cross between sizes. The obvious way to build against a random start, a hidden column on few rows whose signs a random vector cancels half the time, fails on every seed: the hidden column writes itself into the walk's first product and turns the walk towards it. What the block of two's second vector buys is ten points of exact share, not the escape.
Regularisation, and the answer that is chosenOne draw in twenty
Sixteen draws gave generalised cross-validation a worst case of 12%. A thousand draws at each of five noise levels give it a second answer on four to six in every hundred, ten to seven million times worse than the oracle, while its median stays among the best of five rules. The quasi-optimality criterion, told nothing either, never costs more than 1.41 in five thousand draws. The share settles by a thousand draws, and letting the search look further down more than triples it.
Orthogonality, measuredThe basis nobody chose on purpose
A method that eliminates a constraint has to pick a basis for its null space, and every basis is correct. Their condition numbers are eight orders apart, the reduced problem inherits the square, and the choice is usually made by a one-line rule nobody thought of as a numerical decision.
Two errors, and whose fault they areThe tail a sample never reaches
Hager's estimator is exactly right on four random matrices in five, and that share is stable — between 80.5 and 87.5 per cent across nine sizes. The worst underestimate is not stable at all: it falls every time more matrices are drawn, from 0.746 at sixty to 0.377 at four hundred, and the matrix built to defeat the estimator sits five times below anything four hundred draws found.
Two errors, and whose fault they areTwo columns see what one walk cannot
The condition estimator every library ships walks from the all-ones vector, and a matrix whose largest column cancels against that vector hides from it: at n = 24 it reports five per cent of the truth. The block estimator behind MATLAB's condest walks with two vectors, the second random. On the same matrix at three sizes it is exact on every one of twenty seeds. On four hundred random 8 × 8 matrices it is exact on 96.5 per cent where the single walk is exact on 83.0, and its worst case, 0.596, is reached in the first fifty draws and not lowered by the next 1,550. The single walk's worst was still falling at 1,600. Four vectors are exact on all 400.