Numerical Linear Algebra
where the algebra stops being the arithmetic
Randomised, and the guarantee that changes kind

Sketching what is never unfolded

A range finder multiplies its matrix by a few random vectors. For a mode-k unfolding those vectors have n^{d−1} entries, so the random object is the size of the tensor divided by n — and by six indices it is larger than the tensor it is sketching.
37 min read 29 figures Where the algebra stops being the arithmeticMeasured, not assertedAssertions that reject

Worth reading first: The dimension does not appear · A bound that holds with probability · A decomposition made only of SVDs.

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.

Random numbers a sketch needs, against the number of indices, at n = 8A dense Gaussian sketch of a mode-k unfolding multiplies an n × n^{d−1} matrix by a random one with n^{d−1} rows, so the random object is the size of the tensor divided by n — the line that crosses the tensor's own entry count at d = 2 and is 1.51·10⁸ by d = 8. A Khatri–Rao sketch replaces it with d − 1 small Gaussians per column, costing 4,032 numbers at the same point — a factor of 3.74·10⁴ — and is applied as mode products, so nothing the size of the tensor is ever formed. What it is not is Gaussian, which is what the previous figure has to measure rather than bound.12345678910¹10³10⁵10⁷number of indicesrandom numbers drawna dense Gaussian sketchdashes: the tensor's own entriesa Khatri–Rao sketcha random matrix nobody can afforddense at d = 81.5·10⁸structured4032the tensor's entries1.7·10⁷dense ⁄ structured3.7·10⁴crossing at d2the sketch outgrows its tensorand the structured one does not
Fig. 1 The random numbers each kind of sketch needs, against the number of indices. The dashed line is the tensor’s own entry count, and one of the two curves crosses it.

The size of the random matrix

A mode-k unfolding is n_k × n^{d−1}: a few rows and, at d = 6 and n = 8, thirty-two thousand columns. To sketch it, a random matrix with n^{d−1} rows is required.

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

indices dense sketch Khatri–Rao sketch the tensor
3 1,728 432 512
4 18,432 864 4,096
5 184,320 1,440 32,768
6 1,769,472 2,160 262,144

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.

Random numbers a sketch needs, against the number of indices, at n = 16A dense Gaussian sketch of a mode-k unfolding multiplies an n × n^{d−1} matrix by a random one with n^{d−1} rows, so the random object is the size of the tensor divided by n — the line that crosses the tensor's own entry count at d = 2 and is 1.93·10¹⁰ by d = 8. A Khatri–Rao sketch replaces it with d − 1 small Gaussians per column, costing 8,064 numbers at the same point — a factor of 2.4·10⁶ — and is applied as mode products, so nothing the size of the tensor is ever formed. What it is not is Gaussian, which is what the previous figure has to measure rather than bound.12345678910¹10³10⁵10⁷10⁹number of indicesrandom numbers drawna dense Gaussian sketchdashes: the tensor's own entriesa Khatri–Rao sketcha random matrix nobody can afforddense at d = 81.9·10¹⁰structured8064the tensor's entries4.3·10⁹dense ⁄ structured2.4·10⁶crossing at d2the sketch outgrows its tensorand the structured one does not
Fig. 2 At a finer grid, where the crossing moves right and the dense count reaches 10⁹ — the wrong way round for comfort, since a finer discretisation is where the format is most needed.

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.

