A sketch that finds the columns it can see

A randomised range finder spends almost all of its time in one product. It multiplies the matrix A by a random matrix Ω with l columns, orthonormalises the result, and keeps that basis; every later step works on matrices with l columns rather than n. The rank a certificate charges counted how many columns an adaptive rule asks for and found the answer was mostly set by the spectrum. This essay asks what each column costs to draw.

A Gaussian Ω is dense. Forming AΩ on a square n × n matrix is l·$n^2$ multiply-adds, and on a sparse matrix it is l times the number of nonzeros. The dimension does not appear described the cheaper constructions that practice uses instead — a sparse sketch, which puts a few signed nonzeros in each row of Ω, and a subsampled randomised Hadamard transform, which flips signs, applies a fast orthogonal transform and keeps l of its columns — and said that their guarantees are slightly worse, the cost dramatically lower, and the trade always taken.

The guarantees are worse in a particular way, and there is a matrix on which the trade is a bad one.

Four sketches, one matrix and its twin #

Two matrices are compared, and they have the same singular values and the same left singular vectors. They differ only in where their right singular vectors point.

The incoherent matrix has a random orthogonal basis for its right singular vectors. Every column of A is then a mixture of every singular direction, and no column matters more than another.

The coherent matrix has coordinate vectors for its right singular vectors, in a random order. Its tenth-most important direction lives entirely in one column, its first in another, and so on: A is a matrix of 64 columns of which ten carry nearly all the weight. In the vocabulary of regression each of those ten columns has leverage one in the rank-10 subspace and every other column has leverage zero — the concentration influence is decided before the data measured on the rows of a design, turned on its side.

Four sketches, each with l columns:

• Gaussian — every entry independent and normal; l·$n^2$ multiply-adds to apply.
• Hadamard — a random sign on each row, a 64 × 64 Walsh–Hadamard matrix, and l of its columns chosen at random; $n^2$·log₂n multiply-adds with the fast transform, whatever l is.
• Sparse, one nonzero a row — each row of Ω has a single ±1 in a random column; $n^2$ multiply-adds. This is CountSketch: each column of A is added, with a random sign, into one of l buckets.
• Sparse, three nonzeros a row — three entries of $\pm 1/\sqrt{3}$ in three distinct random columns; $3n^2$.

The quantity drawn is the spectral error of the basis divided by $\sigma_{11}$, the error of the best rank-10 approximation, so a value below one is a width-l basis doing better than rank ten could.

On the incoherent matrix every sketch is a Gaussian #

This is the result the practical literature leads one to expect, and it is worth seeing first because it is so complete. At width 12 the medians run from 1.77 to 1.97; at width 24 from 0.19 to 0.24. The one-nonzero sketch has the heaviest tail — its worst draw at width 24 is 0.46 against the Gaussian’s 0.23 — and otherwise is indistinguishable. For a twentieth of the cost of the Gaussian product, the cheapest sketch finds the same range.

The reason is that on this matrix the bucket sums are themselves random mixtures. Every column of A already contains every singular direction with a random weight, so adding a random-signed selection of columns into a bucket produces a vector whose components along the singular directions are sums of many random terms. That is close to what a Gaussian sketch produces directly, and the range finder cannot tell the difference.

On the coherent matrix one bucket can hold two directions #

Put the directions into columns and the mixing that the sparse sketch was borrowing from A disappears.

Column c of the coherent matrix is $\sigma_k u_k$ for the one direction k that lives there. A bucket of the one-nonzero sketch receives a signed sum of the columns hashed to it, so each column of AΩ is ±σᵢuᵢ ± σⱼuⱼ ± … over the directions whose columns fell into that bucket. If two of the ten leading columns fall into the same bucket, the sketch holds only their signed sum. The basis can contain σᵢuᵢ ± σⱼuⱼ but not $u_i$ and $u_j$ separately, and no other bucket holds either, so one of the two directions is missing from the range whatever the rest of the sketch does. The residual keeps at least the smaller of $\sigma_i$ and $\sigma_j$, which is at least $\sigma_{10}$, which is 1.25 times $\sigma_{11}$, so a single such collision pins the error above one.

How often does that happen? Ten columns hashed independently into twenty buckets all land in different buckets with probability 20·19·…·11 / 20¹⁰ ≈ 0.065. So on about fifteen draws in sixteen at least one pair of leading directions has merged.

