A first vector nobody can build against

Two columns see what one walk cannot measured the estimator behind MATLAB’s condest, which walks over the vertices of the 1-norm ball with two vectors at once, the first all ones and the second random. On the matrix built to fool the single walk — whose inverse has a hidden column alternating in sign, so that it cancels against the all-ones vector the walk starts from — the block of two was exact on every seed, where LAPACK’s walk reported five per cent of the truth at size 24. On random 8 × 8 matrices it was exact on 96.5 per cent where the single walk was exact on 83.0, at 1.6 times the products.

The essay noticed what the block of one, the single walk with the block algorithm’s bookkeeping, was doing on the construction: it “escaped the construction on most seeds purely through its random replacement vector” — the random sign vector the block algorithm draws when a walk would otherwise repeat itself. That suggested a cheaper fix. “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.”

Four estimators, one change #

The estimators are the earlier essays’. LAPACK’s walk, which an estimate that can be fooled measured and built the construction against: one vector, a walk over vertices $\pm e_j$, an alternating probe at the end, and no randomness at all. The block algorithm with one vector, started from all ones, which differs from LAPACK’s walk in having no probe and in drawing a random sign vector whenever its sign pattern repeats. The same with its first vector a random sign vector instead of all ones, which is the only change this essay makes. And the block of two.

Every estimate is the condition number of a matrix in the 1-norm — its norm, computed exactly, times the estimated norm of its inverse — and every product with the inverse or its transpose is a solve with the factorisation the library already has, which is why the count of products is the cost that matters: the factorisation is paid for, and every product beyond it is the estimate’s own price.

On random matrices, nothing is lost #

The figure at the top of the page is the sweep the earlier essay asked for. On 400 seeded Gaussian matrices of size 8, LAPACK’s walk is exact on 83.0 per cent, the walk from all ones on 84.0, the walk from random signs on 86.5 and the block of two on 96.5. On 200 of size 16 the four are 83.5, 83.5, 83.0 and 96.0. The random start’s products are 4.3 at both sizes, against 4.4 from all ones: the first vector’s sign pattern changes nothing about how long the walk lasts.

So the all-ones vector is not a good guess, or at least not a better one than a random sign vector. That is less surprising than the earlier essay’s caution made it sound. The first step of the walk computes $y = A^{-1}x$ and moves to the vertex the sign of $y$ points at; for a Gaussian matrix the all-ones vector is one sign vector among $2^n$, with nothing about the matrix to favour it, and a random sign vector is another. The advantage all ones has is that it is the same every time — reproducible, and therefore buildable against.

The exact share is the centre of the distribution; the tail is where an estimator is trusted or not, and the tail a sample never reaches found the single walk’s worst case falling every time more matrices were drawn. The earlier essay found the single walk’s worst case still falling at 1,600 draws while the block of two’s had stopped at 0.596 after fifty, and it read that as the difference between a heavy tail and a bounded one. The two single walks’ tails sit on top of each other. After 1,600 draws of size 8 the walk from all ones has seen a worst ratio of 0.377 and six draws below a half, the walk from random signs 0.324 and eight; at size 16 it is the other way round, 0.301 and eleven from all ones against 0.348 and twelve from random signs. The worse tail changes sides between the two sizes, which is what two draws from the same distribution do.

On the construction, the escape is every seed #

The construction itself is where the two starts differ, and the dial shows how. At size 16 the walk from all ones is exact on 35 of forty seeds and returns 0.077 of the truth on the other five — the decoy column’s norm, a factor of the size below. Its escapes are the random replacement vector at work: the walk from all ones stalls on the decoy, its sign pattern repeats, and the vector drawn to replace it is random and does not cancel the hidden column. On the five seeds where the replacement is not drawn in time, nothing rescues it. At size 8 it is fooled on seven seeds of forty, at 24 on eleven, at 32 on six and at 48 on none.

The walk from random signs is exact on every one of the forty seeds at every size from 8 to 48. It never stands on the vector the construction cancels against, so there is no stall for a replacement to rescue. LAPACK’s walk, which has neither a random start nor a random replacement, returns 0.164, 0.077, 0.051, 0.038 and 0.025 of the truth at the five sizes — the construction’s whole factor, every time.

