Two columns see what one walk cannot

Nobody computes a condition number. Forming the inverse costs more than the solve it is meant to qualify, so every library estimates $\lVert A^{-1}\rVert_1$ from a handful of solves with the factorisation already in hand. An estimate that can be fooled took apart the routine LAPACK ships: Hager’s walk, which starts from the all-ones vector, steps to the vertex of the 1-norm ball its dual vector points at, and stops when no vertex looks better. It is exactly right on four random matrices in five. And a matrix three distinct entries wide defeats it by any factor wanted, because its largest column alternates in sign and sums to zero, so the dual vector the walk tests with never points at it.

The tail a sample never reaches then measured the two halves of that reputation apart. The share on which the estimate is exact was stable, 80 to 88 per cent at every size. The worst case was not: it fell every time more matrices were drawn, from 0.746 at sixty to 0.377 at four hundred, and the constructed matrix sat five times below anything the sample reached. The conclusion was that the tail is a property of how many matrices somebody looked at, and that the constructed matrix is outside the population a sample draws from altogether.

Both essays measured one estimator. There is another in wide use, and it is designed against exactly the weakness the construction exploits.

A walk with more than one vector #

Higham and Tisseur’s block estimator, the routine behind MATLAB’s condest and normest1, runs the same walk with $t$ vectors at once. The first is the all-ones vector, as before. The others are random ±1 vectors. At each step all $t$ are pushed through the inverse, their sign vectors are pushed back through its transpose, and the $t$ most promising vertices not yet visited become the next block. Where two sign vectors coincide, or repeat one from the step before, the duplicate is replaced by a fresh random one — so the block is never $t$ copies of one walk, and the walk cannot circle.

The design reasoning is plain from the construction’s side. A column that alternates in sign sums to zero against the all-ones vector, which is why the single walk never sees it. Against a random ±1 vector it sums to something of the size of its 1-norm divided by the square root of $n$, which is not zero, and the dual vector built from that random vector points straight at it.

Four estimators are compared: LAPACK’s walk, with its alternating extra probe; and the block estimator with one, two and four vectors. With one vector the block estimator is Hager’s walk without the alternating probe but with the replacement of repeated sign vectors, and that difference matters on the constructed matrix. Every estimate is taken the way a library takes it, from solves with the LU factors of $A$ and of $A^{\mathsf T}$, and scored against $\kappa_1$ computed from the explicit inverse.

On random matrices #

The starting point is the earlier measurement’s own picture: most of the sample exactly right, a worst case well below the truth, and the constructed matrix far below that. Every estimator below is run on the same seeded matrices, so its numbers can be read against these directly.

On the same four hundred seeded 8 × 8 matrices the earlier essay used, LAPACK’s walk is exact on 83.0 per cent and its worst estimate is 37.7 per cent of the truth, for 5.2 products with the inverse on average. The block estimator with one vector is exact on 84.0 per cent with the same worst case, for 4.4 products — slightly cheaper, since it spends nothing on the alternating probe. With two vectors it is exact on 96.5 per cent, within ten per cent on 97.5, and its worst estimate is 59.6 per cent of the truth, for 8.5 products. With four vectors it is exact on every one of the four hundred, for 16.8.

So the second vector buys thirteen points of exact share and more than halves the worst shortfall, for 1.6 times the products. The third and fourth vectors buy the remaining three and a half points and the whole of the tail, for twice as much again.

The picture does not change with size. At n = 4, 8, 16 and 32 the single walk is exact on 87.3, 83.0, 83.8 and 82.5 per cent; the block of two on 99.3, 96.5, 96.8 and 95.5; the block of four on 100, 100, 99.3 and 99.0. The earlier essay found the single walk’s exact share flat in the size, an eight-point band with no trend, and each block estimator’s share is flat in the same way, at its own level. What the second vector does is not a property of small matrices.

The tail, and whether it is still falling #

The earlier essay’s sharpest finding was about the worst case. Because the draws are nested, the worst estimate over the first $N$ matrices can only fall as $N$ grows, and for the single walk it fell a long way: a worst case quoted from a sample was a statement about the sample.