The prediction holds draw by draw. Four of the forty draws hashed the ten leading columns into ten different buckets, and their median error is 1.39. With one direction merged the median is 2.69; with two, 3.48; with three, 4.10; with four, 6.58. The error is held up by the largest singular value that was lost, and every additional merge is another chance that the lost one sits near the top of the spectrum, where a step up is a factor of 1.25.

Even the draws with no collision among the leading ten are more than three times worse than the Gaussian’s 0.41. The other fifty-four columns are hashed into the same twenty buckets, about three to a bucket, and each leading direction arrives mixed with two or three minor ones. The basis captures the ten leading directions but has almost nothing left with which to separate the next ten, and those next ten are what a width-20 basis uses to push the error below $\sigma_{11}$.

Widening the sketch does not repair it #

The natural response to a sketch that is too crude is to make it wider, and the first figure already shows why that does not work here. Between width 12 and width 24 the Gaussian median falls tenfold, from 1.81 to 0.18. The one-nonzero median falls from 5.29 to 3.01, and its worst draw from 8.2 to 6.7.

The collision argument predicts this. With 24 buckets the ten leading columns are all separated with probability about 0.11 — better than 0.065, but still leaving seven draws in eight with a merged pair. The number of buckets would have to grow like the square of the number of important columns before collisions became rare, which is the birthday problem, and at that width the sketch is no longer a cheap way to find ten directions.

The width controls how much of the range a sketch can hold. It does not control which directions the sketch can tell apart. Those are different properties, and on a Gaussian sketch they come together; on a hashed one they do not.

Three nonzeros a row, and why three #

With s nonzeros a row, each column of A is split into s buckets with independent signs, and two columns are merged only if they land in all the same buckets. At s = 2 that is already rare, and the median falls to 0.82; but a partial overlap — two columns sharing one of their two buckets — still leaves them poorly separated, and the worst of twenty draws is 3.99. At s = 3 the median is 0.409 against the Gaussian’s 0.407 and the worst 0.99 against 0.78. At s = 4 the worst is 0.65, below the Gaussian’s own worst draw, and eight nonzeros add nothing more.

On the incoherent matrix the same sweep is flat, because there was nothing to repair. That flatness is the useful part of the figure: a code that uses three nonzeros a row pays three times the cost of CountSketch on every matrix and receives the benefit only on coherent ones, but it does not have to know in advance which kind of matrix it has.

The repair is a standard one. Sparse embeddings with a small constant number of nonzeros per row are what the theory of oblivious subspace embeddings recommends when the input may be arbitrary, and the measurement here puts a size on what the one-nonzero version gives up when that recommendation is ignored.

The Hadamard transform never had the problem #

The Hadamard sketch on the coherent matrix is the most instructive line in the first figure, because it is the one that does nothing about collisions and suffers no collisions. Its median at width 20 is 0.37.

The transform does the mixing that the coherent matrix lacks. A column of A that is a single direction, multiplied by a random-signed Walsh–Hadamard matrix, is spread evenly across all 64 coordinates with magnitude 1/8 each: after the transform no direction lives in a particular column any more. Keeping twenty random columns of the transformed matrix is then sampling an incoherent matrix, which is the case that works.

The cost of that mixing is paid in the tail. At width 15 the Hadamard sketch’s worst draw on the coherent matrix is 2.99 against the Gaussian’s 1.75, and at width 24 it is 0.54 against 0.25. Subsampling columns of an orthogonal transform is a coarser randomisation than drawing every entry independently, and on a matrix this small the difference shows up in the worst of twenty rather than in the median.

A median hides the draw a user receives #

Every comparison above is made twice, on the median and on the worst of twenty, and the two do not always tell the same story. On the incoherent matrix the medians of all four sketches agree to within 15 per cent while the worst draws spread by nearly half; on the coherent matrix the Hadamard sketch has the best median of the four and one of the worse tails. A user runs one draw, not twenty, and receives whichever of them the seed produces.

That is the point an answer that changes with the seed made about the Gaussian range finder used as a regulariser, and what a single draw cannot report made about oversampling: the spread across seeds is the quantity a single run cannot see, and it is the one that decides whether the run’s number means anything. Here it matters in a sharper form. A cheap sketch that matches a Gaussian in the median and is twice as bad in its tail has not matched it, because a bound that holds with probability is a statement about the tail, and the tail is where the sketches differ.

On the one-nonzero sketch and the coherent matrix the distinction disappears, because the failure is not a tail at all: fifteen draws in sixteen merge a leading pair, so the typical draw is the bad one. That is what separates a sketch with a heavier tail from a sketch that does not fit the matrix.

