A fade made of drops

The leverage that did not move mixed a matrix continuously from coherent — its ten leading right singular vectors sitting on ten particular columns — to incoherent, by rotating those vectors toward a random basis through an angle $t$, and watched a one-nonzero sketch’s error fade as $t$ grew. Hashing each of 64 columns into one of 20 buckets loses a leading direction whenever two of the ten special columns share a bucket; at $t = 0$ nothing else in the matrix carries that direction, and the median error was 3.47 times the eleventh singular value. At $t = 10^{-4}$ it was 3.01, at $10^{-3}$ 2.09, at $10^{-2}$ 1.23 and at $10^{-1}$ 0.72: about forty per cent off for every decade.

It gave the mechanism — once $t$ is not zero every column carries a faint copy of every leading direction, so every bucket holds a little of the lost one and the range finder can recover it — and it was candid that the mechanism predicts the direction of the effect and not its rate. “Measuring the error draw by draw against how many leading directions collided, at several mixtures, would say whether each collision costs less as t grows or whether the collisions stop mattering one at a time.”

This essay makes that measurement. The answer is neither of the two the question offered, and the rate turns out to belong to the spectrum rather than to the sketch.

One hash, followed across the mixing #

The construction is the earlier one, with the singular values made a parameter: $\sigma_k = \rho^k$ for decay rates $\rho$ of 0.6, 0.7, 0.8 and 0.9. The range finder uses a width-20 sketch, orthonormalises the sketched columns and reports $\|(I - QQ^{\mathsf T})A\|/\sigma_{11}$ — one when the sketch captures the ten leading directions as well as possible, larger when it loses some. Eighty seeded hashes at $\rho = 0.8$ and forty at each other rate, and each hash is kept fixed while the matrix is mixed, through sixteen values of $t$ from 0 to 1, half a decade apart from $10^{-7}$. So a draw is a curve: the same random hash asked the same question of a matrix that is becoming less coherent.

A draw’s collisions are recorded at $t = 0$: a leading column that shares its bucket with a more important leading column is a direction the sketch cannot hold. Of the eighty draws at 0.8, ten collide nowhere, nineteen lose one direction, twenty-seven two, fifteen three and nine four.

The single curves do not look like the median. Each holds its coherent value flat through several decades of $t$, as if nothing had happened, and then drops — within one to three decades — to near the incoherent level, where it stays. The draw that loses the first leading direction holds 8.2 until $t = 10^{-3}$, is at 5.3 by $3 \cdot 10^{-3}$, 2.0 by $10^{-2}$ and 0.78 by $3 \cdot 10^{-2}$. A draw that loses the sixth direction holds 2.7 until $10^{-4}$ and is at 1.04 by $3 \cdot 10^{-4}$. Another draw losing the sixth direction does not start falling until $10^{-2}$. The median is the average of curves like these, each dropping at its own place.

How far each draw falls #

The height of a draw’s drop is predictable before any mixing. A draw that loses leading direction $k$ cannot represent that direction at all at $t = 0$, and the best it can do leaves an error of about $\sigma_k$: at $\rho = 0.8$, $\sigma_k/\sigma_{11}$ runs from 9.3 for the most important direction to 1.25 for the tenth. All nineteen single-collision draws start within a factor of two of that line. The coherent failure, which the earlier essays measured as a median of 3.47, is a mixture of draws that lost directions of very different importance — and the height of each draw’s drop is the importance of what it lost. Draws with two or three collisions start higher, at medians of 4.4 and 5.7, because the most important lost direction of several is, on average, more important than a single one.

A draw that loses several directions does not drop once; it drops once for each, in order of importance. The draw that lost directions 2, 7 and 8 starts at 6.6, falls to 4.3 between $3 \cdot 10^{-5}$ and $10^{-4}$ as its most valuable lost direction comes back, reaches 2.4 by $10^{-3}$, lingers near 1.8 through $10^{-2}$, and comes down to 1.3 only at $10^{-1}$ as the two minor directions return last. Each stage is a drop of the kind a single collision makes, as tall as the direction it recovers, and the curve is their sum. That is the other half of the answer to the earlier question: collisions do stop mattering one at a time — in order of how much they cost.

No draw falls faster than one over t #

