Sketching what is never unfolded

This field’s first four essays are about a matrix. Multiply it by a few random vectors, orthogonalise what comes back, and the resulting subspace captures the leading singular directions with a probability rather than a guarantee — which is the sentence the whole field exists to make precise.

Carrying it to a tensor runs into an arithmetic problem before any of the probability applies.

The size of the random matrix #

A mode-k unfolding is nₖ × nᵈ⁻¹: a few rows and, at d = 6 and n = 8, thirty-two thousand columns. To sketch it, a random matrix with nᵈ⁻¹ rows is required.

Counting across all d modes at r = 4 and five columns of oversampling gives

The dense column crosses the tensor’s own entry count at four indices and is seven times it by six. A range finder that has to allocate a random object larger than the thing it is looking at has saved nothing, and the field’s whole proposition — the same quality for fewer passes over the data — has become the same quality for more storage than the data, which is the trap a format falls into one field over.

The structured sketch #

The repair is to stop drawing a general random matrix and draw a random matrix that happens to be a Khatri–Rao product of d − 1 small Gaussians.

Each of its columns is then an outer product of d − 1 random vectors of length n, so ℓ columns cost (d − 1)·n·ℓ numbers. And applying it to an unfolding is not a dense multiplication: it is ℓ passes of d − 1 mode products, each of which touches the tensor once and forms nothing the size of it.

The counting is on the table above. At five indices it is 1,440 random numbers instead of 184,320, and at six it is 2,160 instead of 1,769,472 — a factor of 819.

What it is not is Gaussian. Its columns are neither independent of one another in the way the field’s theory assumes nor individually Gaussian, so every bound in the previous four essays stops applying. That is not a small caveat: the entire content of this field is that a bound holds with a probability, and here there is no bound.

What the field’s bounds actually assume #

It is worth being specific about which assumption the structure breaks, because “the bounds do not apply” is too coarse to act on.

The randomised range finder’s error bound is an expectation over a Gaussian matrix, and its proof uses two properties. Rotational invariance: a Gaussian matrix has the same distribution after multiplication by an orthogonal matrix, which is what lets the analysis change to a basis where the target’s singular vectors are the coordinate axes. Independence of the entries, which gives the concentration that turns an expectation into a statement holding with high probability — and which a reused sketch also destroys, by a different route.

A Khatri–Rao matrix has neither. Its columns are outer products, so an entry in row (i, j) is the product of an entry indexed by i and one indexed by j — a strong dependence across rows — and rotating it does not give another matrix of the same kind.

What is known about such matrices is weaker and more recent, and the honest summary is that the bounds that exist have constants depending on d and are not sharp enough to be quoted as a design rule. So the position this page takes is the one the collection takes everywhere else when a bound is unavailable: measure it, report the number, and say what the number is of.

What to measure, when there is no bound #

“Measure it and report the number” is the right response and it leaves open which number. The typical error is the obvious one and it is not the one the missing bound would have controlled: a bound on a randomised method is a statement about the worst draw, holding with a probability, and what a method without one has instead is a spread.

So both sketches are run over thirty-two seeds, and both numbers reported:

The median penalty is 7 to 12 per cent. That is the small number, and it is the one a comparison of typical errors reports.

The spread penalty is 30 to 55 per cent — 3.24 against 2.08 on the smooth family, 2.66 against 1.82 on the Hilbert one. The structured sketch’s bad draws are half again as bad as the dense sketch’s bad draws, and that is a penalty on precisely the quantity the theory would have bounded if the theory applied.

Which makes the trade two numbers, not one #

One caution on the spreads themselves, since they are the load-bearing numbers. A worst-over-32-draws is an order statistic, and an order statistic of a heavier-tailed distribution grows with the sample even when the distributions are the same — so part of any gap between two worst-of-32 figures could be the two distributions having different shapes rather than different scales. What rules that out here is that the best draws agree closely — 9.82·10⁻⁴ against 9.87·10⁻⁴ on the smooth family, 5.18·10⁻⁴ against 5.35·10⁻⁴ on the Hilbert one — so the two distributions share a lower end and differ at the upper one, which is a difference in tail rather than in location.

The structured sketch is 819 times smaller, typically a tenth worse, and its worst case is half again as bad as the dense sketch’s worst case. All three are needed to state the trade, and only the first two survive a comparison of medians.

That matters because of what replaces the bound in practice. A method with a guarantee can be run once: the guarantee covers the draw that happened. A method without one has to be run with the worst draw in mind, or run twice and compared — and the number that decides how much margin to leave, or whether two runs are enough, is the spread rather than the median.

The noise row is the control and it says which of the two the structure is costing. There the two spreads are 1.02 and 1.01 — identical — because there is no leading subspace to find and both sketches fail equally. So the structured sketch’s extra variability is not a property of its arithmetic or of its smaller random object; it is a property of how reliably it finds signal that is there, which is exactly what the field’s bounds are about and exactly what cannot be quoted here.

