Columns that steer a random start

A first vector nobody can build against took the matrix built to fool a condition estimator and found that it was built against one vector. The estimator every library ships, Hager’s walk as refined by Higham, estimates $\|A^{-1}\|_1$ by starting from the all-ones vector, and a hidden column of $A^{-1}$ whose entries alternate in sign cancels against all-ones and is never visited. Started instead from a random $\pm 1$ vector, the walk escaped that construction on every seed at every size, at no cost on random matrices. And concentrating the hidden column on a few rows, to raise the chance that a random vector’s signs split evenly across them, did not hide it either: the hidden column’s own entries dominate $A^{-1}x$ on its rows, so the first sign vector the walk forms follows the hidden column’s signs and the next step goes straight to it.

Its last section named the next construction. “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 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 construction works. Each clause of the prediction is wrong in an instructive direction.

An inverse with a decoy, a hidden column and steering #

The estimator never sees $A^{-1}$; it sees products with it, computed by solves with A’s factors — the price the condition number is an amplifier put on knowing the amplification at all, since forming the inverse costs more than the solve it is meant to qualify. So the construction builds $B = A^{-1}$ directly and inverts it to get A. Its columns are: a decoy of ones, the column an all-ones walk would report; the hidden column, $\pm h$ alternating over twelve rows taken in pairs, $+h$ on the first row of each pair and $-h$ on the second, which is the largest column and the one whose 1-norm is the answer; m steering columns; and filler of 0.9 with a diagonal bump to keep B invertible.

A steering column has the same entry on both rows of a pair — a random sign for each pair, size $g$ — and nothing on the other rows. Its whole effect is on the sign vector the walk forms. On a pair of rows, $y = Bx$ is $\pm h x_1 + S$, where $S$ is what everything else contributes, and the steering columns put the same $S$ on both rows. Once $|S|$ exceeds $h|x_1|$, both rows of the pair get the same sign, and the hidden column, which is $+h$ on one and $-h$ on the other, contributes exactly zero to $B^{\mathsf T}s$ from that pair. A sign vector that agrees on every pair cannot see the hidden column at all.

The size of the steering is set by one number. With $g = \gamma h/\sqrt{m}$, m random-signed columns add up on a pair to about $\gamma h$ times a random start’s entry, whatever m is; and each steering column’s 1-norm is $\gamma/\sqrt{m}$ of the hidden column’s. So γ says how hard the steering pushes and $\gamma/\sqrt{m}$ says how large each steering column is — which, when the walk is fooled, is what it reports.

Fooled, and by exactly a steering column #

On a 48 × 48 inverse with every steering column half the hidden column’s 1-norm, the estimate on every seed is one of exactly two numbers: the truth, or 0.51 of it, which is a steering column’s norm over the hidden column’s. Nothing lands in between. When the first sign vector agrees on enough pairs to turn the walk away, the walk goes to a steering column, forms a sign vector from it that agrees on every pair — a steering column’s own signs are pair-equal by construction — and stops there, satisfied, at that column’s norm.

So the factor the estimator is fooled by is not $1/\sqrt{m}$. It is $\gamma/\sqrt{m}$, and γ is the builder’s to choose. The prediction took γ as one, the smallest steering that wins a pair half the time; but the builder can scale γ and m together and hold the factor wherever they like. The dial holds it at one half and moves m from four to thirty-four. The two clusters stay where they are; only the number of seeds in the lower one changes. LAPACK’s walk, which starts from all ones and has no random vector at all, returns 0.51 of the truth on every one of these matrices.

At a fixed factor, more columns fool more seeds #

The figure at the top of the page is the share of the hundred seeds that land in the lower cluster, with the factor fixed at 0.51. With four steering columns one random vector is fooled on 9 seeds; with nine, on 38; with sixteen, 50; with twenty-five, 64; with thirty-four, 77. The prediction said the share would fall as the steering columns’ combined sign lost to the hidden column’s — which is true at a fixed column size, and is not the trade the builder faces. Holding the factor fixed and adding columns raises γ as $\sqrt{m}$, so the steering on each pair grows and the share of random starts it wins grows with it.

