The probe that refuses becomes the column

The rank a certificate charges measured the adaptive range finder: grow an orthonormal basis $Q$ a column at a time from random probes $A\omega$, projected off what $Q$ already holds, and stop when ten fresh probes all come back with $10\sqrt{2/\pi}\,\max_i \|(I - QQ^{\mathsf T})A\omega_i\| \le \varepsilon$. The published guarantee is that the true error is then under $\varepsilon$ except with probability $10^{-10}$, and in every draw that essay made the rule never stopped early. It ended by noting that every probe it used was a dense Gaussian vector, each costing a full matrix–vector product, and pointed to a sketch that finds the columns it can see for cheaper ones.

That essay and its two sequels found the cheaper sketch’s weakness. A sparse sketch is many times cheaper to apply and finds the same range on a matrix whose important directions are spread across its columns. On a matrix whose important directions sit on particular columns — a coherent one — it fails, because a sparse probe touches only a few columns and a column it never touches is a direction it never sees. The leverage that did not move and a fade made of drops measured that failure for a fixed sketch, chosen once and applied.

The adaptive rule asks something the fixed sketch does not: probes play two parts in it. They build the basis, and they decide when to stop. Nothing so far separated the two, and a code that wants the sparse sketch’s price and the adaptive rule’s guarantee has to decide which probes do which job.

Two matrices, four ways to run the rule #

The matrices are the sketch essays’: $64 \times 64$ with singular values $0.8^k$, one with random singular vectors and one whose right singular vectors are columns of the identity in a random order, so that its ten leading directions are ten particular columns. The tolerance is $\varepsilon = 0.1$, which the best rank-11 approximation already meets. A sparse probe has each of its 64 entries nonzero with probability 1/20, with a random sign, so it sums about three columns of $A$ and costs a twentieth of a Gaussian probe to apply. Cost is counted as the multiply-adds that form the probes; the orthogonalisation is the same whatever the probes are.

The rule is run four ways, thirty draws each, with a cap of sixty columns. With Gaussian columns and a Gaussian certificate, the published rule. With sparse columns and a sparse certificate, the cheap rule. With sparse columns and a Gaussian certificate, which this essay calls checked: the basis is built cheaply and judged by the probes the guarantee is about. And with the checked rule plus one change, promotion, described below.

The figure at the top of the page is the outcome of all 240 runs. Each bar is thirty draws: green certified with the true error under the tolerance, red certified with it over, grey never certified within sixty columns. The all-Gaussian rule certifies every draw on both matrices, at a median rank of 30, and is the cost every other row is measured against.

Sparse probes certify what they cannot see #

On the incoherent matrix the all-sparse rule is a bargain: every draw certified correctly, at a median rank of 23, for 4 per cent of the all-Gaussian cost. It stops earlier than the Gaussian rule because a sparse probe sums fewer columns and so reads a smaller residual; on this matrix that is harmless, because every column carries a share of every direction and three columns are as good a sample as sixty-four.

On the coherent matrix it certifies eight bases falsely, out of eighteen it certifies, and the worst has a true error ten times the tolerance. That is the coherence failure appearing inside the certificate. A basis built from sparse probes has missed a column if no probe happened to touch it, and the certificate’s probes are drawn the same way: a probe that does not touch the missing column cannot report it. Ten fresh sparse probes each touch a given column with probability one in twenty, so all ten miss it with probability $0.95^{10} = 0.60$. The certificate is then a vote among probes most of which cannot see the thing being voted on.

The incoherent result is the warning inside the good news. There the all-sparse rule stopped seven columns earlier than the Gaussian one, at a true error of up to $0.39\varepsilon$ against the Gaussian rule’s $0.09\varepsilon$: the sparse certificate already reads less than the dense one on a matrix where nothing is hidden, and only the constant’s factor of eight keeps that from mattering. On the coherent matrix the reading falls further than the error, and the constant is not enough. Randomisation does not create structure put the general point plainly: a random method finds what is there to find, and a probe that samples three columns has three columns’ worth of evidence, however many times it is drawn.