Sketch distortion against sketch width, for 40 vectorsA log-log plot of the worst relative change in vector length against the number of rows in the sketch, for vectors of two dimensions a factor of four apart. The two curves lie almost on top of one another and both fall steadily.10²10².³10².⁵⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁶10⁻¹10⁻⁰.⁵1rows in the sketchworst relative distortiondimension 64dimension 2565 seeds per point, band is best to worstthe dimension does not appear
Fig. 3 The property a dense Gaussian sketch has and this one does not, from the field’s own essay: a distortion of norms with a distribution behind it.
Random numbers a sketch needs, against the number of indices, at n = 4A dense Gaussian sketch of a mode-k unfolding multiplies an n × n^{d−1} matrix by a random one with n^{d−1} rows, so the random object is the size of the tensor divided by n — the line that crosses the tensor's own entry count at d = 2 and is 1.18·10⁶ by d = 8. A Khatri–Rao sketch replaces it with d − 1 small Gaussians per column, costing 2,016 numbers at the same point — a factor of 585 — and is applied as mode products, so nothing the size of the tensor is ever formed. What it is not is Gaussian, which is what the previous figure has to measure rather than bound.12345678910¹10²10³10⁴10⁵10⁶number of indicesrandom numbers drawna dense Gaussian sketchdashes: the tensor's own entriesa Khatri–Rao sketcha random matrix nobody can afforddense at d = 81.2·10⁶structured2016the tensor's entries6.6·10⁴dense ⁄ structured585crossing at d2the sketch outgrows its tensorand the structured one does not
Fig. 4 The same counting on a coarse grid, where the crossing is furthest right and the dense sketch is affordable longest.

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.

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.

Sketch distortion against sketch width, for 12 vectorsA log-log plot of the worst relative change in vector length against the number of rows in the sketch, for vectors of two dimensions a factor of four apart. The two curves lie almost on top of one another and both fall steadily.10²10².³10².⁵⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁶10⁻¹10⁻⁰.⁵1rows in the sketchworst relative distortiondimension 64dimension 2565 seeds per point, band is best to worstthe dimension does not appear
Fig. 5 The property being lost, drawn at a smaller sketch: a distribution of distortions, which is what the field’s bounds are statements about.
What extra columns buy a construction that never sees the matrix, over five seedsThe band is the range across five seeds and the line is their mean; the flat lower line is the best representation of rank 12 there is, which a decomposition of every block would find. With no oversampling the construction is 50.0 times behind it and the spread across seeds is 146 per cent of the mean. Eight extra columns bring it to 3.4× and the spread to 16 per cent. Both halves matter and only one of them is visible in a single run: what oversampling buys is a better answer and a more predictable one, and a figure drawn from one seed would have shown the first and hidden the second. No draw is ever better than the flat line, which is the check that the comparison is honest — a sample cannot beat the decomposition it is approximating.048121610⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸extra columns in the sample, p‖A − A_H‖ ⁄ ‖A‖the best rank-12 representationfive draws, mean and rangea band, not a lineexcess at p = 050excess at p = 83.4spread at p = 01.5spread at p = 80.16the optimum of this rank9.5·10⁻¹²one seed shows the meanand five show the risk
Fig. 6 And the band that follows from having one, from the hierarchy field’s construction.

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:

