What a single draw cannot report

A construction that never looks at the matrix has to look at something, and what it looks at is a random matrix. Built from products alone counts what that costs — a few hundred applications of an operator that is never assembled, against the n² entries the other route reads — and every accuracy in that count is a number one draw produced. Change the seed and the representation changes while nothing about the matrix has changed at all.

That makes every figure of this construction a claim about a distribution, and there are two numbers in a distribution that a code cares about. The first is where it sits: how far the sampled representation is from the best representation of the same rank, which is what a decomposition of every block would return. The second is how wide it is: how far apart two runs of the same code on the same matrix can land. A run reports the first and cannot report the second, because one draw is one draw.

The quantity that settles this essay is therefore not an error but a spread, and the awkward part — the part the measurement turned out to be about — is that a spread has to be estimated too. Five seeds give a mean and a range. What five seeds do not give is any assurance that a second five would have given the same range, and at the setting where the spread is widest they do not.

Both halves are the measurement and a line shows one of them #

At rank eight, on a 128-square kernel matrix with a leaf of sixteen, the mean excess over the best representation of the same rank runs 11.6, 8.2, 6.9, 4.6, 3.0 and 2.5 as the oversampling goes 0, 1, 2, 4, 8, 16. That is the half a single run can report, and read alone it says something reasonable: extra columns buy accuracy at a decreasing rate, and sixteen of them buy a factor of 4.6 over none.

The spread across the five seeds, as a percentage of the mean, runs 44, 17, 21, 13, 12 and 7 over the same six settings. That is the half a single run cannot report at all, and it is the one that decides what the first half means. A code that ran once at no oversampling and published its error published a number that a rerun could have moved by nearly half.

What the extra columns cost is fixed and small. The construction performs 112 products at rank eight with no oversampling and 208 with sixteen, and the difference — 96 — is the same 96 at every rank the sweep runs, because the oversampling enters the count as 2p per level and the levels do not depend on the rank. At rank four that is 64 products becoming 160, which is two and a half times the work; at rank twelve it is 160 becoming 256, which is 1.6 times. So the proportional price of a trustworthy number falls as the rank rises, which is the opposite of what a cost table suggests and is worth knowing before the rest of this essay argues about how much of that price is worth paying.

The mechanism behind the accuracy is the range finder every block is built on: a random matrix with k + p columns is applied to the block, and the first k left singular vectors of what comes back are taken as a basis for its range. With p = 0 the sample has exactly as many columns as the subspace being sought, so a draw that is nearly deficient in one direction has no spare column to recover with. With p = 16 there are sixteen spare directions and the chance of missing badly is small. That is the argument the field’s probabilistic bounds make, and it predicts both a lower mean and a narrower spread. The measurement below is about how well each of those two predictions can be checked.

The widest band sits at the highest rank, which is the wrong way round #

Rank twelve is the most accurate setting the sweep runs. The best representation of that rank has a relative error of 9.5·10⁻¹², eight decades below rank four’s 2.6·10⁻⁴, and it is where a code that wanted digits would work. It is also where the construction is least predictable: 50.0 times the optimum at no oversampling, with a seed-to-seed spread of 146 per cent of the mean.

A spread larger than the mean means the largest of the five draws is more than twice the smallest, and in this case the five errors at p = 0 span from 6·10⁻¹¹ to 1.1·10⁻⁹. A single run at that setting reports one point in a range covering more than a decade, so it carries essentially no information about what a rerun of the identical code will do.

There is a reason the high rank is the unstable one and it is not a defect of the sampling. By rank twelve an off-diagonal block of this kernel has already given up almost everything it has; the rank that is really a number of digits measures the exchange rate at about half a column a decade, so the twelfth column is buying a direction whose singular value is twelve orders below the first. Sampling a direction that small is sampling something the rest of the block barely distinguishes from nothing, and the range finder’s chance of catching it cleanly is correspondingly a matter of luck.

That suggests an ordering — the higher the rank, the worse the excess at no oversampling — and the ordering is not there. Across the nine ranks the sweep will draw, the mean excess at p = 0 reads

