The tail a sample never reaches

The guarantee attached to a condition estimator is one sentence long and it forbids almost nothing. Every vector the walk examines produces a lower bound on ‖A⁻¹‖₁, the estimate is the largest of them, and a maximum of lower bounds is a lower bound. That statement is true of an estimator which returns a hundredth of the truth, and of one which returns the number one on every matrix ever handed to it. As a promise about accuracy it is empty.

So the reason the routine is in LAPACK, in MATLAB’s rcond and behind the 1-norm branch of numpy.linalg.cond is not that theorem. It is a distribution: on matrices nobody built to defeat it, the estimate is usually not merely close but exactly right. That claim carries the whole reputation of the routine, it is the half an estimate that can be fooled states in a single reassuring paragraph, and it is the subject here.

A distribution has two halves and they answer to sampling in opposite ways. The centre — how often the estimate is exact — is an average over the sample, and an average is what sampling estimates well. The tail — the worst underestimate anybody found — is an extreme, and an extreme is a report about how deep the sample went. Drawing more matrices moves an average towards a limit and moves a minimum downwards without one.

Both halves can be watched at once, because the matrices come from a generator started at a stated seed and drawn in order. A sample of sixty is therefore the first sixty of a sample of four hundred, not an independent experiment beside it, so every number below is the same run read at different lengths.

The centre is settled by a hundred matrices #

Read at four lengths, the first bar of that figure moves as little as a bar can while moving at all. The estimate is exact on 78.3% of the first sixty matrices, 79.0% of the first hundred, 80.5% of the first two hundred and 83.0% of all four hundred. In counts rather than shares that is 47, 79, 161 and 332 matrices whose reported condition number was the condition number, to every digit either quantity carries.

The share therefore moves 4.7 percentage points while the sample grows by a factor of just under seven, and it moves in one direction, upwards, which is worth naming as the small piece of luck it is rather than treating as a trend: three of the four readings sit inside a band two points wide, and the fourth is the smallest sample.

Sixty matrices is a defensible sample for a share. The standard error of a proportion near four in five over sixty draws is about five points, and the reading at sixty sits within five points of the reading at four hundred, which is the arithmetic working exactly as advertised. Somebody who ran sixty matrices, wrote down “four out of five”, and stopped, would have been right.

The second bar behaves the same way and says something the first does not. The share inside ten per cent reads 88.3%, 87.0%, 87.0% and 88.3% at the four lengths — it does not even move monotonically, because it is an average of a bounded quantity and averages of bounded quantities wobble around their limits. The gap between the two bars is the population of near misses: matrices where the walk found a good column and not the best one, roughly one matrix in twenty at every sample size measured.

That is the whole of the good news, and it is genuinely good news. Four in five exactly right is a far stronger statement than the theorem supports, it is stable enough to be quoted, and it can be established from a sample a laptop produces in a second.

The worst case is a running minimum, so it can only fall #

The third bar is a different kind of number and the nesting makes the difference visible rather than arguable. The worst underestimate over the first k matrices is a running minimum over a fixed sequence, so as k grows it can only stay where it is or drop. It reads 0.746 at sixty, 0.426 at a hundred, 0.377 at two hundred and 0.377 at four hundred.

Reading the sequence of records rather than the endpoint is what makes the shape of the thing plain. Over the four hundred draws the worst case is set at matrix 1, then improved upon — in the direction that makes the routine look worse — at matrices 8, 14, 68, 73 and 189, at the values 1.0000, 0.8828, 0.7464, 0.6345, 0.4257 and 0.3772. Six records in four hundred draws, and the last two hundred and eleven matrices produced none. The tail is not a rare event that arrives at a steady rate. It is a sequence of increasingly rare events, each of which needs roughly a multiple of the sample that preceded it.

That is a general property of extremes rather than anything about this estimator, and it has a consequence which is easy to state and rarely acted on: a quoted worst case is a statement about how many matrices somebody looked at. Two authors reporting “worst underestimate 0.75” and “worst underestimate 0.38” for the same routine on the same family are not disagreeing. One drew sixty matrices and the other drew two hundred.

The rest of the distribution shows how thin the region is that the record lives in. Of the four hundred draws, 47 fall below 0.9 and only five fall below 0.5, with the five worst reading 0.3772, 0.4133, 0.4212, 0.4257 and 0.4888. The median ratio is exactly 1. A sample of four hundred buys a hundred-odd near misses, five real misses and one worst case, and the worst case is the only number in that list which cannot be pinned down by drawing more.

The size of the matrix does not decide the share #