So the earlier essay’s suggestion holds, and more completely than its own measurement implied: the block of one’s escape was partial because its randomness arrived late, and moving the randomness to the first vector makes it total.

Building against a random start #

A construction that defeats a fixed vector is a construction against that vector. A random vector cannot be built against in that way, but it might be built against in probability: a matrix whose hidden column is missed by most random sign vectors would fool a random start on most seeds.

The natural attempt follows from why the alternating column hides. It hides from all ones because its entries cancel against a vector of equal signs. A hidden column on only k rows, with entries alternating in sign there and zero elsewhere, still cancels against all ones; against a random sign vector it cancels exactly when the random signs on its k rows split evenly, which happens with probability $\binom{k}{k/2}/2^k$ — one half for k = 2, 0.27 for k = 8, 0.16 for k = 24. The trade is then between how badly the estimator is fooled, which needs a hidden column with a large norm and so many rows, and how often, which needs few.

The construction works against LAPACK’s walk at every k: it returns 0.607 of the truth with the hidden column on two rows and 0.051 with it on all twenty-four, the trade the paragraph above describes. The cancellation model predicts that a random start would be fooled on half the seeds at k = 2 and on a sixth at k = 24. It is fooled on none. Over 100 seeds at every even k from 2 to 24, the random start’s worst estimate is exact.

Why the hidden column cannot hide from the first product #

The model was wrong about which vector the hidden column has to cancel against. The walk does not compare its starting vector with the columns; it computes $y = A^{-1}x$, takes the sign vector $s = \operatorname{sign}(y)$, and moves to the column $j$ with the largest $|(A^{-\mathsf T}s)_j|$. The column has to cancel against $s$, and $s$ is not random. It is the sign of a product in which the hidden column itself takes part: $y$ contains the hidden column times the starting vector’s entry in that position, and the hidden column is the largest thing in the matrix. So on the hidden column’s rows $y$ takes the hidden column’s own signs, up to one overall sign, and $s$ points straight at it.

From all ones the same arithmetic hides it, because the construction chose its other entries so that every row sum is positive: $y$ is then a positive vector, $s$ is all ones, and the hidden column sums to zero against it. That choice is a choice about the all-ones vector specifically. A random sign vector multiplies the hidden column’s entry by $\pm 1/n$ and the filler’s by a sum of random signs, and the hidden column, being largest, wins. The figure measures the result: at the first dual step the hidden column’s pull is at least 1.80 times the strongest other column’s with the column on two rows, rising to 395 times on all twenty-four, and it is the same on every seed because changing the seed only changes an overall sign.

That is a statement about this family, not a theorem about random starts. A construction that fools a random start would have to make $\operatorname{sign}(A^{-1}x)$ orthogonal to the hidden column for most x, which means the sign of $y$ on the hidden column’s rows has to be decided by something other than the hidden column — by columns larger than it, whose own norms the walk would then report. Whether such columns can be arranged so that their norms stay below the hidden one while their signs still dominate is the open question at the end of this page.

What the second vector buys #

The earlier essay’s question was whether the fix for the construction is a second vector or a different first one. It is a different first one: a random start escapes on every seed at every size, at the single walk’s cost of 4.3 products. The block of two escaped too, at 8.5.

What the second vector buys is the distribution. On random matrices of size 8 the block of two is exact on 96.5 per cent where either single walk is exact on 84 to 86, and its worst case over 1,600 draws stopped at 0.596 where both single walks went below 0.33. That is a better estimator, and it costs twice the products; it is not a cure for the construction, because the construction never needed curing by more than one random vector.

That separates two reasons a library might choose the block estimator that the earlier essays ran together. One is robustness against matrices built to fool the walk, which a random first vector provides for nothing. The other is accuracy on ordinary matrices, which costs products and which the second vector really does buy: ten points of exact share, and a tail that stops falling early. Two columns see what one walk cannot measured the second and attributed some of it to the first; the attribution belongs to the random start.

And a block whose first vector is random too #