k   4     5     6     7     8     9     10    11    12
    15.0  17.5  13.8  26.8  11.6  23.1  15.7  25.1  50.0

which rises, falls, rises, falls, rises, falls, rises and then trebles. Rank eight, in the middle, is the best-behaved of the nine. Rank seven is worse than rank nine. No account of the construction predicts that shape, and the next section is about why no account should be asked to.

The left-hand edge is an estimate of an estimate #

Rank six is the quietest of the nine at no oversampling: a spread of 16 per cent where rank five reads 75 and rank seven reads 62. Nothing about rank six is special. It happens to be the rank at which the five particular seeds this sweep uses landed close together.

The test for that reading is cheap and decisive. Run the same nine ranks again on a disjoint set of five seeds, and compare the two estimates of the same quantity:

The two rows disagree at rank twelve by a factor of 3.7 — 50.0 against 13.6 — and at rank eight by a factor of 2.8 in the other direction. Rank eight is the smallest entry in the first row and the second largest in the second; rank twelve is the largest in the first and the second smallest in the second. Ranked by their p = 0 excess, the two orderings have a rank correlation of −0.167, which is not merely weak agreement but none: the ordering the first row appears to establish is not reproduced at all by the second, and its slight negative sign is itself noise.

So the shape of the p = 0 column is not a property of the rank. It is a property of five numbers, and five samples of a quantity whose own spread reaches 146 per cent of its mean estimate that quantity badly. This is the same reading an answer that changes with the seed arrives at from the direction of a solve, and the variation that comes with a seed from the direction of the machine: the seed is an input to the answer, and a figure that hides it has hidden an input.

The consequence for the bands drawn in this essay is specific and worth stating flatly. The left-hand edge of every one of them is drawn where five draws happened to fall. Its height is not a measurement and neither is its ordering against the left-hand edge of the band above it.

The spread has a spread, and at rank seven it is a factor of ten #

The second column has the same problem as the first, and rank seven shows it without ambiguity. Its spread across the six oversampling settings reads 62, 35, 7, 73, 19 and 8 per cent. Between two adjacent settings — two extra columns and four — the estimated spread moves by a factor of ten, in the wrong direction, on a quantity every account of the method says falls monotonically.

Nothing in the construction moves that way. Four columns of slack cannot be worse than two: the sample is strictly larger, the subspace it sees strictly contains what a two-column sample would have found in expectation, and the mean excess at those two settings duly reads 5.6 and 5.7, which is a difference of nothing. What moved by a factor of ten is not the width of the distribution but the estimate of it, computed from five numbers.

That is why the figure’s own machinery reports the spread and asserts nothing about it. The construction runs an assertion that the excess at no oversampling is more than three times the excess at eight columns, which holds at every rank the sweep draws; it runs no assertion that the spread falls, because at rank six the spread reads 16 per cent at no oversampling and 23 per cent at eight, and an assertion that failed there would be an assertion about which five seeds were used. The distinction is the site’s usual one arriving in an unusual place: the mean is a quantity the code can be held to, and the spread at this sample size is a quantity about which the honest report is the number and its provenance.

There is a general shape here worth naming, because it is what makes a heavy-tailed quantity awkward rather than merely noisy. The excess at p = 0 is a ratio whose numerator occasionally takes a very large value — a draw that misses the subspace badly — and a five-sample mean of such a quantity is usually below the true mean and occasionally far above it. That is exactly the pattern the two rows of the table show: seven of the nine pairs sit between 11 and 35, and the disagreements are concentrated in the two ranks where one row caught a large draw and the other did not.

Where it narrows, it narrows to five per cent #

Rank ten is what the argument for oversampling looks like when the estimate is not fighting itself. The spread reads 85, 48, 44, 24, 5 and 5 per cent — down at every step, by a factor of seventeen overall, and flat once eight extra columns have been paid for. The mean excess runs 15.7, 9.1, 6.9, 4.7, 3.0 and 2.8 over the same settings, so the two halves move together and the figure says the thing the field says it should.

Set that against rank six, four figures above, where the spread reads 16, 34, 59, 28, 23 and 20 and ends wider than it began. Both are five-seed estimates of the same kind of quantity on the same matrix at neighbouring ranks. One of them traces the textbook curve and one of them does not, and no property of rank six or rank ten distinguishes them.

