Promotion buys rank, not safety

The probe that refuses becomes the column put two cheap ideas together. An adaptive range finder grows an orthonormal basis for a matrix’s range a column at a time and stops when ten fresh random probes, projected off the basis, all come back short; the rank a certificate charges found it never stopping early with the published safety factor. A sparse probe — each entry nonzero with probability one in twenty, so about three columns of the matrix summed with random signs — costs a twentieth of a dense Gaussian one. Build the basis from sparse probes and certify it with dense ones, and the certificate is honest: on a coherent matrix, whose important directions sit on ten particular columns that sparse probes keep missing, the dense probes refused to certify on most draws. Then promote: whenever the largest dense probe, per unit of its own length, is more than eight times the sparse candidate, take the dense probe as the column instead. That certified every draw correctly, with no promotions on the incoherent matrix and about one per important column on the coherent one.

The essay asked about the matrices in between. The leverage that did not move had built a family that runs continuously between the two: the leading right singular vectors are the orthonormalised mixture $\cos t \cdot P + \sin t \cdot R$ of ten coordinate vectors and a random orthogonal basis, coherent at $t = 0$ and incoherent at $t = \pi/2$. “The promoted rule paid ten dense columns for ten coherent directions and none for none. The prediction with a sign is that on the matrices mixed toward incoherence by an angle $t$, the median number of promotions falls from ten to zero as $t$ goes from 0 to $\pi/2$, and is still at least five at $t = 0.1$, where the fixed sparse sketch’s median error had already fallen to about a third of its coherent value.”

It does exactly that. The interesting part is what the promotions are for once the matrix has moved even slightly off its coherent extreme, because by then it is no longer safety.

The promotions fade as predicted #

At the coherent end the median draw promotes ten dense probes, with a range of five to fourteen. At $t = 0.05$ it is still ten; at $0.1$, nine; at $0.2$, five; at $0.3$, two; at $0.5$, one; from $0.8$, none. The prediction’s two numbers — ten to zero across the range, at least five at $0.1$ — both hold. And every one of the 270 promoted runs certifies with its true error under the tolerance: the rule is as safe across the family as it was at its two ends.

The promotion count falls on the same logarithmic scale as everything else in this family. A fade made of drops found the fixed sparse sketch’s error falling about forty per cent per decade of $t$ — and found that no single draw falls at that rate; each holds its coherent error and then drops when a hash collision resolves. The promotions are similar: a draw promotes when the sparse candidate is much weaker than the strongest dense probe, and that happens most when the next important direction sits on columns the sparse probes have not hit, which becomes rarer as the directions spread.

The danger is exact coherence, and nothing else #

The promotions exist to stop two failures, and the figure shows where those failures live. Sparse probes certifying a sparse basis certify falsely on ten draws of thirty at the coherent end, with an error up to eight times the tolerance; dense probes certifying a sparse basis without promotion refuse on nineteen draws of thirty there, running to the sixty-column cap. At $t = 0.05$ both counts are zero, and they stay zero across the rest of the family.

That is a stronger form of the earlier finding that the sparse sketch’s failure is a property of exact coherence. At $t = 0.05$ the leading subspace’s coherence — its largest column leverage scaled by $n/k$ — is 6.39, against 6.40 at the coherent end. By the statistic that names coherence, nothing has changed. But the important directions are no longer exactly on their columns; every column carries a few per cent of every direction, and a sparse probe that hits any column sees a little of all of them. Repeated over enough probes, that little is enough: the sparse basis reaches the range, and the dense certificate confirms it. The danger the promotions guard against is gone two decades before the promotions start to thin out.

So what are the promotions buying? #

At $t = 0.05$ and $0.1$ the promoted rule costs 0.54 and 0.51 of the all-Gaussian rule’s probe work and stops at rank 30 — the rank the Gaussian rule itself reaches. The unpromoted rule, certified by the same dense probes, costs 0.30 and stops at rank 38 and 36. Both are correct; both certify every draw. The difference is the basis’s size, and the promoted rule pays for the smaller one in dense probes: about four fifths more probe work for a basis 17 to 21 per cent smaller.

