The leverage that did not move

A sketch that finds the columns it can see compared four ways of drawing the random matrix Ω that a randomised range finder multiplies A by, and found that one of them fails on one kind of matrix. The cheapest sketch puts a single signed nonzero in each row of Ω, so each column of A is sent, whole, to one of the l buckets that become the columns of AΩ. On a matrix whose important right singular directions are spread over all its columns, that sketch found the range as well as a dense Gaussian one. On a matrix whose ten leading right singular vectors sit on ten particular columns it was eight times worse, because two important columns hashed to the same bucket arrive as one direction, and no other bucket holds either of them.

Those were the two ends of a line. Every matrix a user meets lies somewhere between them, and that essay closed with two unmeasured questions: how coherent must an input be before three nonzeros a row stop being optional, and would a sketch that gave the heaviest columns buckets of their own keep the cheap sketch’s cost while losing its failure.

Both have answers, and neither is the one the vocabulary suggests. The word for the property that breaks the cheap sketch is coherence, and coherence is measured by the largest column leverage. On the matrices here the failure fades by two thirds while that number does not change in its third figure. And the obvious repair — reserve a bucket for each column that matters — repairs a third of the failure when it reserves as many buckets as the rank, and all of it only when it reserves half again as many.

A dial between the two matrices #

The matrices keep everything from the earlier comparison except the right singular vectors. Each is 64 × 64, with singular values falling by a factor of 0.8 a step, so that $\sigma_{11}$ — the first singular value a rank-ten approximation must leave behind — is the floor every method is measured against. The left singular vectors are one fixed random orthogonal matrix. The right singular vectors are built from two bases: a permutation P, whose columns are coordinate vectors, and a random orthogonal matrix R. Column k of V is $\cos t$ times the k-th column of P plus $\sin t$ times the k-th column of R, and the result is orthonormalised in order.

At $t = 0$ that is the coherent matrix: the k-th right singular vector is one coordinate vector, so column $c$ of A is exactly $\sigma_k u_k$ for the single direction k assigned to it. At $t = \pi/2$ it is the incoherent twin, whose singular vectors have no preference for any column. In between, t is roughly the angle by which each leading direction has been turned away from its own column, so $t = 0.01$ is about half a degree.

The statistic that textbooks attach to this property is the coherence of the leading subspace: the largest squared length of any row of the first k columns of V, which is the largest column leverage, multiplied by n/k so that a perfectly spread subspace scores one. Influence is decided before the data met the same quantity on the rows of a regression design, where the leverages sum to the number of columns and a row holding most of one is a row that decides the fit on its own. For the column space the arithmetic is identical. On the coherent matrix ten columns hold leverage one and the rest hold zero, so the coherence is $64/10 = 6.4$, its largest possible value.

At each of fourteen mixtures from $t = 0$ to $t = \pi/2$, four sketches of width twenty are drawn thirty times, and the range finder’s error $\|(I - QQ^{\mathsf T})A\|_2$ is divided by $\sigma_{11}$. The four are the one-nonzero sketch, the three-nonzero sketch, a Gaussian sketch, and a hybrid described further down.

Four decades of mixing, and a steady fall #

The Gaussian sketch and the three-nonzero sketch are flat. Across the whole range their medians sit between 0.37 and 0.44, which is the same number the earlier comparison measured at both ends, and it is what a width-20 basis achieves on this spectrum whatever the directions look like. They are the reference line.

The one-nonzero sketch starts at 3.47 on the coherent matrix — a little above the 3.33 measured with twenty draws in the earlier essay, which is the difference between two sets of seeds — and falls steadily as the mixture grows. At $t = 10^{-4}$ it is 3.01, at $10^{-3}$ 2.09, at $10^{-2}$ 1.23, at $0.1$ 0.72, and it reaches 0.50 at $t = 0.5$ and 0.46 at the incoherent end. From $10^{-3}$ to $10^{-1}$ each decade of mixing takes about forty per cent off the median.

The shape is the first thing worth saying about it. The failure is not a property that switches off at some level of spreading; it is at its worst only at exact coherence and it gives way to every order of magnitude of mixing in turn. At a hundredth of a radian, which is a rotation nobody inspecting the singular vectors would call anything but coherent, most of the gap between the one-nonzero sketch and the Gaussian has already closed. By a tenth of a radian what is left is under a factor of two.