What distinguishes them is where they are being read. Rank ten’s spread falls to 5 per cent and stays; rank six’s wanders between 16 and 59 without leaving that interval. The wandering is confined to the region where the spread is large, and the settling happens in the region where it is small. A five-sample estimate of a small, well-behaved spread is a reasonable estimate. A five-sample estimate of a large, heavy-tailed one is not, and both figures are showing that fact rather than showing anything about their ranks.

Which turns the essay’s question around. The interesting reading is not which rank behaves best at no oversampling — that question has no stable answer — but whether the right-hand end of these bands, where every rank claims to have settled, is a measurement or another accident of five seeds.

The right-hand edge is a measurement, and that is what oversampling is for #

The same test that destroyed the left-hand edge can be run on the right. Two disjoint sets of five seeds, nine ranks, sixteen extra columns:

The largest disagreement between the two rows is 12 per cent, at rank six, and six of the nine pairs agree to within 5 per cent. Their rank correlation is 0.900 against the −0.167 the p = 0 column returned, and both rows show the same gentle rise with the rank, from about 2.0 at rank four to about 2.9 at rank twelve. Two independent experiments agree on the value, on the ordering and on the trend.

So the two ends of every band in this essay are objects of different kinds. At p = 0 a five-seed estimate of the excess is reproducible to a factor of 3.7. At p = 16 it is reproducible to 12 per cent. The same five seeds, the same code, the same matrix, the same nine ranks — and the number is a measurement at one end of the figure and not at the other.

That is a second reason for oversampling, and it is not the reason usually given. The first is accuracy: sixteen extra columns take the excess from between 11.6 and 50 down to between 2.0 and 2.9, for 96 more products. The second is that they take the reported error from a quantity a five-run experiment cannot pin down to one it pins to a tenth. A code that oversamples is not only more accurate; it is a code whose accuracy can be quoted. Four extra columns, the conventional choice, already reach a spread of 13 to 29 per cent across the ranks, at a cost of 24 products, which is why that choice survives.

And this is the point at which the caution has to be applied to the essay’s own headline. The claim that the excess falls from 11.6–50 to 2.0–2.9 is not one claim but two. The second range is measured. The first is the range of nine badly-estimated numbers, and a second experiment would produce a different one — 11.9 to 35.4, as the table above shows. What survives both experiments is the direction and the order of magnitude: without oversampling the construction is tens of times worse than the representation it is approximating, and with sixteen columns it is between two and three times worse, at every rank tried.

The floor is the check that the comparison is honest #

Every one of these figures carries a flat dashed line, and it is not a reference drawn for scale. It is the error of the best representation of the same rank — every block decomposed from its entries, truncated to k — which is what the best approximation there is guarantees no other rank-k object can beat. A sampled representation is a rank-k object, so the flat line is a bound the measurement must respect.

Across nine ranks, six oversampling settings and ten seeds — 540 draws — the closest any single draw came to that line is 1.825 times it, at rank four with sixteen extra columns. Not one went under. That matters more here than in a figure whose numbers are reproducible, because everything else on these bands moves: if the excess at p = 0 can read 50.0 or 13.6 depending on the seeds, an experiment that occasionally produced 0.9 would be indistinguishable from one more piece of scatter. The floor is the one quantity in the sweep that does not move, and it is therefore the one that can catch a bug.

It also marks the boundary of what the randomness is doing. Randomisation does not create structure makes the argument in general — a random projection finds what is there and invents nothing — and the floor is that statement in the form a sweep can check. Every number above the flat line is a sample failing to reach an optimum; a number below it would be a sample beating a decomposition it approximates, which is not a better method but an arithmetic error.

The same construction from the other side, where one seed is enough #

The compression route is handed an accuracy and returns whatever rank that costs. This one is handed a rank and returns whatever accuracy that buys, because the random matrix is drawn before a single entry of the block has been seen. Read that way, the object of interest is not a ratio at a setting but a slope: how many decades of accuracy each extra column buys.