The obvious suspicion about a stable share is that it is stable only at the size it was measured at, and that the routine degrades as the matrix grows — more columns for the walk to find the largest of, and the same handful of steps to find it in. The suspicion is reasonable, it is the reading a reader of one figure would naturally take, and it is not what the sizes say.

Measured at two hundred matrices each, at n = 4, 6, 8, 10, 12, 14, 16, 18 and 20, the exact share reads 87.5, 85.5, 80.5, 87.5, 83.5, 85.5, 83.5, 82.0 and 84.5 per cent. The band is seven points wide, the largest reading is shared by the second-smallest size and one in the middle, and the smallest reading is at n = 8 — in the middle of the range, not at the end of it. Nothing in that sequence descends.

The same sweep at four hundred matrices, which is the slider’s own five stops, reads 87.3, 83.0, 84.5, 83.8 and 86.3 per cent at n = 4, 8, 12, 16 and 20. That is a band 4.3 points wide across a fivefold change in the size of the matrix, and the largest value is at the smallest size and the second largest at the biggest one.

There is a mechanism behind the flatness and it is the same one that makes the estimator work at all. The walk is applied to A⁻¹ rather than to A, and the columns of an inverse have far more spread in their 1-norms than a Gaussian’s do, so in almost every draw there is one obvious winner and the walk finds it in a step. That spread is a property of inverting a random matrix, not of the number of columns, so growing the matrix adds columns to the search and adds separation between them at the same time. What is measured is the net of the two, and the net is nearly nothing.

The worst case over the same nine sizes behaves as badly as ever: 0.4626, 0.4082, 0.3772, 0.4457, 0.3570, 0.1721, 0.4933, 0.3703 and 0.2510. A factor of 2.9 between the best and worst readings of a quantity whose companion moved by seven points, with no order to it, from samples of identical size.

Ten seeds separate the two halves outright #

The nesting shows what happens as one sample is extended. Changing the seed shows what happens when a different sample of the same size is drawn instead, which is the question anybody quoting a number from a paper is implicitly asking.

Ten seeds, two hundred 8×8 matrices each. The exact share reads 80.5, 84.5, 82.5, 87.5, 86.0, 85.0, 85.5, 86.0, 85.0 and 88.5 per cent — a spread of 8.0 points, every reading recognisably the same statement. The worst underestimate over the same ten samples reads 0.377, 0.418, 0.396, 0.534, 0.452, 0.418, 0.664, 0.336, 0.390 and 0.191 — a spread of a factor of 3.48, from a matrix that lost a third of the truth to one that lost four fifths of it.

Two numbers computed from identical data by adjacent lines of the same routine, and one of them is reproducible to a few points while the other moves by a factor of three and a half. This is the same distinction a bound that holds with probability draws between a guarantee and a draw from it, arriving from the other side: there the bound is proved and the answer is random, and here the answer is deterministic given the matrix and the evidence about it is a draw. An estimator quoted with a worst case and no sample size has reported the seed.

Twenty times the sample buys a factor of two #

The record trajectory predicts what a much larger sample does, and the prediction can be run.

Extended to eight thousand matrices at n = 8 — twenty times the figure’s largest sample — the exact share reads 84.8%, against 83.0% at four hundred. Under two points, for twenty times the work. The worst underestimate reads 0.1842, against 0.377: the tail halves. The new records arrive at matrices 609, 1632, 3956 and 5156, at 0.3616, 0.2938, 0.1972 and 0.1842 — four more records for 7,600 further draws, where the first four hundred produced six.

At n = 20 the same extension gives an exact share of 83.7% against 86.3% at four hundred, moving this time in the other direction and by two and a half points, and a worst case of 0.1978 against 0.251. That record was set at matrix 4,747; the one it replaced had stood since matrix 162, through four and a half thousand draws that found nothing worse.

So the tail is not out of reach in principle. It is expensive in exactly the way a logarithm is expensive: each further factor costs a multiple of everything spent so far, and the multiple grows. Sampling can drive the reported worst case down as far as anybody is willing to pay for, and can never report that it has reached the bottom, because the instrument that would say so is the same instrument that keeps finding lower values.

That figure is the point of the whole section in one drawing. Its centre bar says nothing that the eight other sizes do not; its tail bar is deeper than the tail of a sample twenty times as large at a neighbouring size. Nothing about n = 14 is special. One draw out of two hundred happened to land somewhere the other seventeen hundred draws in this essay did not, which is what a maximum does and what an average never does.

The constructed matrix is not the tail of this distribution #

Every number so far is about matrices drawn at random. The matrix that defeats the estimator is not drawn, and the difference is not one of degree.