The mechanism the earlier essay traced draw by draw explains why exact coherence is the worst case. When two leading columns share a bucket, the sketch holds only their signed sum, and at $t = 0$ no other bucket holds either direction at all — the lost direction is simply absent from the range. Once t is not zero, every other column of A carries a small multiple of every leading direction, and each bucket therefore holds a faint copy of the lost direction beside whatever it was dealt. The range finder orthonormalises, and orthonormalisation does not care how faint a direction is, only whether it can be separated from what it arrives mixed with. A faint copy of $u_j$ in a bucket that is otherwise full of minor directions buys back part of $u_j$, and as t grows the copies grow and more of it comes back.

That is an account of the direction of the effect and not of its rate. The measured rate — close to a constant fraction per decade — is not something the account predicts, and nothing here derives it.

The statistic that names the failure does not see it #

If coherence were what broke the sketch, the sketch’s error would move with it. The next figure puts the two on the same axes.

The coherence is 6.400 at $t = 0$, and still 6.400 at $t = 10^{-2}$, when the median error has fallen from 3.47 to 1.23. It is 6.39 at $t = 0.05$, where the median is 0.80, and 6.35 at $t = 0.1$. It does not fall appreciably until t is a few tenths — 5.97 at 0.3, 5.30 at 0.5 — and by then the one-nonzero sketch’s median has been within a quarter of the Gaussian’s for some time. It ends at 1.77 on the incoherent matrix rather than at one, because a random ten-dimensional subspace of a 64-dimensional space is not perfectly spread either.

So over the range where the sketch’s behaviour changes most, the statistic that names its failure is constant. Two matrices with coherence 6.40 get median errors of 3.47 and 1.23, and a matrix with coherence 6.35 gets 0.72. That is the first claim this essay refuses: that the largest leverage is what decides whether a one-nonzero sketch fails.

The reason is visible in the definition. A leverage is the squared length of a column’s share of the leading subspace. Turning a direction by half a degree changes that share by about $t^2$, which at $t = 0.01$ is one part in ten thousand. The sketch does not respond to the share; it responds to whether any bucket holds a copy of the direction it lost, and at $t = 0.01$ every bucket holds one of relative size roughly t, not $t^2$. The failure scales with the first power of the mixing and the leverage with the second, so on a logarithmic scale of mixing the leverage is the last of the two to notice anything.

The honest version of the earlier essay’s closing question is therefore not “how coherent”, as coherence is measured, but “how exactly coherent”. A matrix whose important directions sit on columns by accident of construction — a feature matrix in which ten features are exactly the ten directions that matter — is the dangerous one. A matrix whose important directions are merely concentrated on some columns, with every other column carrying a little of them, already gives the cheap sketch most of what it needs.

One draw in ten tells a different story #

A median describes the draw a user usually receives. A randomised method is also judged by the draw it occasionally delivers, and a bound that holds with probability made the case that the honest figure for these methods is a band rather than a line. The ninetieth percentile is the top of that band.

Here the fade is slower. The one-nonzero sketch’s ninetieth percentile starts at 8.19, drops to 2.07 at $t = 0.01$, and is still 1.71 at $t = 0.1$ and 1.31 at $t = 0.2$. It is 1.02 at $t = 0.3$ and 0.80 at $t = 0.5$, and it reaches 0.67 only at the incoherent end. The three-nonzero sketch’s ninetieth percentile is between 0.56 and 0.68 everywhere, a little above the Gaussian’s 0.49 to 0.57 and flat in the same way.

So by the tail, the one-nonzero sketch is not safe until each leading direction has been turned by somewhere between seventeen and thirty degrees, and over that stretch the coherence is still between 5.97 and 5.30. A rule of the form “use one nonzero when the coherence is below some threshold” would need a threshold near six to protect the tail, which is almost the maximum, and at that threshold it would still send the exactly coherent matrix and the half-degree matrix, whose tails differ by a factor of four, down the same path.

This is where three nonzeros a row earn their place. They cost three times as much to apply as one, and on the coherent matrix their median is the Gaussian’s; across the mixture their tail stays where it was on the incoherent matrix. The earlier essay found that three was the point at which cheap and reliable meet, measured at the two ends. Measured along the line between them, nothing moves that conclusion. What the line adds is that the case for one nonzero is weaker than a median suggests even on matrices that are nearly incoherent: at $t = 0.5$ its median is 0.50 against the Gaussian’s 0.39, and its ninetieth percentile 0.80 against the three-nonzero sketch’s 0.68.

Buckets for the columns it can see #

The second question was whether the failure could be avoided without paying for more nonzeros. The failure is a collision among a few heavy columns, and heavy columns are visible before any sketch is drawn: a column’s squared norm is $\sum_k \sigma_k^2 V_{jk}^2$, which on a matrix with a decaying spectrum is dominated by the column’s weight in the leading directions. So the hybrid sketch computes all the column norms, gives the h heaviest columns h distinct buckets, and hashes the rest into all l buckets with one signed nonzero each, exactly as before.