The block of two keeps all ones as its first vector, and with the measurements above that vector is doing nothing a random one would not. Replacing it is the same one-line change, and it can be measured on the same draws.

With both vectors random, the block of two is exact on 98.3 per cent of the 400 random matrices of size 8, against 96.5 per cent with all ones first, for 8.7 products against 8.5. Over 1,600 draws the two are 97.9 and 96.9 per cent; at size 16, on 400, 97.0 and 96.8. So two random vectors are a point or two better than all ones and one random vector, never worse at these sizes, and the difference is about the size of the draws’ own noise at size 16. The worst cases do not separate: 0.739 against 0.596 after 400 draws of size 8, then 0.524 against 0.596 after 1,600, the same crossing the single walks showed.

The single walks say why the difference is small. Where the walk from all ones and the walk from random signs return different estimates — 83 of the 400 matrices of size 8 — the random start is the more accurate on 43 and the all-ones start on 40. Neither vector is a better first guess; they are two guesses, and a block of two random vectors is two independent guesses where all ones and a random vector are also two, one of them the same every time. On random matrices that sameness is worth nothing either way. On a constructed matrix it is the whole weakness.

This is the same observation the randomised methods make from the other direction. A bound that holds with probability is about a low-rank approximation whose guarantee comes from its random test vectors, and Hutchinson’s trace estimator, which counting what cannot be looked at measured, probes with exactly the random sign vectors this walk now starts from. In both the randomness is what makes a statement about every matrix possible. In the condition estimator it buys no statement — the estimate is still only a lower bound, which can still be far off on an unlucky draw — but it removes the one matrix a fixed walk could be handed on purpose.

Reproducibility, the cost the shares do not show #

The one thing a random start does cost is that the estimate is no longer a function of the matrix alone. Two runs on the same matrix with different seeds return the same estimate wherever both are exact, and can return different ones elsewhere. On the 400 matrices of size 8 the walk from all ones and the walk from random signs return different estimates on 83 — about one matrix in five — and on 41 of the 200 of size 16, and every one of those is a matrix on which at least one of them is wrong. A library that seeded its estimator from the clock would report a condition number that changes between runs on exactly the matrices where it is least trustworthy.

A fixed seed restores reproducibility and keeps the immunity, because the construction is built against a vector and not against a seed: a fixed pseudo-random sign vector is a vector nobody building a matrix knows. The variation that comes with a seed measured the same trade for randomised methods generally — a seed fixes which random object was drawn — and here the trade is unusually cheap, because nothing about the estimate’s accuracy depends on which sign vector was drawn.

What three families do not show #

Random Gaussian matrices of size 8 and 16, the alternating construction at five sizes, and one family of concentrated constructions at size 24. A random start’s immunity is measured against those constructions and not proved against all; the argument above explains why the concentrated family fails and not why every family must. The estimators are run with the block algorithm’s iteration limit of five and its replacement rule; LAPACK’s own walk has a different stopping rule and an alternating probe, and moving its first vector to random signs is a change to a different routine that is not measured here. And the comparison is in the 1-norm throughout, the norm these estimators exist for.

Still open: a construction that steers, and a block that starts random #

Columns that steer the first product. The hidden column wins the first product because it is the largest column. A family of steering columns, each smaller than the hidden one but together large enough to decide the sign of $A^{-1}x$ on the hidden column’s rows — for instance columns whose entries are equal on each pair of rows the hidden column alternates over, so that every sign vector they produce cancels the hidden column — would make the walk’s first sign vector orthogonal to the hidden column whatever x was. The prediction with a sign is that m such columns fool a random start by about $1/\sqrt{m}$, on a share of seeds that falls as the steering columns’ combined sign loses to the hidden column’s on some pair of rows, and that the block of two is fooled by the same construction on about the same share.

The tail of the block, at larger sizes. The block of two’s worst case stopped falling at fifty draws of size 8 in the earlier essay and fell to 0.524 here once both its vectors were random and 1,600 matrices were drawn. Whether the block’s tail is bounded at all, or only falls more slowly than the single walk’s, needs the running worst over tens of thousands of draws at several sizes, and a sample that size is what the tail a sample never reaches warns can still be too small.