oversampling dense structured penalty
0 2.59·10⁻³ 6.98·10⁻³ 2.69
5 1.36·10⁻³ 1.40·10⁻³ 1.029
10 1.08·10⁻³ 1.09·10⁻³ 1.011

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 error of a rank-4 Tucker representation built from a sketch, against the columns of oversamplingThe flat line is the deterministic decomposition — d matrix SVDs — at 8.81·10⁻⁴, and nothing random can go below it, since every curve here is a projection onto a subspace of the same size. The upper two are medians over five seeds: a dense Gaussian sketch, which the randomised field's bounds cover, and a Khatri–Rao sketch, whose columns are outer products of small random vectors and which no bound in that field applies to. With no oversampling the dense sketch is 3.65 times the deterministic answer; at twelve extra columns it is 1.15. The structured one costs 6.8 per cent more at four extra columns and 9.5 per cent at twelve — measured, because there is nothing else to say about it.-113579111310⁻³10⁻²extra columns in the sketchrelative errora Khatri–Rao sketch: no bound covers ita dense Gaussian sketchthe decomposition, which nothing beatsrank 4, five seedsdeterministic8.8·10⁻⁴dense, p = 00.0032dense, p = 120.001structured, p = 120.0011structured ⁄ dense1.1a bound and a measurementand only one of them is available
Fig. 7 The three curves, with the floor drawn: no random subspace beats the decomposition, and the two random ones converge onto it together.
The error of a rank-2 Tucker representation built from a sketch, against the columns of oversamplingThe flat line is the deterministic decomposition — d matrix SVDs — at 0.0671, and nothing random can go below it, since every curve here is a projection onto a subspace of the same size. The upper two are medians over five seeds: a dense Gaussian sketch, which the randomised field's bounds cover, and a Khatri–Rao sketch, whose columns are outer products of small random vectors and which no bound in that field applies to. With no oversampling the dense sketch is 2.78 times the deterministic answer; at twelve extra columns it is 1.20. The structured one costs 39.4 per cent more at four extra columns and 6.6 per cent at twelve — measured, because there is nothing else to say about it.-113579111310⁻¹1extra columns in the sketchrelative errora Khatri–Rao sketch: no bound covers ita dense Gaussian sketchthe decomposition, which nothing beatsrank 2, five seedsdeterministic0.067dense, p = 00.19dense, p = 120.081structured, p = 120.086structured ⁄ dense1.1a bound and a measurementand only one of them is available
Fig. 8 At rank two, where the floor is higher and both sketches reach it sooner.

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_k × ℓ 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 extra columns buy a construction that never sees the matrix, over five seedsThe band is the range across five seeds and the line is their mean; the flat lower line is the best representation of rank 8 there is, which a decomposition of every block would find. With no oversampling the construction is 11.6 times behind it and the spread across seeds is 44 per cent of the mean. Eight extra columns bring it to 3.0× and the spread to 12 per cent. Both halves matter and only one of them is visible in a single run: what oversampling buys is a better answer and a more predictable one, and a figure drawn from one seed would have shown the first and hidden the second. No draw is ever better than the flat line, which is the check that the comparison is honest — a sample cannot beat the decomposition it is approximating.048121610⁻⁸10⁻⁷10⁻⁶10⁻⁵extra columns in the sample, p‖A − A_H‖ ⁄ ‖A‖the best rank-8 representationfive draws, mean and rangea band, not a lineexcess at p = 012excess at p = 83spread at p = 00.44spread at p = 80.12the optimum of this rank7.8·10⁻⁸one seed shows the meanand five show the risk
Fig. 9 The hierarchy field’s version of the same sweep, from the essay that uses it: an oversampling axis whose direction is the check.
Applications of an operator that is never assembled, against the entries of the matrix it stands forThe blocks at one level of the tree have disjoint column supports, so one batch of random vectors samples all of them at once: two batches a level for the ranges, two more for the projections, and one batch of leaf products for every diagonal block in the matrix together. That is leaf + 2(2k + p)·levels products, and the counter inside the operator says 112, 160, 208, 256 at n = 64, 128, 256, 512 — 48 more per doubling, which is a logarithm. The other line is n², the entries the compression route reads. At n = 512 that is 256 products against 262,144 entries, and the representation it produces is within 7.3× of the one that read them all.567891010¹10²10³10⁴10⁵10⁶log₂ nnumbers the construction touchedentries, n²products with the operatoran operator, applied a few hundred timesproducts at n = 512256entries at n = 5122.6·10⁵per doubling48‖A − A_H‖ ⁄ ‖A‖4·10⁻⁷excess over the compression7.3no entry of the matrixwas ever read
Fig. 10 And the construction whose defect had the same shape, where every number was right and the answer was not.

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.

What each round of sketch-and-deflate actually sees, for a sketch kept, half redrawn, and redrawnA randomised range finder forms Y = AΩ, takes Q spanning it, and deflates: A ← A − QQᵀA. With the same Ω the next sketch is A₂Ω = AΩ − QQᵀ(AΩ) = Y − QQᵀY, which is zero exactly, because Q spans Y. Measured, the kept sketch sees 2.62 at the first round and 9.03·10⁻¹⁵ at the second — the unit roundoff, which is to say nothing at all, and the subspace it produces after that is whatever the rounding error happened to point at. A fresh sketch stays at about 3.3, and redrawing half the columns sees about half as much. After 5 rounds of identical arithmetic the kept run is at 0.2845 and the redrawn one at 0.1126.012345610⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹round‖AΩ‖ ⁄ ‖A‖ at that roundredrawn each roundhalf redrawnkept: the sketch is now the zero matrixthe randomness is spentkept, round 12.6kept, round 29·10⁻¹⁵redrawn, round 23.1kept, final error0.28redrawn, final error0.11a random matrix used twiceis not random the second time
Fig. 11 The field’s own version of a seed deciding an answer, from the essay that measures what a reused sketch is worth.
The randomised SVD against the optimum it cannot beat, with 1 power iterationA semi-logarithmic plot of approximation error against target rank. A shaded band shows the spread across seeds, a solid line the optimal error from the exact singular values, and a dashed line the published probabilistic bound well above both.04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσ_{k+1}, optimalhow far apart the three areworst seed spread1.2bound / median at k = 1211median / optimum at k = 12160×60, 6 seeds, oversampling p = 5band is best to worst
Fig. 12 And the band a randomised low-rank approximation comes with, which is the object this page’s medians are summarising.

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.