Drawn to 1,600, the single walk’s worst is 0.746 after fifty draws, 0.426 after a hundred, 0.377 after two hundred and 0.362 after eight hundred, and still 0.362 at 1,600 — a running minimum that has fallen by half and gives no sign of where it would stop. The block of two’s worst is 0.596 after the first fifty draws and is still 0.596 after 1,600. The block of four’s is exactly one until the eight-hundredth draw and 0.971 after it.

That is a different kind of tail. The single walk’s worst case keeps moving because its failures come from a continuum of near-cancellations of the kind the construction makes exact: the closer a random column comes to summing to zero against the all-ones vector, the more the walk underestimates it, and a larger sample finds a closer near-miss. The block of two’s failures need a column to be nearly invisible to two unrelated sign vectors at once, which is a much smaller target, and the worst one in 1,600 draws was already there in the first fifty. The earlier essay’s warning — do not quote a worst case without its sample size — applies to both, but for the block estimator the number the warning protects against has stopped changing.

The matrix built for the single walk #

On the constructed matrix, LAPACK’s walk returns 16.4, 7.7 and 5.1 per cent of the true condition number at n = 8, 16 and 24, following the line $1/t$ the earlier essays derived. The block estimator with two vectors returns the exact condition number on every one of twenty seeds at every size. So does the block of four.

The block of one is the instructive case. Its worst seed is exactly as bad as LAPACK’s walk — 16.4, 7.7 and 5.1 per cent — but it is exact on 80, 80 and 65 per cent of the seeds. Its only source of randomness is the replacement of a repeated sign vector, and on this matrix the walk does repeat: after its first step it is standing on the column of ones, whose sign vector is the all-ones vector again, and the replacement is a random ±1 vector that sees the alternating column. When the replacement happens to be nearly orthogonal to the hidden column, the walk stops short as LAPACK’s does. The construction was built against a deterministic walk, and a walk that is not deterministic in the one place the construction relies on escapes it most of the time. Randomness is doing something real here that randomisation does not create structure warned it cannot do in general: it is not finding structure the matrix lacks, it is denying an adversary the one fixed vector the adversary needs.

That answers what the construction proves. It is a theorem about walks that start from a fixed vector and never randomise: for any fixed number of steps there is a matrix on which they stop arbitrarily short. It is not a theorem about condition estimation. The block estimator is still an estimate — the tail of 0.596 is a matrix on which it lost forty per cent — but the construction that defeats one fixed walk does not defeat two walks one of which is random, because it has to cancel against a vector it does not know.

Why four vectors leave nothing #

The walk goes wrong when the column that holds the 1-norm is invisible to the dual vectors it tests with — when the column’s inner product with every sign vector the walk forms is smaller than the column it is standing on. For one deterministic walk that is a condition on one sign vector at each step, and a random matrix meets it, approximately, often enough to leave a sixth of the sample estimated inexactly. For a block of $t$, it is a condition on $t$ sign vectors at once, $t - 1$ of them random. If the chance that a random sign vector misses the right column is $p$, the chance that all of them do is about $p^{t-1}$ times the single walk’s, and the exact shares fit that roughly: a sixth of the matrices missed by one vector, a thirtieth by two, none of four hundred by four.

That is the same arithmetic a bound that holds with probability described for the randomised low-rank approximation, where a few extra random columns turn a failure that is merely unlikely into one that is negligible. Here the extra columns are cheap, because each is a pair of triangular solves, and the failure they guard against is the one that reports a matrix as better conditioned than it is. And as there, the randomness is honest only with its seed stated: every block estimate above is reproducible from the seed of its random columns, and an answer that changes with the seed is the standing reminder that an estimate which varies from run to run has to be reported with the run.

The alternating probe, against a random one #

LAPACK’s routine already contains a defence against cancellation, and the comparison with the block of one measures it. After its walk, xGECON pushes one more vector through the inverse: entries of increasing size and alternating sign, $x_i = (-1)^{i+1}(1 + (i-1)/(n-1))$, chosen so that a column whose entries cancel against the all-ones vector will not also cancel against this one. On the constructed matrix it does not help: the probe’s estimate, scaled by the $2/(3n)$ that keeps it a lower bound, comes out at 4.3, 8.5 and 12.6 at n = 8, 16 and 24, about half the walk’s 8, 16 and 24, so the routine reports the walk’s number and the hidden column stays hidden. That is why the earlier essays found the routine fooled with its probe in place.