As the mixture grows the two rules converge, and they converge on the unpromoted rule’s cost rather than on the promoted rule’s rank. At $t = 0.2$ the promoted rule costs 0.41 for rank 31 against 0.29 for rank 33; at $0.5$, 0.31 for rank 32 against 0.29 for rank 32; from $0.8$ both cost 0.29 and stop at rank 30 or 31. On the incoherent matrix there is nothing to choose between them. The sparse certificate is cheapest of all, at 0.04 to 0.08 — and safe everywhere but the coherent end, where it lies.

So above exact coherence the promotions buy rank, not safety. Whether that is a good purchase depends on what the basis is for. A basis used once to compress a matrix pays for its rank in every later product with it, and eight fewer columns in a basis of thirty-eight is eight fewer columns in every one of those products. A basis used once and discarded does not.

Why the trigger fires when nothing is wrong #

The promotion test compares two numbers at every step: the largest dense probe’s norm after projection, per unit of the probe’s own length, against the sparse candidate’s, per unit of its own. It fires when the first is more than $\rho$ times the second. On the coherent matrix it fires because the sparse candidate has missed the important columns entirely and is nearly zero after projection. At $t = 0.05$ the candidate has not missed them — every column now carries a few per cent of every important direction — but a sparse probe that touches three columns picks up only those few per cent of each, while a dense probe touching all sixty-four picks up everything. Per unit of length the dense probe is still several times stronger, and at $\rho = 8$ often enough stronger to fire.

So the test measures how efficiently a sparse probe samples the remaining range, and near coherence that efficiency is low even when it is not zero. Low efficiency means a sparse basis needs more columns to cover the same range — which is exactly the rank difference — and it does not mean the sparse basis will fail. A sketch that finds the columns it can see drew the same distinction for a fixed sketch: a sparse sketch that can see a column at all finds the direction on it, given enough width. The adaptive rule supplies the width by adding columns, and the promotion test, reading efficiency, cannot tell “needs more columns” from “will never get there”.

A bound that holds with probability is the guarantee the dense certificate carries: ten Gaussian probes, all short, bound the remaining error with a stated probability whatever the basis was built from. That guarantee is what makes the unpromoted rule safe away from exact coherence — the certificate does not care how the basis was built, only whether it covers the range — and what makes the promotions unnecessary for safety there.

The threshold is a price #

The threshold $\rho$ decides how readily a dense probe is promoted: it must beat the sparse candidate by a factor of $\rho$ per unit of length. At the coherent end the dial shows its first job. With $\rho = \infty$ — never promote — eleven draws of thirty certify; with any finite $\rho$ from one to sixteen, all thirty do, at costs from 0.79 down to 0.50 of the Gaussian rule. There, some promotion is necessary, and the threshold sets how much.

Turn the dial to $t = 0.05$ and the job changes. Never promoting now certifies all thirty draws at a cost of 0.30. Every finite threshold also certifies all thirty, at a cost that rises as the threshold falls — 0.49 at $\rho = 16$, 0.54 at $8$, 0.66 at $2$, 0.81 at $1$ — and buys a smaller basis for the extra. The threshold has stopped being a safety margin. It is the exchange rate between probe work now and basis size later, and $\rho = 8$, chosen on the two extreme matrices, sets that rate higher than the nearly coherent matrices need. At $t = 0.2$ a threshold of sixteen promotes one probe and costs 0.32; eight promotes five and costs 0.41.

Where the promotions go #

The promotions near coherence cluster early. At $t = 0$ and $t = 0.1$ about a third of all promotions fall in the first fifth of the basis and a ninth in the last, which is where the leading directions are being found: a sparse candidate that misses a strong direction is weak compared with a dense probe that catches it, and the ratio test fires. At $t = 0.3$ the sixty-six promotions are spread across the basis, with a quarter in the last fifth, where the singular values are small and a single sparse probe’s luck matters more.

That pattern explains the rank difference. Promoting early puts the leading directions into the basis as soon as the dense probes see them, so every later column is spent on the next direction rather than on what a weak sparse candidate happened to bring in. The unpromoted rule gets to the same range eventually — its certificate says so — but by accumulating more, weaker columns on the way. What a single draw cannot report and an answer that changes with the seed found the same variability in which columns a random method chooses; promotion is a way of replacing the luckiest of those choices with a sure one.