The truncation error of a hilbert tensor against the rank kept, between the two bounds the theorem givesThe middle curve is the measured error of the projection; the upper dashed one is √(Σ_k tail_k²), which the theorem says it cannot exceed, and the lower one is max_k tail_k, which the best possible error cannot fall below. They are a factor of √3 apart. The measurement is that the projection sits on the upper one, and not between them: the ratio of error to bound runs 0.689, 0.829, 0.906, 0.950 … 0.999812, so by rank 10 the bound is attained to five decimals and the ratio to the lower bound is 1.7317 against √3 = 1.7321. That reads as a bad result and is not one — what it says is that the lower bound is weak, which only a second measurement can establish.024681010⁻¹²10⁻⁹10⁻⁶10⁻³1rank kept in every moderelative errordashes above: √(Σ tail²), the upper bounddashes below: max tail, a floor under the bestsolid: what the projection returnshilbert: pinned to the upper boundrank 10 error1.4·10⁻¹²its upper bound1.4·10⁻¹²the lower bound8.3·10⁻¹³error ⁄ bound1error ⁄ lower1.7inside the boundand sitting on it
Fig. 13 The first of the three alone, on a family with a faster spectrum, from the field that measures 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^{d−1} matrix, and the cheapest honest route to it is a decomposition of the transpose, which is n^{d−1} × n. That is a Jacobi sweep over n columns of vectors with n^{d−1} 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.

Applications of an operator that is never assembled, against the entries of the matrix it stands forThe blocks at one level of the tree have disjoint column supports, so one batch of random vectors samples all of them at once: two batches a level for the ranges, two more for the projections, and one batch of leaf products for every diagonal block in the matrix together. That is leaf + 2(2k + p)·levels products, and the counter inside the operator says 96, 136, 176, 216 at n = 64, 128, 256, 512 — 40 more per doubling, which is a logarithm. The other line is n², the entries the compression route reads. At n = 512 that is 216 products against 262,144 entries, and the representation it produces is within 7.1× of the one that read them all.567891010¹10²10³10⁴10⁵10⁶log₂ nnumbers the construction touchedentries, n²products with the operatoran operator, applied a few hundred timesproducts at n = 512216entries at n = 5122.6·10⁵per doubling40‖A − A_H‖ ⁄ ‖A‖10⁻⁵excess over the compression7.1no entry of the matrixwas ever read
Fig. 14 The argument at its strongest, from the hierarchy field: a representation built from a few hundred products with an operator that is never seen.
Error of a difference quotient for J(x)v against ε, on the Bratu problem at n = 64The Jacobian of this problem is a formula, so the error of each quotient is measured against a derivative that is exact rather than against a better quotient. The forward difference falls with a slope of 1.01 — first order — reaches 1.28·10⁻¹⁰ at ε = 10^-6, and rises again with a slope of -1.00 as cancellation takes over. The central difference falls with a slope of 2.00 and bottoms at 1.11·10⁻¹² for two residual evaluations instead of one. Neither gets near the unit roundoff at any ε.10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1εrelative error in J(x)vforwardcentralcancellationtruncationagainst a derivative that is exactforward floor1.3·10⁻¹⁰central floor1.1·10⁻¹²truncation slope, forward1truncation slope, central2no ε reaches the roundoffand the analytic derivative is free of the choice
Fig. 15 And the matrix-free field’s version of the same trade, for scale.

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^{d−1} 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.