The block of one has no such probe and replaces a repeated sign vector with a random one instead. On the four hundred random matrices it is exact slightly more often than LAPACK’s routine, 84.0 against 83.0 per cent, with the same worst case, and it spends 4.4 products against 5.2. On the constructed matrix it escapes on 65 to 80 per cent of seeds where the deterministic probe escapes on none. A fixed probe is a guess about what an adversary will do; a random one is a refusal to be guessed, and on this evidence it is the better use of the same product.

What the second vector costs #

The block of two spends 8.5 products with the inverse against the single walk’s 5.2, and each product is a solve with the LU factors: two triangular solves, $2n^2$ operations. On a factorisation that cost $2n^3/3$, the estimate is a small fraction of the solve either way: at n = 1,000 the block of two’s extra 3.3 products are about 6.6 million operations against the factorisation’s 670 million, one per cent. The block of four’s 16.8 products are about a twentieth of the factorisation at that size.

So the choice LAPACK made — one vector, deterministic, cheapest — buys a factor of 1.6 in the estimate’s own cost, which is a factor of a few per cent in the total, and pays for it with a fifth of all random matrices estimated inexactly and a family of matrices estimated arbitrarily badly. The condition number is an amplifier priced what an underestimate of κ costs: digits of the answer reported as trustworthy that are not. A few per cent of a factorisation is cheap insurance against that.

Where this leaves the reading of an estimate #

The earlier essays’ practical advice holds, with the estimator named. An estimate from any of these routines is a lower bound on $\kappa_1$ — every ratio measured here is at most one — so a large estimate is evidence and a small one is the absence of it, the one-sided reading rank is a decision asks of a threshold and a small residual is not a small error asks of a residual. What changes is how much absence. From LAPACK’s walk, a small estimate is consistent with the true $\kappa_1$ being 1/0.36 times larger on the random matrices drawn so far, and any multiple at all on a constructed one. From the block of two, 1/0.6 on random matrices, and the construction that defeats the single walk does not apply. From the block of four, the random sample drawn here never produced a shortfall beyond three per cent.

It also changes what a user can do cheaply. A code that calls LAPACK’s estimator and doubts it can run the estimator again on the transpose, which is the same walk on a different matrix, or run a block estimator, which is a different walk. The second is the one designed against the known failure.

What this does not settle #

Gaussian matrices and one construction. The block estimator’s own worst cases — the 0.596 at n = 8, the 0.639 and 0.722 of the blocks of two and four at n = 32 — are not analysed, and nothing here says whether a construction exists that defeats the block of two for every choice of its random vector.

The block estimator is implemented here in its essentials — the random columns, the replacement of parallel sign vectors, the choice of the $t$ best unvisited vertices, the stopping test — and not with every refinement of the published routine. Its numbers are therefore those of the algorithm rather than of any one library’s code.

Still open: the block’s own adversary, and a random start for the single walk #

A matrix built for the block of two. The single walk’s adversary cancels against a known vector. An adversary for the block estimator would have to hide a column from a random vector as well, and the natural attempt — a column nearly orthogonal to most sign vectors, of the kind that concentrates on a few entries — trades the 1-norm it can hide against how often it hides. Whether some family drives the block of two’s ratio to zero as n grows, or whether its worst case is bounded below by something like $1/\sqrt{n}$, is the question that would say whether the second vector buys a guarantee or only a better distribution.

One walk from a random start. The block of one escaped the construction on most seeds purely through its random replacement vector. A single walk started from a random ±1 vector instead of all-ones costs nothing extra and would escape it on every seed. Whether it keeps the single walk’s 83 per cent on random matrices, or loses some of it because the all-ones start is a good guess for most matrices, is one sweep and decides whether the fix for the construction is a second vector or a different first one.