A slower spectrum hides the failure #

On a spectrum falling like 1/j the one-nonzero sketch is 1.75 times worse than a Gaussian rather than eight, and a user comparing the two on such a matrix would call the difference moderate. The mechanism is the same — merged leading columns remove directions from the range — but the lost singular values are close to $\sigma_{11}$, so losing one costs a factor near one instead of a factor that grows by 1.25 for every step the lost direction sits above the eleventh.

That is the opposite of how the spectrum usually acts on a randomised method. Randomisation does not create structure found that a flat spectrum makes every randomised approximation bad, because there is nothing to find; here a slowly decaying spectrum makes a bad sketch look almost acceptable, because what it fails to find is worth little. A test of sketch quality on a slowly decaying matrix is therefore a weak test. The spectrum on which a hashed sketch’s failure is largest is exactly the one on which a randomised range finder is otherwise most accurate.

What each sketch costs, and what it buys #

Three sketches sit in a flat row near 0.4, and one has a stalk. The Gaussian costs 81,920 multiply-adds, the Hadamard transform 24,576, three nonzeros 12,288 and one nonzero 4,096. Coherence moves the first three by at most 0.07 and moves the cheapest by a factor of 7.4.

So the trade on this matrix is not the one the dimension does not appear described. The cheapest sketch saves a factor of three over the next cheapest and costs a factor of eight in accuracy on a coherent input. Three nonzeros a row are six to seven times cheaper than the Gaussian and match it in the median on both matrices, and they are the point on this figure at which cheap and reliable meet.

The counts are multiply-adds on a dense matrix, where the Hadamard transform’s n log n is honest only because 64 is a power of two. On a sparse A the comparison shifts further toward the hashed sketches — applying s nonzeros per row costs s times the nonzeros of A, while a Hadamard transform must touch every row of the product — which is why sparse embeddings are the ones used on sparse inputs, and why their failure mode on coherent inputs matters. The same 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.

Where coherent matrices come from #

A matrix whose important right singular directions sit on particular columns is not exotic. A term–document matrix in which a handful of terms carry most of the variation, a feature matrix with a few dominant features, a covariance matrix of variables with very different scales that nobody standardised — each has a small set of columns with leverage near one. Two observations that hide each other and its neighbours studied the same concentration on rows, where a high-leverage row decides a fit on its own.

The measured matrix is the extreme case, with leverage exactly one on ten columns and zero elsewhere. Real inputs lie between it and the incoherent twin, and the error of a one-nonzero sketch should lie between 0.45 and 3.33 accordingly. The column leverages of the leading subspace are what would place a given matrix on that range — and computing them needs the singular vectors that the sketch was supposed to find.

What this rests on #

Sixty-four-square matrices with a fixed seed for their singular vectors, twenty sketch seeds for each point and forty for the collision scatter; a rank of ten; widths from 12 to 24. The error is the exact spectral norm of the residual, and the costs are counts rather than timings. On a matrix this small, collision probabilities are large and the gaps are wide; on larger matrices with more buckets per important column they shrink, and how fast is not measured here.

The claim that has to fail #

The claim is the tempting summary of the incoherent figure: that a sketch with l columns finds the same range as a Gaussian with l columns whatever kind it is, so the cheapest is the right choice. On the coherent matrix at width 20 a one-nonzero sketch has a median error of 3.33 times $\sigma_{11}$ against the Gaussian’s 0.41, and the refusal is fed the claim that the two medians are within half again of each other and fails.

Still open: how many columns count as coherent, and a sketch that adapts #

Partial coherence. Between leverage one on ten columns and leverage spread over all of them lies every matrix a user meets. Mixing the two right-singular bases in a controlled proportion would place the one-nonzero sketch’s median as a function of the largest column leverage, and would say how coherent an input must be before three nonzeros a row stop being optional.

Hashing that avoids collisions it can see. The failure is a collision among a few heavy columns, and column norms are cheap to compute before any sketch is drawn. A sketch that gives the heaviest columns their own buckets and hashes the rest is a hybrid of column sampling and CountSketch, and whether it keeps the cost of the one while losing the failure of the other is unmeasured.

The stopping rule with a cheap sketch. The rank a certificate charges measured the adaptive rule with Gaussian probes. Its probes need to be Gaussian for the certificate to hold, while its basis columns need not be; a rule that grows the basis with a sparse sketch and certifies with a few dense probes separates the two costs, and how the four ranks move under it is the next measurement.