The slope moves with the size of the matrix, and it moves a long way. At 64 unknowns it is 1.08 decades a column, at 128 it is 0.90, and at 256 it is 0.74. A bigger matrix has more blocks to get wrong and deeper peeling between them, so the same column buys fewer digits.

That figure is drawn from one seed, which by every argument above ought to be inadmissible. It is not, and the reason is measurable. Recomputing the slope at each size from five separate seeds gives 1.068, 1.077, 1.080, 1.079 and 1.062 at 64 unknowns; 0.883, 0.883, 0.898, 0.878 and 0.885 at 128; and 0.743, 0.756, 0.738, 0.765 and 0.785 at 256. The seed moves the slope by at most 0.018, 0.020 and 0.047 at the three sizes. The size moves it by 0.19 and 0.13. The effect being reported is four to ten times larger than the variation a change of seed produces, so one draw settles it.

The difference is in what is being read off the picture. A slope is fitted through six points spanning ten decades, and the fit absorbs the scatter each individual point carries; a ratio at one setting is one point, and it carries all of it. That is a general property rather than an observation about this construction, and it is what makes a single-seed figure legitimate here and illegitimate two sections above.

The same figure carries the counterexample in its own margin. Its excess over the optimum, rank by rank, reads 2.2, 2.2, 4.1, 3.5, 2.8 and 3.2 — a single draw at each of six ranks, wobbling by a factor of nearly two with no trend in it. That column is the same quantity the bands in this essay put a range on, drawn without one, and it moves exactly as much as the bands say it should.

What a code should report #

Report a spread, not an error. A hierarchical representation built from products is one draw. A code that returns its residual returns a sample, and the cheapest honest fix is to build twice with different seeds and report both, which costs a second construction and no analysis at all.

Choose the oversampling for the spread rather than the mean. Four columns take the excess from between 11.6 and 50 to between 3.6 and 5.7 and the spread from 16–146 per cent to 13–29, for 24 more products at rank eight. Sixteen columns take the spread to between 4 and 20 per cent for 96. The accuracy argument alone would stop earlier than either.

Do not rank-order anything on a five-seed estimate at no oversampling. Two disjoint sets of five seeds put rank eight first and second-last on the same nine ranks. Any comparison — of ranks, of leaf sizes, of two implementations — made at that setting is comparing seeds.

Check the floor rather than the value. The one assertion that survives all of this is that no draw beats the decomposition of its own rank, which held over 540 draws with the closest at 1.825 times. That is the shape of check worth writing when the quantity itself is a distribution, and it is the same discipline the sketch that is not the answer applies when it moves the randomness out of the answer and into a preconditioner, where the reported number stops moving at all.

And carry the caution into the neighbouring fields. Sketching what is never unfolded measures a structured sketch against a dense one by comparing medians and spreads over seeds, and the sketch that is spent measures what a reused draw is worth. Both are reading quantities of exactly the kind this essay finds unreproducible at small sample sizes, and both are read at settings where the spread is small.

The refusal #

The claim under test is one taught as a refinement: that oversampling adjusts a method slightly, so a code that skips it is running the same method with a little more variance.

The assertion fed the counterexample is the strict version of that — with no extra columns at all, the sketched decomposition is within a thousandth of the exact one of the same rank. It is fed a sketched Tucker decomposition at no oversampling, whose median error over three seeds is 2.2338 times the exact decomposition’s, and it fails.

That refusal runs on a tensor sketch rather than on the construction this essay measures, and the duplication is the point rather than an accident of where the assertion lives. Two different objects — a three-index tensor decomposed in a sketched subspace, and a hierarchical matrix assembled from products — return the same verdict about the same parameter, at a factor of 2.2 in one and between 11.6 and 50 in the other. A claim that fails on one object and one library is a claim about that library.

The tensor sweep also carries the essay’s own caution, unprompted and in a different code. Its median ratio at no oversampling is 2.2338 and at two extra columns it is 2.5900 — worse, on a parameter whose whole purpose is to improve it, from a three-seed median. The number of samples is smaller there and the effect is the same one: a small sample of a quantity with a long tail returns an ordering that the next small sample will not reproduce.