The drops are steep but not arbitrarily steep, and their steepest is a number the mechanism predicts. A lost direction comes back through the faint copies of it in the other buckets, and those copies are proportional to $\sin t$, which for small $t$ is $t$. The part of the lost direction that the range finder can separate from what it arrives mixed with grows at most in proportion to the copies, so the error that is left can fall at most in proportion to $1/t$ — one decade of error for each decade of mixing.

Across all 2,600 half-decade steps up to $t = 0.3$, at every decay rate, the largest fall is 0.993 decades per decade. The distribution sits well below it: at decay 0.8 the steepest step of the median draw falls 0.51 decades per decade, at 0.9 only 0.34. The bound is never broken while the mixing is small; only in the last step, from $t = 0.3$ to a full quarter turn, where $\sin t$ is no longer $t$, does a draw fall faster.

So “each collision costs less as t grows” is true within a drop — the error of a draw falls as its lost direction is recovered — but the rate is not a constant of the process. It is bounded above by one over $t$ and reached only in the middle of a drop; before the drop and after it, a draw does not change at all.

The spread of the drops is the median’s slope #

A median of curves that each hold, drop and hold again is a smooth fall if the drops are spread over a range of $t$, and a cliff if they are not. At decay 0.8 they are spread: the midpoints of the eighty draws’ falls lie between $10^{-3.0}$ and $10^{-0.8}$ from the tenth to the ninetieth percentile, over two decades, while the median draw goes from a fifth of its fall to four fifths in 1.9 decades. Overlapping drops of about two decades’ width, centred across two decades, average to a slope of a few tenths of a decade per decade — the forty per cent the earlier essay measured.

Turn the dial and the account is tested on spectra that were not used to find it. At decay 0.9 the singular values fall slowly, a lost direction is worth only 1.2 to 2.5 times the eleventh, and every draw’s fall is small and late: the midpoints crowd between $10^{-1.3}$ and $10^{-0.4}$, the typical fall is under a decade wide, and the median holds at 1.83 all the way to $t = 10^{-2}$ before falling to 1.01 in about a decade and a half. There is no constant fraction per decade there: there is a flat line and then a cliff. At decay 0.7 and 0.6 the lost directions are worth ten and a hundred times the eleventh, each draw’s fall is taller and so longer — three decades or more at the median, within the one-over-$t$ bound — and the midpoints spread over four or five decades, from below $10^{-6}$. The median slides from the smallest $t$ measured to the largest.

The draws’ own statistics say why. Taller falls tend to begin earlier and to take longer: at decay 0.7 and 0.8 the width of a fall grows by about a decade for each decade of height, which is what a fall running at a bounded rate must do, and its midpoint moves earlier as its height grows, because a more important lost direction has more of itself in each faint copy and comes back at a smaller $t$. A flatter spectrum makes every lost direction less important, so every fall is shorter and later, and the spread collapses; a steeper spectrum does the reverse.

The rate belongs to the spectrum #

Scaled to their own falls, the four medians are half gone at $t = 10^{-5}$, $10^{-3}$, $10^{-2}$ and $10^{-1}$ for decays 0.6, 0.7, 0.8 and 0.9, and their shapes differ as much as their positions. No single rate per decade describes all four, and no rescaling of $t$ by the spectrum makes them coincide, because the spectrum changes both where the drops fall and how tall they are. The forty per cent per decade was a property of decay 0.8: real, reproducible, and not a law of the sketch.

The practical question the earlier essay cared about — how coherent does a matrix have to be before a one-nonzero sketch is dangerous — therefore has a spectrum in its answer. On a matrix whose singular values fall slowly, the sketch is safe as soon as the leading directions are rotated a tenth of a radian from coordinate columns, and dangerous right up to that point. On a matrix whose values fall fast, a rotation of $10^{-5}$ already recovers half the damage in log terms, and some draws are still hurt at $10^{-1}$. A sketch that finds the columns it can see reserved buckets for heavy columns as a repair; the measurement here says the repair matters most for exactly the spectra whose falls are late and steep, where no amount of accidental mixing helps until it is nearly complete.

What a probability bound says about a drop #