The errors spread accordingly. The all-sparse rule’s thirty runs range from $0.005\varepsilon$ to $10\varepsilon$, and the red dots above the line are the false certificates. The figure also shows what the all-Gaussian rule pays for its safety: its errors sit between $0.03\varepsilon$ and $0.13\varepsilon$, an order of magnitude under the tolerance, because the certificate’s constant $10\sqrt{2/\pi} \approx 7.98$ demands that much margin, the price the rank a certificate charges measured as ten columns of the nineteen extra.

Dense probes refuse, and refusing is not enough #

Certify the same sparse basis with Gaussian probes and the false certificates disappear: not one in thirty on either matrix. A Gaussian probe touches every column, so a missing direction shows up in every probe, at the size of its singular value. The certificate the guarantee is about is back in charge.

On the incoherent matrix that costs little: the checked rule certifies every draw at a median rank of 31 for 29 per cent of the all-Gaussian cost, the sparse columns doing the building and ten Gaussian probes per check doing the judging. On the coherent matrix it exposes the other half of the problem. The checked rule certifies only twelve draws of thirty by the sixty-column cap, at ranks from 34 to 59, and refuses eighteen. Nine of those eighteen still miss a direction, with errors up to ten times the tolerance. The other nine are under the tolerance but not yet under the certificate’s margin; the sparse basis takes so many columns to wander onto every important one that it runs out of room before it has also reduced the rest.

The arithmetic of the miss is simple. A sparse probe touches a given column with probability 1/20, so after $k$ sparse columns a given column has been missed with probability $0.95^k$: 0.21 at thirty columns, 0.046 at sixty. With ten important columns, the chance that all ten have been touched is $0.79^{10} = 0.09$ by thirty columns and $0.954^{10} = 0.62$ by sixty. So at the cap about four draws in ten should still miss a direction, and nine of thirty, three in ten, do. An honest certificate cannot fix that. It can only say so, every time it is asked, and it does.

Promoting the probe that refuses #

The probe that refuses is the fix. When a Gaussian certifying probe comes back large, its projected vector $(I - QQ^{\mathsf T})A\omega$ is a sample of exactly what the basis is missing, the coherent column included, because a Gaussian combination of all sixty-four columns contains every one of them. The published rule makes every probe a column eventually; the sparse basis wastes that information by drawing its next column elsewhere.

So the promoted rule compares, at each step, the next sparse candidate with the largest certifying probe, each projected and divided by the length of the probe vector that made it — a sparse probe has about three unit entries and a Gaussian sixty-four, and without the division the Gaussian probe always wins. If the Gaussian probe’s reading is more than $\rho$ times the sparse candidate’s, the Gaussian probe becomes the column, a fresh Gaussian probe replaces it in the certificate, and the sparse candidate is discarded. Otherwise the sparse candidate is the column, as before.

On the first draw the all-sparse and checked rules’ readings sit near ten for forty columns and then drop by a decade at once, when a sparse probe finally lands on a missing column; both are still above the tolerance at sixty, with the true error at $0.44\varepsilon$. The promoted rule’s reading falls steadily from the start. It promotes ten Gaussian probes, at ranks 5, 6, 7, 8, 9, 13, 14, 16, 17 and 21, and certifies at rank 32 with a true error of $0.031\varepsilon$. On the six draws on the dial the promoted rule certifies every time, by rank 32, with true errors from $0.02\varepsilon$ to $0.07\varepsilon$. The all-sparse rule refuses twice, certifies falsely once — the fourth draw, at $1.21\varepsilon$ — and certifies the other three at ranks 42 to 59. The checked rule refuses three and certifies three, at ranks 44 to 59. Where the sparse readings sit on a plateau, the promoted rule has already taken the probe that would have ended it.

The matrix sets the price #

At $\rho = 8$ the promoted rule certifies every draw on both matrices with the true error under the tolerance — at most $0.07\varepsilon$ on the incoherent matrix and $0.09\varepsilon$ on the coherent one — at a median rank of 30, no more than two columns past the all-Gaussian rule’s largest. What it costs depends on the matrix.

On the incoherent matrix it promotes nothing in the median draw and costs 29 per cent of the all-Gaussian rule: there is never a Gaussian probe eight times more informative than a sparse candidate, because the sparse candidates see everything. On the coherent matrix it promotes a median of ten probes and costs 54 per cent. The checked rule’s 33 per cent looks cheaper and is not: it delivered twelve certified draws of thirty, so per draw it could certify it spent 83 per cent of the all-Gaussian cost, and eighteen draws got nothing for theirs.