One sketch reused across 20 independent matrices, against a fresh sketch for eachThe matrices are drawn from the same construction with different seeds, so none of them can depend on the sketch. This is the case the randomised bounds were written for, and the two rows of points are the answer: mean error 0.36184 with one sketch kept and 0.35789 with 20 fresh ones, a difference of 0.00396 against a standard error of 0.00508. The rule is therefore not that a sketch must be redrawn — it is that the randomness is spent the moment the input starts depending on it.31323334353637383940410123relative approximation error ‖A − QQᵀA‖ ⁄ ‖A‖, per centone sketch, kepta fresh sketch eachthe vertical marks are the two meansreuse, where nothing adaptskept sketch, mean error0.36fresh sketches, mean error0.36difference0.004standard error of either0.0051spread, kept0.019the guarantee is about a drawthe input has not seen
Fig. 16 The last of those, from the essay that measures it: where reusing randomness is safe and where it is spent.
The randomised SVD against the optimum it cannot beatA semi-logarithmic plot of approximation error against target rank. A shaded band shows the spread across seeds, a solid line the optimal error from the exact singular values, and a dashed line the published probabilistic bound well above both.04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσ_{k+1}, optimalhow far apart the three areworst seed spread1.6bound / median at k = 125.9median / optimum at k = 121.960×60, 6 seeds, oversampling p = 5band is best to worst
Fig. 17 And the band with no power iteration, for reading against the version with one.

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.

Where a bound can be proved, against κuEvery combination of 4 working precisions and 6 Hilbert sizes, placed by the product of the condition number and the unit roundoff. Filled marks are the cases where a bound was proved; open ones are the cases the method refused. The two sets separate at κu ≈ 1 — the largest verified is 0.24 and the smallest declined is 0.89 — which is the threshold iterative refinement's convergence sits at.10⁻⁹10⁻⁶10⁻³110³10⁶13212937κ · usignificand bitsκu = 1a bound was provedthe method refusedit never returns a wrong boundlargest κu with a proof0.24smallest κu without one0.89cases refused, of the grid10a refusal is not a wide bound — it is no bound at alland it is the only failure mode here
Fig. 18 The arithmetic field’s version of a method that declines rather than lying, from the essay that measures it.
Two greedy contraction rules against the exhaustive optimum, over 60 random networksEach curve is one rule's excess over the exhaustive answer, sorted, so the horizontal axis is the share of networks at or below that excess. Pairing whichever two operands are cheapest to multiply is optimal on 1.7 per cent of them, has a median excess of 1.446 and a worst case of 25.4. Pairing whichever two leave the smallest result — the rule the libraries ship — is optimal on 50.0 per cent with a median of 1.0026. The upper curve is the spread between each network's own best and worst orders, median 607, which is the size of the thing being searched for.020406080100110¹10²10³10⁴share of networks, per centexcess over the exhaustive orderthe exhaustive orderdashes: each network's own best-to-worst spreadpair by cheapest productpair by smallest resulttwo rules, one line apartby cost, median1.4by cost, worst25by size, median1by size, worst2.8spread, median607both are plausibleand one is thirty times better
Fig. 19 And the cost field’s version of a median against a tail, from the essay on contraction orders.

At other settings