That is the honest position, and it is narrower than either “the structured sketch is fine” or “the bounds do not apply”. The structured sketch is fine on average, measurably less reliable at the tail, and the size of the tail is a measurement on four families at one shape — which is evidence, and is not a bound, and the difference between those two words is the whole reason this section exists.

So it is measured #

When the theory runs out the only honest thing left is an experiment, and this collection’s habit is to run it and report both numbers rather than to argue that the structured sketch is probably fine.

Three curves on the accuracy figure: the deterministic decomposition, which is a floor nothing random can go below; the dense sketch, whose theory is the field’s; and the structured one, whose theory is nothing.

At rank four on a smooth 12 × 12 × 12 array, medians over five seeds:

With no oversampling the structured sketch is nearly three times worse. At five extra columns it is 2.9 per cent worse and at ten it is 1.1 per cent worse.

That is the finding, and it is a measurement rather than a bound: the structure costs something, it costs it mostly at zero oversampling, and a handful of extra columns buys it back.

The floor moves by six orders across the slider and the sketch’s distance from it does not.

Rank two is where the floor is highest and the sketch’s shortfall smallest in relative terms. Six ranks further up, the floor has fallen by seven orders and the shortfall has grown:

At ranks 2, 3, 4, 5, 6 and 8 the floor reads 0.0671, 0.0122, 8.81·10⁻⁴, 1.16·10⁻⁴, 7.94·10⁻⁶ and 4.09·10⁻⁹, and the best a dense sketch reaches at full oversampling reads 0.081, 0.015, 0.001, 1.3·10⁻⁴, 9.8·10⁻⁶ and 5.6·10⁻⁹. The ratio between them is 1.21, 1.23, 1.14, 1.12, 1.23 and 1.37 — between twelve and thirty-seven per cent, at every rank, with no trend.

That is the essay’s claim as a constant rather than as a demonstration. A sketch does not approach the deterministic answer as the rank rises; it stays a fixed fraction above it while both fall by six orders of magnitude. The oversampling buys the distance down to that fraction and no further.

And what the oversampling itself is worth grows with the rank. Within each rank the first oversampling step to the last improves the dense sketch by 2.3×, 4.0×, 3.2×, 6.2×, 12× and 4.6× — so the extra columns matter more where there is more structure to miss, and a fixed oversampling is a different amount of insurance at each rank.

The two sketch types are a wash at full oversampling and not at none. With every extra column the dense and structured sketches read 0.081/0.086, 0.015/0.015, 0.001/0.0011, 1.3·10⁻⁴/1.7·10⁻⁴, 9.8·10⁻⁶/9.7·10⁻⁶ and 5.6·10⁻⁹/5.5·10⁻⁹ — within thirty per cent, with the structured one ahead at two of the six. With none, the structured sketch is worse at low rank (0.24 against 0.19 at rank two, 0.0063 against 0.0032 at rank four) and better at rank eight (2.2·10⁻⁸ against 2.6·10⁻⁸). The structure costs something when the subspace is small and nothing when it is not.

The defect that made the answer worse with more columns #

One implementation error on this page cost more than everything else on it, and it is worth recording because its symptom was a monotone quantity going the wrong way.

The first version took a QR of the sketch and kept its first r columns. Measured, the error rose from 2.9 to 6.9 times the deterministic answer as the oversampling went from zero to ten — that is, giving the method more information made it worse, consistently, across every seed.

The reason is that a QR’s columns are an orthonormal basis for the sketch’s column space in an arbitrary order. Truncating them keeps an arbitrary r-dimensional slice of that space, and a wider sketch means a larger space to pick badly from. The repair is one line: decompose the sketch itself, which is nₖ × ℓ and costs nothing, and keep the directions carrying the most of it.

Nothing else would have caught it. Every intermediate quantity was finite, ordered and plausible; the bases were orthonormal to the rounding level; the projections were projections. What caught it is that the figure has an oversampling axis and the curve on it has an expected direction.

That is the same shape as the hierarchy field’s peeling defect, which returned a relative error of 0.25 with every intermediate quantity correct — and the same lesson: a sweep over a parameter whose effect is known in direction is a test even when its value is not known.

What the seed decides #

The field’s standing question, asked of this format.

Over eight seeds at rank four with five columns of oversampling, the spread between the best and worst answer is 1.66 on the smooth family, 1.47 on the Hilbert family, and 1.014 on independent normal entries. No seed beats the deterministic decomposition on any of them, which the assertion checks family by family.

The last row is the counterweight. On a tensor with no structure the sketch is stable across seeds and the answer is 0.97 — stable, reproducible, and useless. A small spread is not evidence that a randomised method is working; it is evidence that the answer does not depend on which subspace was found, which happens both when every subspace is good and when none is.

