The randomised SVD against the optimum it cannot beat
At its defaults it draws the randomised svd against the optimum it cannot beat. A 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.
randomised-error is one function in lib/figures/randomised.js —
randomised — a bound that holds with a probability, and the seed that moves. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
A 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.
power: 0
The arguments are the ones A bound that holds with probability passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A 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.
p: 2
The arguments are the ones A bound that holds with probability passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A 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.
p: 8
The arguments are the ones A bound that holds with probability passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A 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.
p: 20
The arguments are the ones A bound that holds with probability passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A 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.
power: 1
The arguments are the ones A bound that holds with probability passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A 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.
What it checked while drawing
Every figure above checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
73 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
no basis beats σₖ₊₁ at rank 0 — checked 41 times
no seed beats σₖ₊₁ at k = 2 — checked 6 times
the band at k = 2 is ordered — checked 6 times
a constant of a tenth misses on nearly every draw
a decay rate the study draws
a decay the dial draws
a probe count and a largest rank inside the matrix
a sketch kind this measurement defines
a sketch no wider than the matrix
a sketch width the sparsity sweep is drawn at
a spectrum and tolerance the sweep is drawn at
a spectrum the trace is drawn for
a spectrum this measurement defines
an oversampling the k + p sketch fits inside the matrix at
and the seed changes the answer
at least one nonzero a row and no more than the sketch is wide
matmul shapes agree
no more reserved buckets than the sketch is wide
on the coherent matrix one nonzero a row is several times worse
power iteration does not make it worse
the four ranks are ordered on the geometric spectrum
the published constant misses on no draw
three nonzeros a row reach the Gaussian median on the coherent matrix
Against the rule
It draws a decomposition and prints its residual. It calls
svd, randomisedSVD,
and every figure above carries the badge — which residualcheck verifies by looking
for it in the emitted SVG rather than by finding the call that builds one. A badge that is
constructed and then left out of the body is the failure that check exists for.
Across the library: the rule bites on 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
A bound that holds with probability
Every other guarantee in this collection is deterministic. The randomised low-rank approximation offers one that holds with a probability, the seed changes the answer, and the honest figure is a band rather than a line.
Randomised, and the guarantee that changes kindA fade made of drops
A one-nonzero sketch's median error fell by about forty per cent for every factor of ten in how far a coherent matrix had been mixed toward an incoherent one, and nothing explained the rate. Followed one draw at a time, no draw fades at that rate. Each holds its coherent error — as large as the singular value of the direction its hash lost — and then drops, within one to three decades of mixing, never faster than one decade of error per decade of mixing. The median's steady slope is where the drops happen to fall. Change the spectrum and they fall elsewhere: at a decay of 0.9 there is no slope, only a cliff.
Randomised, and the guarantee that changes kindA sketch that finds the columns it can see
A sparse sketch with one nonzero in each row is twenty times cheaper to apply than a Gaussian one, and on a matrix whose important directions are spread across its columns it finds the same range: a median error of 0.45 against 0.43. Put the same ten directions into ten particular columns and it is eight times worse — 3.33 against 0.41, with a worst draw of 7.1 — because two important columns hashed to one bucket are one direction. Three nonzeros a row repair it at a sixth of the Gaussian's cost, and a randomised Hadamard transform never had the problem.
Methods that were designed apartAn answer that changes with the seed
A randomised rank-k solve is a truncation computed in a random subspace, and it reaches the same floor as the deterministic ones. What it does not do is return the same answer twice — a factor of 1.84 across four seeds at rank 8, and 1.02 at the rank where the method is best.
Randomised, and the guarantee that changes kindRandomisation does not create structure
On a matrix whose singular values are all equal, a rank-ten randomised approximation has error 1.0 — and so does the optimal deterministic one. Neither achieved anything, and only one of them is usually sold with the implication that it might.
Randomised, and the guarantee that changes kindSketching what is never unfolded
A range finder multiplies its matrix by a few random vectors. For a mode-k unfolding those vectors have nᵈ⁻¹ 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.
Randomised, and the guarantee that changes kindThe 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.
Randomised, and the guarantee that changes kindThe leverage that did not move
A one-nonzero sketch fails on a matrix whose leading directions sit on ten particular columns, and coherence — the largest column leverage — is the statistic that names the failure. Turn the directions away from their columns by a hundredth of a radian and the sketch's median error falls from 3.47 to 1.23 times σ₁₁ while the coherence stays at 6.40 to three figures. Giving the heaviest columns buckets of their own repairs the rest, but only when it reserves more buckets than the rank: ten reserved leave 1.16, sixteen reach 0.36, below the Gaussian's 0.41.
Randomised, and the guarantee that changes kindThe rank a certificate charges
A randomised range finder can choose its own rank: grow the basis a column at a time and stop when ten fresh probes all come back short. With the published safety factor it never stopped early in any draw measured, and on a matrix whose singular values fall by 0.8 a step it stopped at rank 30 for a tolerance the best rank-11 approximation already meets. The nineteen extra columns are three separate prices — four for building the basis from random vectors, five because a probe reads more than the spectral norm, and ten for the constant — and the spectrum decides which of them dominates.