The guarantees that come with sketches are statements about the chance of a bad draw, and a bound that holds with probability is the essay that measured one against the draws it describes. For a one-nonzero sketch of a coherent matrix the bad event is a collision, and its chance does not depend on $t$: the hash is fixed, and whether two leading columns share a bucket is decided before any mixing. What $t$ changes is what a collision costs, from the lost direction’s full singular value at $t = 0$ to almost nothing once the mixing has passed the draw’s drop. A bound written in terms of the chance of a bad draw is therefore exactly right at $t = 0$, where every collision is a failure, and increasingly pessimistic as the matrix loses coherence, since it keeps charging for collisions that no longer cost anything.

That is the same gap the rank a certificate charges found between a bound and a measurement from the other side: a certificate that is always valid pays for the worst case at every input. Here the worst case is exact coherence, a single point on the mixing axis, and a draw’s own curve shows how quickly the price falls away from it — a decade or two of $t$, placed by the spectrum.

Which regime a matrix is in #

A user cannot see $t$, but the spectrum decides the regime and the spectrum is partly visible. The drops are tall and early when the leading singular values stand far above the ones the sketch’s width reaches, and short and late when they do not; the ratio of the twentieth singular value to the tenth — 0.35, 0.11, 0.028 and 0.006 for decays 0.9, 0.8, 0.7 and 0.6 — is a single number that orders the four regimes correctly. A range finder estimates the leading singular values of its own output as it goes, and the cheap rank and what it cannot see measured how well such an estimate tracks the truth. The same estimate, read at the sketch’s width, says whether a lost direction would have been costly: on a steep spectrum a collision costs a factor of ten or more and takes decades of mixing to undo, which is when a sketch with more than one nonzero per row, or reserved buckets, earns its cost; on a flat one a collision costs less than a factor of three and is undone by a tenth of a radian, which almost any real matrix has.

What the median was hiding #

This is a recurring shape in randomised numerical linear algebra and it is worth naming. A median over draws is a summary of a distribution, and when the distribution is bimodal in time — each draw either fully hurt or fully recovered — its median moves smoothly through values that no draw ever takes for long. An answer that changes with the seed found the same thing in another place: a quantity whose seed-to-seed spread is part of its answer, not noise around it. What a single draw cannot report found the error of one draw uninformative about the error of the next; here, one draw’s curve is uninformative about the median’s slope, and the median’s slope says nothing about when a particular draw will recover.

For a user with one draw, the useful statement is the draw’s own: its error is either near the coherent value set by what it lost, or near the incoherent floor, and which one depends on whether the mixing has passed that draw’s midpoint. Randomisation does not create structure was about a matrix with nothing to find; this matrix has a great deal to find, and a given hash either finds it or does not, with a transition that is a decade or two wide.

What sixty-four columns do not show #

One matrix size, one sketch width, one mixing construction, and the spectrum as the only property varied. The one-over-$t$ bound is argued from the mechanism and measured on every step; it is not proved. The drop midpoints are read by interpolating each draw’s curve on a half-decade grid, which puts them to within a quarter of a decade, and at decay 0.6 some drops begin below the grid’s first point and are placed there. The sketches are hashes with random signs; a sketch with more nonzeros per row was found flat in the earlier essay and would have no drops to measure.

Still open: where a drop falls, and a sketch that knows the spectrum #

Predicting a draw’s midpoint. The midpoint moves earlier as the lost direction’s importance grows, at about a decade per decade at decay 0.7. The prediction with a sign is that a draw’s midpoint is where $t\,\sigma_k$ reaches the size of the minor directions its bucket holds — a quantity computable from the hash and the spectrum — and that it predicts the midpoints to within half a decade.

Reserving by importance. The hybrid sketch reserved buckets for the heaviest columns. On a steep spectrum the draws that stay hurt longest are the ones that lost the most important directions, so reserving buckets for only the three or four heaviest columns — the directions worth the most — should remove most of the late falls on steep spectra and little on flat ones.

Larger matrices. With more columns hashed into more buckets, the number of collisions among the leading columns is set by the ratio of their count to the bucket count. Holding that ratio fixed, the drops should keep their heights and widths, and the median’s shape at decay 0.8 should survive a change of size unchanged; if it does not, something other than collisions is at work.