At n = 16 it returns 7.74% of the true condition number — 2.746·10² reported against a true κ₁ of 3.548·10³. That is five times below the worst of four hundred draws, and 2.4 times below the worst of eight thousand. The temptation is to read it as the far tail of the same distribution, reachable by somebody with more patience. It is not, for a reason that has nothing to do with patience: the construction works by making one column’s entries sum to exactly zero, so the dual vector the walk tests with never points at it. Perturbing any entry of that column destroys the cancellation, and a random matrix has probability zero of exhibiting it. The set is not rare within the population being sampled. It is outside it.

The ladder is the second thing sampling cannot supply. A sample produces a worst case at one size, and it is a number. The construction produces a worst case at every size along a line with no floor, and it is a statement — that no ratio exists which the estimator cannot be driven below, at a cost of five products, with its own stopping test firing. An estimate that can be fooled derives that line and shows what the walk does on its way to being wrong.

And the matrix doing it is plain. At n = 16 its entries take five distinct values — 1, ±12.92, 0.9 and 1.7 — over 256 entries: a column of ones, an alternating column, and filler columns at 0.9 with a bump on the diagonal to keep the matrix invertible. This essay’s refusal is fed the claim that the matrix which defeats the estimator has many distinct entries, and is required to fail, because the thing that makes a counterexample dismissible is the belief that it is elaborate.

The two halves of the reputation are therefore both true and they do not meet. The routine is exact on four matrices in five, at every size measured, from a sample anyone can reproduce; and it can be made arbitrarily wrong by three lines of construction whose output no sample will ever contain. A number that summarises the first says nothing about the second, and the flattering direction of the error — the condition number is an amplifier prices what that direction costs in digits — means the second is the one that reaches a caller as silence.

What this changes for anything that reads a condition estimate #

A quoted worst case needs its sample size beside it or it is not a measurement. 0.75, 0.43 and 0.38 are the same routine on the same family at sixty, a hundred and two hundred matrices. The convention this site uses for anything drawn from a generator is the same one: state the seed and state how many draws, because an answer that changes with the seed is an answer whose reported value is partly a property of the report.

A share is worth quoting and does not need a large sample. Sixty matrices settle the centre to within the five points that a proportion over sixty draws is worth. Spending four hundred to refine 83.0% from 78.3% is spending on the wrong half of the picture; the same four hundred draws spent at a different size would have said something the first sixty could not.

Do not extrapolate a tail from a sample of anything. The estimator is the clean case because the adversarial set is measure zero, but the shape recurs wherever a method is validated by drawing test cases, and randomisation does not create structure is the same observation about what a random draw contains: a sample finds what is there in proportion to how much of it there is, and a constructed matrix occupies none of the space.

Read the estimate as one-sided, at every sample size. The reported number is a lower bound on κ₁, so a large one is evidence and a small one is the absence of evidence. That asymmetry is what makes the tail the dangerous half: an overestimate in the tail would produce a spurious warning, and an underestimate produces a clean bill of health. It is the reading rank is a decision asks for of a threshold and a small residual is not a small error asks for of a residual — a reassuring number whose reassurance is about a different question.

And check whether the matrix explains the estimate before believing it. Rows differing enormously in size means κ is reporting the units, which is the units the matrix is measured in, and that costs one pass. A componentwise condition number is invariant under row scaling exactly, which is why a condition number scaling cannot move is the better quantity when the scaling is the suspect. And a caller who needs to know which of two correct formulations is in hand — the situation the basis nobody chose on purpose describes, where two valid choices are eight orders apart — has the estimate as the only cheap instrument, and should know that the instrument is exact four times in five and silent the fifth.

And say which condition number. The estimate is of the 1-norm, because the 1-norm is the one a maximum over vertices can reach; two condition numbers of one matrix is the distance between that and the number a theorem was probably stated about.

What is worth carrying #

The routine’s reputation rests on a distribution, and the distribution has been measured. Four matrices in five exactly right, at nine sizes from 4 to 20, on samples from sixty to eight thousand, with the share between 80.5 and 87.5 per cent and no trend in the size. That is a real property of a real routine and it is why the routine is shipped.

The tail of that distribution has not been measured and cannot be. Every worst case in this essay is a running minimum over a finite sample, it fell every time the sample grew, and the last extension — twenty times the draws — bought a factor of two and four new records. There is no sample size at which the falling stops, and no way to tell from inside a sample whether it has.

And the matrix that matters is not in the sample at all. 7.74% of the truth, five distinct values, five products, the stopping test firing correctly. A distribution answers the question of how often the estimator is right. It does not answer the question of how wrong it can be, and those are the two questions a caller has.