Held at eight columns, the dependence on γ alone is a threshold. Below a combined size of one the steering loses most pairs and almost no seed is fooled — 1 and 3 per cent at sizes of a half and one. At one and a half it wins: 45 per cent, and 63 at two, 75 at two and a half. The earlier essay’s concentrated column traded how badly the estimator was fooled against how often, because the only lever was the hidden column itself. Steering columns are a second lever, and with two levers the builder can have both: any factor, on as large a share of seeds as there is room for columns.

The room is the limit, and it is a property of the matrix rather than of the estimator — the distinction the exact answer to a nearby problem draws between an algorithm’s failure and a problem’s. At order 48, with twelve rows taken by the pairs and a few by the decoy and filler, thirty-four columns is the most the construction holds, and it fools three random starts in four. A larger matrix holds more. Nothing here suggests the share stops rising before the columns run out.

The first step does most of it #

The mechanism is visible in the first product. With four steering columns, a random start’s first sign vector agrees on 2.3 of the six pairs on average, and the walk turns away from the hidden column at once on 5 starts in a hundred. With thirty-four it agrees on 4.3 pairs and turns away on half. The walk ends fooled more often than its first step turns away — 77 against 50 at thirty-four columns — because a walk that visits a steering column first forms that column’s pair-equal signs next, and a walk that visits the decoy forms all-plus signs, and either way the hidden column, still largest, is never looked at again.

How many pairs the first sign vector agrees on can be predicted in one line. On a pair the steering’s contribution is a sum of m terms, each the steering entry $g$ times a random $\pm 1/n$, which is close to a normal variable whose standard deviation is $g\sqrt{m}/n = \gamma h/n$; the hidden column’s contribution is $h/n$ in magnitude. The pair agrees when the first beats the second, which happens with probability $\operatorname{erfc}(1/(\gamma\sqrt{2}))$, and the expected count of six pairs is six times that.

The model is within four tenths of a pair everywhere and within a tenth from sixteen columns up: 1.90 predicted against 2.25 measured at four columns, 3.03 against 3.21 at nine, 3.70 against 3.87 at sixteen, 4.14 against 4.25 at twenty-five, 4.38 against 4.29 at thirty-four. Where it is low, it is low because the decoy and filler columns, which are the same on both rows of every pair, add a little steering of their own that the model leaves out; with few steering columns that extra is a larger share. So the threshold in the previous figure is the model’s curve read at the point where agreement on most pairs becomes likely: a combined size of about one and a half, where each pair agrees with even odds.

That last point is the difference from the earlier essay’s construction. There the hidden column won the first product because its entries dominated $y$ on its rows. Here the hidden column is still the largest column, but largest is not what the walk asks; it asks which column $B^{\mathsf T}s$ points at, and the steering columns decide $s$. An estimate that can be fooled found the estimator stopping “because it is satisfied” — no vertex looks better than where it stands — and a steering column is a vertex built to satisfy it.

A block of t vectors is t guesses #

The prediction’s last clause expected the block of two to be fooled as often as one vector. It is fooled far less often, and by a rule simple enough to state. On the fixed-factor family with nine steering columns, one random vector is fooled on 38 seeds, the block of two on 16 and the block of four on 3; $0.38^2$ is 0.14 and $0.38^4$ is 0.02. With thirty-four columns, 77, 64 and 39 against 0.59 and 0.35. Wherever the single vector is fooled on more than a third of seeds, the block of two is fooled on the square of that share and the block of four on its fourth power, each within a tenth — dashed on the figure at the top of the page.