On the coherent matrix with h equal to the rank, ten, the ten heaviest columns are precisely the ten leading directions, and no two of them can collide. The earlier essay’s collision scatter predicts what that should buy: its draws with no collision among the leading ten had a median error of 1.39, well below the 3.47 of the one-nonzero sketch and still more than three times the Gaussian’s 0.41.

The prediction holds. With ten buckets reserved the median is 1.16 and the worst of thirty draws 1.49, against 3.47 and 8.23 for the plain sketch: the median falls by two thirds and the worst draw by more than four fifths. The failure’s tail has almost gone, because what made the worst draws worst — several leading directions lost at once, one of them near the top of the spectrum — can no longer happen. And every draw is still above $\sigma_{11}$.

The earlier essay named the reason, one level down from collisions. Even with the ten leading directions in ten different buckets, the remaining 54 columns are hashed on top of them, about three to a bucket, so each leading direction arrives mixed with two or three minor ones. The basis has twenty columns, and a width-20 basis beats $\sigma_{11}$ by also catching some of directions eleven to twenty. With the leading ten each sharing a bucket with minor columns and the next ten hashed wherever they fall, the basis catches the leading ten and has almost nothing left to separate the next ten with.

That is the second claim this essay refuses: that reserving a bucket for each of the rank’s heavy columns cures the coherent failure. It cures the collisions; it does not bring the sketch to the Gaussian’s accuracy.

How many buckets to reserve #

The remedy for the second-level problem is the same as for the first: reserve more. Nothing about the construction ties h to the rank. The next figure sweeps it from none, which is the plain one-nonzero sketch, to twenty, where every bucket belongs to one heavy column and the other 44 columns are hashed on top.

On the coherent matrix the curve falls throughout: 3.47 with none reserved, 3.19 with four, 1.72 with eight, 1.16 at the rank, 0.72 at twelve, 0.55 at fourteen, and 0.36 at sixteen — past the Gaussian’s 0.41 — then 0.24 at eighteen and 0.15 at twenty. The worst draw at sixteen reserved is 0.41, below the Gaussian’s median, and every one of the thirty draws is below $\sigma_{11}$.

At twenty the sketch is almost a column selection: on this matrix the twenty heaviest columns are the twenty leading right singular directions, each has its own bucket, and the range finder comes within a factor of 1.4 of $\sigma_{21}$, the error of the best rank-twenty approximation. No random sketch of width twenty can do as well on a matrix whose important directions are spread, because it has no way of knowing which directions to spend its columns on. On a coherent matrix the column norms tell it.

At $t = 0.01$ the curve has the same shape from a lower start, and crosses the Gaussian line between fourteen and sixteen. At $t = 0.1$ it crosses at fourteen. At the incoherent end it is flat: the column norms carry no information when every column holds a little of every direction, so reserving buckets for the largest of them changes nothing, and the median stays between 0.39 and 0.49 at every h. Reserving does no harm there, measured in the median.

One thing in this figure is not explained. At $t = 0.01$ and $t = 0.1$, reserving two to six buckets leaves a slightly higher median than reserving none — 1.50 against 1.23 at four, and 0.94 against 0.72 at six. At thirty draws a point that difference is within what the draws scatter by, and whether it is real is not settled here.

What the hybrid costs #

The earlier essay priced the sketches in multiply-adds on this dense matrix: 81,920 for the Gaussian, 24,576 for a subsampled randomised Hadamard transform, 12,288 for three nonzeros a row and 4,096 for one.

The hybrid adds one pass over A to find the column norms, which on a dense 64 × 64 matrix is 4,096 multiply-adds, and a partial sort of 64 numbers. Its sketch is still one nonzero a row, so it applies for 4,096. The total is 8,192, two thirds of the three-nonzero sketch’s cost, and at sixteen reserved buckets it matches or beats the three-nonzero sketch at every mixture measured: 0.36 against 0.41 on the coherent matrix, 0.32 against 0.41 at $t = 0.01$ and 0.29 against 0.43 at $t = 0.1$. At the incoherent end it is 0.39 against 0.37, which is the same number within the scatter of thirty draws.

On a sparse A the balance is the same. Column norms cost one pass over the nonzeros, and so does applying a one-nonzero sketch, so the hybrid costs twice the cheapest sketch and two thirds of the three-nonzero one, as it does here. The adaptive range finder that the rank a certificate charges measured spends ten dense probes on every certificate, each costing 4,096 multiply-adds here; beside that, one pass for the column norms is a small price.