The promotions cluster where the matrix’s structure says they should. Ten of the thirty draws promote exactly ten, and the range is five to fifteen. The coherent matrix has ten leading directions on ten particular columns, and the promoted rule pays for a dense column about once for each of them. The rule was not told there were ten; the count comes out of comparing what two kinds of probe can see.

And they come early. On the ten draws laid out here the promoted columns sit mostly among the first twenty, many at ranks one to three: the leading directions are the largest, so the first certificate readings are dominated by them, and the rule spends its dense columns on the directions that matter most and its sparse ones on the long tail where the matrix’s columns are mixed enough for three of them to be a fair sample.

Why the comparison is per unit of probe #

The division by the probe’s own length is not a detail. The first version of the promoted rule compared the projected vectors as they came, and took the Gaussian probe whenever it was the larger. Measured on the same thirty draws it promoted a median of twenty-eight probes a draw on both matrices, almost every column, and cost 98 per cent of the all-Gaussian rule: it had become the all-Gaussian rule with extra steps. A Gaussian probe sums all sixty-four columns with weights of size one and a sparse probe sums about three, so the Gaussian probe’s projected vector is about $\sqrt{64/3} \approx 4.6$ times longer on any matrix, coherent or not, for no reason but its own size. Divided by the probe vector’s length, the two readings estimate the same thing — how much of $A$ the basis is missing, per unit of probe — and the comparison measures what it is meant to: whether the dense probe sees something the sparse one does not, rather than whether it is bigger.

The threshold trades cost for nothing #

The threshold is the rule’s one setting, and across a wide range it does not matter much. At $\rho = 1$ the rule promotes whenever the Gaussian probe is simply the better candidate, which is most of the time: twenty-one promotions a draw on both matrices and 81 per cent of the all-Gaussian cost. As $\rho$ grows the incoherent matrix’s cost falls to 49 per cent at 2, 31 at 4 and 29 from 8 on, where it promotes nothing. The coherent matrix’s falls to 64, 59, 54 and 52 per cent at 2, 4, 8 and 16, never below its ten necessary promotions. Every one of those settings certifies all thirty draws correctly on both matrices. Only at $\rho = \infty$, never promoting, does the coherent matrix’s cost fall to 33 per cent, and there twelve of thirty certify. A code can set $\rho$ anywhere from four to sixteen and the matrix decides what it pays.

What thirty draws on two matrices do not show #

Two matrices of one size and one spectrum, chosen to be the two extremes the earlier essays studied: every direction spread over every column, or every leading direction on one column. A matrix partway between, the mixtures the leverage that did not move built, would promote a number somewhere between zero and ten, and how that number follows the mixing is unmeasured. One sparse probe design, one nonzero in twenty; a denser one would see more columns per probe and need fewer promotions at a higher price per probe. Columns are added one at a time, where real codes add blocks; a block of sparse columns with a block of Gaussian probes beside it is the natural generalisation and has its own trade. The cost counts only the products with $A$, which is right when $A$ is the expensive thing to touch and wrong when orthogonalisation dominates, as it does for a small dense matrix like these.

And the guarantee is measured, not proved. A bound that holds with probability began this line of essays with the published bound, which assumes the certifying probes are independent of the basis. Promotion breaks that a little: the probe promoted is the largest, so the nine that remain have been selected for being smaller, and a certificate built from them leans optimistic. Across every finite threshold measured — five values of $\rho$, both matrices, thirty draws each — the promoted rule made 300 runs, and every one certified with its true error under the tolerance. That is evidence the lean is small beside the constant’s factor of eight, not a bound on it.

Still open: a mixture, and a sketch that learns its columns #

A mixture. 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.

A sketch that learns its columns. Each promoted probe carries a direction the sparse probes missed, and with it the columns that direction lives on. A rule that, after each promotion, gives the heaviest columns of the promoted vector buckets of their own in later sparse probes — the reserved buckets of the hybrid sketch, chosen by the data instead of in advance — should need fewer promotions. The prediction is that on the coherent matrix it certifies every draw with a median of at most five promotions, at under 45 per cent of the all-Gaussian cost.