The error of a rank-8 Tucker representation built from a sketch, against the columns of oversamplingThe flat line is the deterministic decomposition — d matrix SVDs — at 4.09·10⁻⁹, and nothing random can go below it, since every curve here is a projection onto a subspace of the same size. The upper two are medians over five seeds: a dense Gaussian sketch, which the randomised field's bounds cover, and a Khatri–Rao sketch, whose columns are outer products of small random vectors and which no bound in that field applies to. With no oversampling the dense sketch is 6.40 times the deterministic answer; at twelve extra columns it is 1.37. The structured one costs 1.9 per cent more at four extra columns and -2.4 per cent at twelve — measured, because there is nothing else to say about it.-113579111310⁻⁸10⁻⁷extra columns in the sketchrelative errora Khatri–Rao sketch: no bound covers ita dense Gaussian sketchthe decomposition, which nothing beatsrank 8, five seedsdeterministic4.1·10⁻⁹dense, p = 02.6·10⁻⁸dense, p = 125.6·10⁻⁹structured, p = 125.5·10⁻⁹structured ⁄ dense0.98a bound and a measurementand only one of them is available
Fig. 20 At rank eight, where the floor is lowest and the sketches need the most oversampling to reach it.
The error of a rank-6 Tucker representation built from a sketch, against the columns of oversamplingThe flat line is the deterministic decomposition — d matrix SVDs — at 7.94·10⁻⁶, and nothing random can go below it, since every curve here is a projection onto a subspace of the same size. The upper two are medians over five seeds: a dense Gaussian sketch, which the randomised field's bounds cover, and a Khatri–Rao sketch, whose columns are outer products of small random vectors and which no bound in that field applies to. With no oversampling the dense sketch is 15.12 times the deterministic answer; at twelve extra columns it is 1.23. The structured one costs 34.8 per cent more at four extra columns and -1.0 per cent at twelve — measured, because there is nothing else to say about it.-113579111310⁻⁵10⁻⁴10⁻³extra columns in the sketchrelative errora Khatri–Rao sketch: no bound covers ita dense Gaussian sketchthe decomposition, which nothing beatsrank 6, five seedsdeterministic7.9·10⁻⁶dense, p = 01.2·10⁻⁴dense, p = 129.8·10⁻⁶structured, p = 129.7·10⁻⁶structured ⁄ dense0.99a bound and a measurementand only one of them is available
Fig. 21 And rank six, between the settings the argument is made at.
Random numbers a sketch needs, against the number of indices, at n = 6A dense Gaussian sketch of a mode-k unfolding multiplies an n × n^{d−1} matrix by a random one with n^{d−1} rows, so the random object is the size of the tensor divided by n — the line that crosses the tensor's own entry count at d = 2 and is 2.02·10⁷ by d = 8. A Khatri–Rao sketch replaces it with d − 1 small Gaussians per column, costing 3,024 numbers at the same point — a factor of 6665 — and is applied as mode products, so nothing the size of the tensor is ever formed. What it is not is Gaussian, which is what the previous figure has to measure rather than bound.12345678910¹10³10⁵10⁷number of indicesrandom numbers drawna dense Gaussian sketchdashes: the tensor's own entriesa Khatri–Rao sketcha random matrix nobody can afforddense at d = 82·10⁷structured3024the tensor's entries1.7·10⁶dense ⁄ structured6665crossing at d2the sketch outgrows its tensorand the structured one does not
Fig. 22 The counting on a grid of six, for reading how the crossing moves.
Random numbers a sketch needs, against the number of indices, at n = 12A dense Gaussian sketch of a mode-k unfolding multiplies an n × n^{d−1} matrix by a random one with n^{d−1} rows, so the random object is the size of the tensor divided by n — the line that crosses the tensor's own entry count at d = 2 and is 2.58·10⁹ by d = 8. A Khatri–Rao sketch replaces it with d − 1 small Gaussians per column, costing 6,048 numbers at the same point — a factor of 4.27·10⁵ — and is applied as mode products, so nothing the size of the tensor is ever formed. What it is not is Gaussian, which is what the previous figure has to measure rather than bound.12345678910¹10³10⁵10⁷10⁹number of indicesrandom numbers drawna dense Gaussian sketchdashes: the tensor's own entriesa Khatri–Rao sketcha random matrix nobody can afforddense at d = 82.6·10⁹structured6048the tensor's entries4.3·10⁸dense ⁄ structured4.3·10⁵crossing at d2the sketch outgrows its tensorand the structured one does not
Fig. 23 And on a grid of twelve, where the dense count passes 10⁸.
The truncation error of a smooth tensor against the rank kept, between the two bounds the theorem givesThe middle curve is the measured error of the projection; the upper dashed one is √(Σ_k tail_k²), which the theorem says it cannot exceed, and the lower one is max_k tail_k, which the best possible error cannot fall below. They are a factor of √3 apart. The measurement is that the projection sits on the upper one, and not between them: the ratio of error to bound runs 0.688, 0.717, 0.879, 0.933 … 0.999982, so by rank 10 the bound is attained to five decimals and the ratio to the lower bound is 1.7320 against √3 = 1.7321. That reads as a bad result and is not one — what it says is that the lower bound is weak, which only a second measurement can establish.024681010⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹rank kept in every moderelative errordashes above: √(Σ tail²), the upper bounddashes below: max tail, a floor under the bestsolid: what the projection returnssmooth: pinned to the upper boundrank 10 error1.1·10⁻¹¹its upper bound1.1·10⁻¹¹the lower bound6.3·10⁻¹²error ⁄ bound1error ⁄ lower1.7inside the boundand sitting on it
Fig. 24 The deterministic answer these sketches are measured against, from the field that owns it.
The share of a HOSVD core's energy on its superdiagonal, by family, at rank 6A matrix SVD hands over orthonormal factors and a diagonal middle at the same time. For three indices they come apart, and this is the half that does not survive. Every core here is all-orthogonal — the largest inner product between two slices perpendicular to a mode, relative to the core's own energy, is 3.5·10⁻¹⁶ — and none of them is diagonal. The bars are the fraction of the squared norm carried by the 6 entries on the superdiagonal: smooth 97.7%, hilbert 94.5%, wave 26.6%, noise 0.4%. Keeping only those entries costs 0.152, 0.235, 0.857, 0.998 in relative error against the full core's 7.94·10⁻⁶, 1.77·10⁻⁶, 1.34·10⁻¹⁵, 0.842.smooth97.7%hilbert94.5%wave26.6%noise0.4%share of the core's energy on its 6 superdiagonal entrieskeeping only them: 0.152 against 7.94·10⁻⁶keeping only them: 0.235 against 1.77·10⁻⁶keeping only them: 0.857 against 1.34·10⁻¹⁵keeping only them: 0.998 against 0.842orthogonal, and not diagonalsmooth on-diagonal0.98hilbert on-diagonal0.94wave on-diagonal0.27noise on-diagonal0.0044worst slice pair3.5·10⁻¹⁶the slices are orthogonalthe core is not diagonal
Fig. 25 And the object being built, whose factors are what the sketch is estimating.
What a rank-10 approximation can achieve, by spectrumA semi-logarithmic plot of singular value against index for three spectra — geometric decay, algebraic decay, and flat — with the rank-ten approximation error marked on each.1112131415110⁻³10⁻²10⁻¹1index jσⱼσ11geometric, 0.85ʲalgebraic, j^−0.50flatmeasured, and equal to σ₁₁rank-10 error, geometric0.2rank-10 error, algebraic0.3rank-10 error, flat160×60, spectrum chosen rather than the entriesthe matrix decides, not the method
Fig. 26 A spectrum with no gap, which is where every randomised method on this site stops working.
What the black-box construction costs: the rank has to be chosen before anything is knownThe 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 has to be drawn before a single entry of the block has been seen. The curve is a straight line at -0.74 decades a column — from 0.0407 at k = 2 to 1.72·10⁻⁹ at k = 12 — so the guess is a guess about a number of digits, and being two columns short costs about a decade and a half. The lower line is the best representation of the same rank, so the vertical gap is what never seeing the matrix costs: 2.9, 4.5, 4.1, 4.4, 6.6, 8.1 times, widening slowly as the rank grows, because a sample of a block whose spectrum has already fallen off a cliff is sampling noise.0246810121410⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1rank asked of every block‖A − A_H‖ ⁄ ‖A‖built from productsthe best of the same rankan accuracy for a rankerror at k = 20.041error at k = 121.7·10⁻⁹decades a column0.74products at the top240excess over the optimum8.1one route asks for digitsand the other asks for columns
Fig. 27 The hierarchy field’s version of having to guess a rank before sketching for it.
The three unfoldings of a 10 × 11 × 12 noise tensor, and the singular values of eachA tensor has one matrix per index — put that index on the rows and every other index down the columns — and each of those matrices has an ordinary rank. Here they are 10, 11, 12 at a relative tolerance of 10⁻⁸, from a tensor of 1320 entries whose modes are of different lengths. Nothing requires the three numbers to agree, and nothing requires any of them to be the tensor's own rank: they are three different matrices built from one array. The leading singular values are 14.2, 13.6, 13.4, each normalised to its own mode below.02468101210⁻¹⁶10⁻¹²10⁻⁸10⁻⁴1index of the singular valueσ ⁄ σ₁the tolerance the ranks are read atmode 1 · rank 10mode 2 · rank 11mode 3 · rank 12noise: three matrices, one arrayentries1320mode-1 rank10mode-2 rank11mode-3 rank12‖T‖36three ranksand none of them is the tensor's
Fig. 28 And the array with nothing to find, seen through the three matrices a sketch would be applied to.
The largest train rank of a 5-index reciprocal tensor against the accuracy asked forEvery point is a decomposition that met its tolerance: the measured errors are 0.0041, 4.2·10⁻⁴, 3.4·10⁻⁵, 3.3·10⁻⁷, 5.7·10⁻⁹, 6.6·10⁻¹², 1.6·10⁻¹³ against tolerances of 10⁻², 10⁻³, 10⁻⁴, 10⁻⁶, 10⁻⁸, 10⁻¹⁰ and 10⁻¹². The rank runs 3, 4, 5, 7, 8, 10, 11 and the storage 264, 448, 680, 1,160, 1,664, 2,208, 2,504, against 32,768 entries. That is 0.80 of rank per decade of accuracy over the whole range — a constant, with no cliff and no regime where a digit costs more than the last one, which is the same shape the hierarchy field measured for a kernel matrix and is not something either field's geometry promises.-13-11-9-7-5-3-1024681012log₁₀ of the accuracy asked forlargest train rank0.80 of rank per decadea cost that is typed inentries3.3·10⁴stored at 10⁻²264stored at 10⁻¹²2504rank per decade0.8worst error ⁄ tolerance0.57the storage is chosena constant of rank a decade
Fig. 29 What the deterministic route costs on a longer chain, for the reader deciding whether the sketch is worth its penalty.