That is what independent guesses would do. Each of the block’s random vectors is steered away with the same probability, independently of the others, and the block is fooled only when every vector is. Two columns see what one walk cannot introduced the block of two as a remedy for a construction against one fixed vector, and the earlier essay found that two random vectors behave as two guesses on random matrices. Against a construction built for random vectors, the guesses are still independent, and so the only defence left is more of them: at three random starts fooled in four, a block of four is fooled on two seeds in five, and a block of sixteen would be fooled on about one in a hundred.

Independence turns the choice of block size into arithmetic. To be fooled on fewer than a fraction δ of seeds against a construction that fools one vector with probability p, a block needs $t \ge \log\delta / \log p$ vectors. At p of three quarters and δ of one in a hundred that is sixteen; at p of a half, seven. The cost grows only with the logarithm of the safety wanted, which is cheap, and with $1/(1-p)$ as p approaches one, which is not: since $\log p \approx -(1 - p)$ near one, a construction that fools one vector nine times in ten needs a block of about forty-four for the same one in a hundred, and one that fools it ninety-nine times in a hundred needs about four hundred and sixty. A rate measured on a hundred seeds is itself only good to a few points, as one draw in twenty found for a parameter-choice rule’s catastrophes, which settled only by a thousand draws; the block sizes above inherit that uncertainty through p.

What the builder can and cannot do #

The builder controls the factor and, through the number of columns, the probability that one random vector is fooled. What the builder cannot control is independence: whatever probability p the construction achieves against one vector, t independent vectors are all fooled with probability $p^t$. So a construction can force a block estimator to be wrong with any probability below one, but only by making p close to one, and the number of steering columns that takes grows with the block size. The estimator’s defence costs t products a step; the builder’s attack costs a matrix big enough to hold the columns.

A residual check would not have caught any of this. The estimate is a lower bound on every seed — it is the norm of a column the walk actually visited — and a small residual is not a small error is the standing reminder of what a quantity that always looks plausible can hide. For a library, the measurement sharpens a choice the earlier essays left open. The all-ones walk is fooled on every one of these matrices; a single random start is fooled with whatever probability the matrix’s builder chose; a block of t random starts is fooled with that probability to the power t. The tail a sample never reaches warned that a worst case measured on random matrices says little about the matrices nobody sampled. A block with random starts is the one estimator here whose failure probability on a constructed matrix can be stated in advance from a property of the estimator, given p — and p is the one number the construction is free to push towards one.

What one construction does not show #

One family of constructions, built around a hidden column on twelve rows in six pairs, at orders 24 and 48, a hundred seeds for each setting. A hidden column spread over more pairs needs the steering to win more pairs at once, which on independent pairs should lower p for the same γ; this family does not separate that effect from the number of columns. The estimator is the block 1-norm estimator of the earlier essays, with its rule of replacing a sign vector that repeats an earlier one by a fresh random vector; how often that rule fires on these matrices, and how much of the block’s escape it accounts for, is not separated here. And the construction makes no attempt to look like a matrix anyone would solve with: whether such structure arises without being built for is the question that decides whether any of this matters outside an essay about building it.

Still open: steering against a block, and pairs that are not pairs #

A construction against the block’s independence. Every random vector here is steered independently because the steering columns’ signs are fixed and the start’s are not. A construction whose steering depends on the start cannot be built into a fixed matrix — but one whose steering columns are many enough to win almost every pair for almost every start can push p towards one. The prediction with a sign is that at order 96 with eighty steering columns at a factor of one half, one random vector is fooled on more than ninety seeds in a hundred and the block of four on more than sixty, so that the block’s escape through independence is a matter of size, not of principle.

A hidden column that is not paired. The steering works because the hidden column’s alternation is in pairs of adjacent rows, and the steering is equal within each pair. A hidden column whose signs follow a random pattern over its rows needs steering columns whose entries agree within each group of rows of the same sign — two groups rather than six pairs — and the prediction is that this makes steering easier, not harder: two groups are won by a combined size of about one, where six pairs needed one and a half.