The three sources of error, kept apart #

A sketched decomposition has three separate things wrong with it and confusing them makes the numbers above unreadable.

The truncation. Even with the exact leading subspace, keeping rank r discards energy. That is the floor on every figure here and it is the previous field’s subject: quasi-optimal, within √d of the best, and sitting on its upper bound.

The subspace. A sketch finds a subspace that is not quite the leading one, and the gap between them is what oversampling closes. This is what the field’s bounds are about.

The random matrix’s structure. A Khatri–Rao sketch finds a slightly different subspace again, for reasons that have nothing to do with how many columns it has.

The measurements separate all three. The floor is the deterministic curve; the dense sketch’s distance above it is the second; and the distance between the two random curves is the third. At ten columns of oversampling those are 1.08·10⁻³, a factor of 1.00, and a factor of 1.011 — so on this family the truncation is essentially the whole of the error and the two random effects are rounding on top of it.

What it is actually for #

A sketched decomposition costs one pass over the tensor per mode and a deterministic one costs the same, so the saving is not in passes here — it is in what a pass does.

A deterministic mode-k decomposition needs the leading singular subspace of an n × nᵈ⁻¹ matrix, and the cheapest honest route to it is a decomposition of the transpose, which is nᵈ⁻¹ × n. That is a Jacobi sweep over n columns of vectors with nᵈ⁻¹ entries: affordable, and it touches every entry sixty times.

A sketched one touches every entry ℓ times, with ℓ = r + 5, and then decomposes an n × ℓ matrix. At r = 4 that is nine passes against sixty, and the difference grows with the accuracy the Jacobi sweep is run to.

The other saving is the one that matters at scale and this page does not measure: a structured sketch can be applied to a tensor that is never formed, since the mode products can be composed with whatever produces the entries. That is the same argument the hierarchy field’s construction-from-products essay makes, and it is why this variant exists at all.

Where it leaves the field #

This field’s four earlier essays are all about matrices, and three of their findings survive the move unchanged while one does not.

A bound that holds with probability survives, for the dense sketch, and is unavailable for the structured one. That is the change, and it is a change of kind rather than of degree: what replaces the bound is a measurement over seeds, which is a weaker object because it describes the tensors that were tried.

Randomisation does not create structure survives exactly. The noise family is 0.97 under every sketch, every seed and every amount of oversampling, and the deterministic decomposition is 0.94. A method that finds nothing finds nothing faster.

The dimension does not appear survives with a caveat worth stating. The number of columns needed is still r + p rather than anything depending on the ambient size — that is the field’s headline and it holds here. What does depend on the ambient size is the cost of a column, which for a dense sketch is nᵈ⁻¹ numbers and for a structured one is (d − 1)n.

A sketch that is spent survives and is sharper here. Reusing one random matrix across all d modes would save nothing in the structured case, since the draws are already negligible, and would introduce a dependence between the d subspaces that no analysis covers. The measurement here draws fresh vectors per mode for that reason.

The refusal #

The claim under test is the one that makes a sketch sound unconditionally cheaper: that it is a substitute for a decomposition, so the random matrix is an implementation detail.

The assertion that the dense sketch is smaller than the tensor it sketches is fed six indices at eight points a side. It fails, at 1,769,472 random numbers against 262,144 entries.

That refusal is what makes the structured sketch a necessity rather than an optimisation. Without it, the previous section’s accuracy penalty would look like a price paid for a small saving; with it, the alternative is not available at all past four indices.

The file’s other refusals cover the two flattering readings. One is fed the seed spread on two families and required to refuse the claim that a sketch improves on the decomposition — nothing random beats a projection onto the leading subspace, and an assertion that it does would pass on a family reproduced exactly and mean nothing. The other is fed the zero-oversampling case and required to refuse the claim that no oversampling is as good as some, which is the whole reason the parameter exists.

What it would cost to be sure #

The measurement above is over five seeds on one family at one rank, which is enough to establish a penalty of a few per cent and is not enough to establish anything about a tail. That is worth saying, because the difference between a median and a worst case is the difference this collection’s cost field makes about heuristics.

A worst case for a randomised method is not obtainable by more seeds — the tail of a distribution is exactly what a finite sample does not see. What is obtainable is a failure probability, and for the dense sketch the field’s bounds supply one. For the structured sketch there is no such bound and the honest position is that the worst case is unknown.

What follows practically is that a code using a structured sketch should carry a check, and the check is cheap: form the residual of the resulting representation against the tensor, which costs one more pass, and repeat with a different seed if it is worse than expected. That is a posterior verification rather than a prior guarantee, and it is the same trade the interval-arithmetic essay in the arithmetic field describes — a method that declines rather than lying.