Promoting only when stuck #

The measurement suggests separating the two things promotion does. Safety needs a promotion only when the sparse basis is stuck — when the dense certificate keeps refusing because the sparse probes keep missing a direction. Rank needs promotions whenever a dense probe is much stronger than the sparse candidate. A rule that promotes only on the first condition should be as safe as the present rule and as cheap as the unpromoted one.

That rule is easy to state and to run: promote a dense probe — the strongest one, if it beats the sparse candidate at all — only when the certificate’s largest probe has fallen by less than a tenth over the last five columns added. Across the family it does what the argument says it should. At the coherent end it certifies all thirty draws, promoting a median of four dense probes where the $\rho = 8$ rule promoted ten, at 0.40 of the Gaussian rule’s probe cost against 0.53, and stops at a median rank of 43. From $t = 0.05$ on it never promotes at all: the certificate never stalls, because the sparse basis never gets stuck, and the rule is the unpromoted rule — 0.30 of the Gaussian cost, rank 38 at $t = 0.05$, every draw certified.

So the two purchases can be bought separately. Promoting when stuck is the cheapest rule that is safe at every mixture; it spends dense probes only where the sparse ones genuinely fail. Promoting at $\rho = 8$ buys, on top of that, the Gaussian rule’s rank — 30 at every mixture — for whatever the extra dense probes cost, which is most near coherence and nothing far from it. Which to run is a question about how the basis will be used, and the measurement now prices both answers.

What this changes about the rule #

The rule as the earlier essay left it was: sparse basis, dense certificate, promote at $\rho = 8$. Measured across the family it is safe everywhere, as claimed, and it is more expensive than it needs to be over the two decades of mixture nearest coherence, by up to four fifths of its own cost. The rule that promotes only when the certificate stalls keeps the safety at the coherent end, where the refusals are real, and pays nothing at $t = 0.05$, where they never happen; it is the default the measurement argues for, with the $\rho$ test kept for callers who want the smaller basis and can say what it is worth to them.

The broader lesson is about what a coherence statistic can tell a randomised method. The leverage that did not move found the largest column leverage unchanged at 6.40 while the sparse sketch’s error fell by two thirds; here the same statistic is unchanged while the need for promotion disappears entirely. The statistic measures how concentrated the directions are on their heaviest columns. The failures depend on whether they are exactly there — on whether any probe that misses those columns sees nothing at all — and the statistic cannot tell a tiny leak from no leak. Randomisation does not create structure is the companion caution: a random method finds what is there, and here the tiny leak is enough for it to find.

What sixty-four columns do not show #

Every matrix is 64 by 64 with a geometric spectrum, and the mixture is one random rotation family. On a larger matrix with more important directions, a sparse probe’s chance of hitting any of their columns grows, and the danger at exact coherence would be expected to shrink with it. The cost counts only the products that form the probes; the orthogonalisation, which depends on the final rank, is the same per column for every rule and is left out, so the unpromoted rule’s larger basis is cheaper here than it would be in a count that included it. And the claim that early promotions are what keep the rank down is argued from where they fall, not from an experiment that moves them.

Still open: what the extra columns cost later, and a larger matrix #

What the extra columns cost later. The unpromoted rule’s basis is up to eight columns larger near coherence, and every later product with the compressed matrix pays for them. The prediction with a sign is that if the basis is used for more than four products with the matrix it compresses — counting each at the cost of one dense probe per basis column — the $\rho = 8$ rule’s total work falls below the stall-promoting rule’s at $t = 0.05$ and $0.1$, and that the break-even number of products falls to two at the coherent end.

A larger matrix. With 256 columns and forty important directions, a sparse probe of the same density hits about thirteen columns, and the chance that a coherent direction goes unseen for many probes falls. The prediction is that on the coherent 256 by 256 matrix the unpromoted rule refuses on fewer than five draws of thirty, where on the 64 by 64 matrix it refused on nineteen — and that the promoted rule’s cost advantage at the coherent end shrinks below a tenth of the Gaussian rule’s.