There is a second cost that multiply-adds do not show. The hybrid reads A twice before it can sketch, once for the norms and once for the product. A range finder applied to a matrix that arrives as a stream — rows or columns seen once, in order — cannot make the first pass, which is the setting in which cheap sketches are most wanted.

What a column norm knows #

The hybrid works on these matrices because a heavy column is a column the leading directions live on. That is a consequence of how the matrices were built, and it is worth being exact about when it holds.

A column’s squared norm is its leverage in each direction weighted by that direction’s squared singular value. On a spectrum falling by 0.8 a step, the leading ten carry most of the weight, and a column with leverage one on a leading direction has norm at least $\sigma_{10}$, while a column holding only trailing directions has norm at most $\sigma_{11}$. So the heaviest columns are the high-leverage ones, and ranking by norm is ranking by leverage in the subspace that matters.

On a flatter spectrum the ranking blurs. Randomisation does not create structure took the extreme: all singular values equal, where no rank-ten approximation achieves anything. Short of that, a column that holds a little of many moderate directions can outweigh a column that holds all of one leading direction, and the reserved buckets go to the wrong columns. The matrices here do not test that case.

The other way a norm misleads is scale. A matrix of variables measured in different units has columns whose norms reflect the units, and the heaviest columns by norm may be the ones in the smallest unit. On such a matrix both the coherence and the column norms describe the units rather than the data, and so do the singular vectors themselves; the remedy there is the scaling, before any sketch.

Where this sits beside the other uses of a sketch #

The same sparse embeddings are used as preconditioners, in the sketch that is not the answer, where a sketch that loses a direction produces a preconditioner that leaves that direction unconditioned. The collisions measured here are the same event, and the hybrid is the same repair: a preconditioner built from a sketch that reserves buckets for the heavy rows of a coherent least-squares problem avoids the collision that would leave one of them unconditioned. The residual the solution cannot hold met rows of leverage near one from the other side, as the rows whose residuals a fitted solution cannot represent, and the heavy columns here are the same object transposed.

And an answer that changes with the seed measured how far the randomised answer moves between draws. On the coherent matrix with one nonzero, the error of the worst of thirty draws is 8.23 against a median of 3.47; with sixteen reserved buckets the worst draw and the median differ by fifteen per cent. Reserving buckets is also a way of making the method less random, because it replaces the part of the hashing that mattered most by a deterministic choice.

What this rests on #

One family of 64 × 64 matrices with a fixed seed for the singular vectors and the permutation; one spectrum, falling by 0.8 a step; rank ten; sketch width twenty; thirty sketch seeds at every point, the same thirty for every sketch kind. The error is the exact spectral norm of the residual, and costs are multiply-add counts, not timings. The mixture $\cos t \cdot P + \sin t \cdot R$ is one way to interpolate between a coherent and an incoherent basis, chosen because it moves every leading direction by the same angle; a matrix whose directions are turned by different amounts, some exactly coherent and some not, is not measured. On larger matrices with more buckets per important column the collision probabilities fall and all the gaps here shrink, and by how much is not measured either.

The claims that have to fail #

The first is that coherence decides the failure. At $t = 0$ and $t = 0.01$ the coherence is 6.400 both times and the one-nonzero median is 3.47 and 1.23; the refusal is fed the claim that the two medians agree to within half a unit, and fails.

The second is that reserving the rank’s worth of heavy columns is the repair. With ten buckets reserved on the coherent matrix the median is 1.16 against the Gaussian’s 0.41; the refusal is fed the claim that it comes within a quarter of the Gaussian’s median, and fails. Sixteen buckets pass the same test, at 0.36.

Still open: the rate of the fade, and choosing how many to reserve #

Why a constant fraction per decade. The one-nonzero median falls by about forty per cent for every factor of ten in the mixture between $10^{-3}$ and $10^{-1}$. The account above says the lost direction returns through faint copies of relative size t, but not why the error should then fall like a power of t rather than, say, linearly. 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.

Choosing h without knowing the rank. Sixteen was the right number here because the rank was ten and the width twenty. A range finder that grows its basis adaptively does not know its rank in advance. Reserving buckets for every column whose norm exceeds a fixed fraction of the largest, and letting that count grow with the basis, would tie h to the matrix rather than to a guess; whether it keeps the adaptive rule’s stopping rank where the Gaussian keeps it is the next measurement.

The streaming case. The hybrid needs a pass over A before it sketches. A one-pass version would have to discover heavy columns while hashing them — a count-min style tally of column norms that promotes a column to its own bucket once it is seen to be heavy — and what that costs in the columns it promotes too late is unmeasured.