Where this goes next

10²10².³10².⁵⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁶10⁻¹10⁻⁰.⁵1rows in the sketchworst relative distortiondimension 64dimension 2565 seeds per point, band is best to worstthe dimension does not appear The dimension does not appear A random projection preserves the lengths of a set of vectors to within a distortion that depends on how many vectors there are and not on how many coordinates each one has. That is the fact the whole field rests on, and it is genuinely surprising. 024681010⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹rank kept in every moderelative errordashes above: √(Σ tail²), the upper bounddashes below: max tail, a floor under the bestsolid: what the projection returnssmooth: pinned to the upper boundrank 10 error1.1·10⁻¹¹its upper bound1.1·10⁻¹¹the lower bound6.3·10⁻¹²error ⁄ bound1error ⁄ lower1.7inside the boundand sitting on it A decomposition made only of SVDs Everything the definition of tensor rank loses comes back if the SVD's algorithm is carried across instead of its definition — take the leading left singular subspace of every unfolding and project onto all of them. It exists, it costs d matrix decompositions, and its error is within √d of the best there is. 567891010¹10²10³10⁴10⁵10⁶log₂ nnumbers the construction touchedentries, n²products with the operatoran operator, applied a few hundred timesproducts at n = 512256entries at n = 5122.6·10⁵per doubling48‖A − A_H‖ ⁄ ‖A‖4·10⁻⁷excess over the compression7.3no entry of the matrixwas ever read Built from products alone A 512-square hierarchical representation, at a relative error of 4·10⁻⁷, from 256 applications of an operator that is never assembled. The compression route reads 262,144 entries; this one reads none, and pays for it with a factor of seven against the representation the entries would have given.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Higher-order SVDKhatri–Rao productLow-rank approximationMultilinear rankOversamplingRandomised SVDSeeded generatorSketchingTruncated svdTucker decomposition