An answer that changes with the seed

The randomised field arrived on this site with one sentence attached to it: the guarantee changes kind. Everywhere else a bound either holds or it does not; a randomised low-rank approximation has a bound that holds with a probability, and the seed changes the answer.

That was written as a statement about error bounds, and the essay that made it measured the bound: never violated once in eighty seeds, loose by 5.43× against the median, with the error spanning 1.60× across seeds at a fixed oversampling. All true, and all about a quantity — the bound — that no user of the method ever computes.

This essay measures the thing a user does see. Take the randomised method out of the low-rank field and put it to work as one of the four knobs on an ill-posed problem with an answer that is known, and ask how much the answer moves when nothing about the problem does.

The method, stated as a filter #

A randomised SVD draws a Gaussian matrix Ω with k + p columns, forms AΩ, orthonormalises it to a basis Q, and factorises the small matrix QᵀA. What comes back is a rank-k approximation whose singular vectors are computed inside a random subspace rather than the exact one.

Used as a solver, that is a truncation:

x  =  Σ_{j<k} (uⱼᵀb / σⱼ) vⱼ

with the u, σ, v from the randomised factorisation rather than the exact one. The same filter as the truncation knob — one for the components kept, zero for the rest — applied to a basis that is nearly, and not exactly, the right one. That framing is what makes the comparison in the previous essay fair, and it is what makes the spread below a statement about the basis rather than about the filter.

The oversampling here is p = 5 with no power iterations, which is the standard cheap setting and the one the randomised field’s own figures use.

What it costs to be right on average #

Read the spread column from the top and something inverts. The band is widest at rank 8, where the method returns an answer four times worse than its best; it is essentially closed at rank 16, where the method is nearly at its best; and it has opened slightly again by rank 24, which is the optimum.

That is not what a probabilistic bound suggests. A bound of the form “with probability 1 − δ the error is below E” invites the reading that the risk lives in rare unlucky draws — a small chance of a much worse answer, spread evenly over the operating range. What is measured is a wide band in a regime nobody would operate in and a narrow one in the regime everybody would.

The mechanism is not subtle once the method is read as a basis rather than as a bound. At a rank well below what the problem needs, the random subspace has to catch a few of the important directions and its luck in doing so varies from draw to draw. At a rank where enough directions have been caught, every draw catches them: the subspace is oversampled relative to what is left to find, and the remaining difference between seeds is below the level the noise already imposes.

So the randomness costs most where the method is worst. Which is a comfortable finding and a misleading one to stop at, because the operating point is not chosen with the answer in hand — it is chosen by one of the parameter-choice rules, which are themselves uncertain by more than a rank or two, and a rule that lands at rank 8 rather than 16 is inside the band rather than beside it.

The other three sweeps do not do this #

The comparison is what makes the finding a finding rather than an observation about noise. The truncation sweep and the step-count sweep are run twice in the assertion and required to agree exactly — not to a tolerance, exactly — and they do. The Tikhonov sweep is the same. Three of the four knobs are functions of their input in the ordinary sense: same matrix, same right-hand side, same parameter, same answer.

The fourth is not a function of its input at all. It is a function of its input and a seed, and the seed is not part of the problem.

This is where the assertions-that-reject habit pays. It would be easy to write an assertion that the randomised solve agrees with the deterministic truncation at the same rank, discover that it does to two digits at rank 16, and ship a claim that quietly assumes the method is deterministic. The refusal this essay publishes is exactly that claim, fed two seeds at rank 8, and it fails as it must.

What it buys, since it must buy something #

Nothing above is an argument against the method, and it would be a poor essay that left it there.

The randomised factorisation touches A in one pass: k + p products with A, and then a factorisation of a matrix with k + p columns rather than n. The exact truncation needs the singular value decomposition of A, which is a one-sided Jacobi sweep over n² entries in this site’s implementation and O(n³) in anyone’s. On a 64-point problem that is a difference nobody would notice. On a problem where A is a fast transform and n is a million, it is the difference between a method and no method.

So the honest statement of the trade is: the same floor, one pass over the data, and an answer that moves. The first two are why the method exists and the third is the price, and this site’s job is to put a number on the third rather than to leave it as an adjective.

And the flat spectrum, where none of it helps #

The randomised field has a standing result that belongs here as a boundary rather than as a caveat: on a matrix with no decay in its spectrum, the randomised rank-10 error is 1.0 and so is the optimal one. Neither method achieved anything and the failure belongs to the matrix.

The problem in this essay is the opposite case — a spectrum decaying exponentially with no gap anywhere — and that is what makes a low-rank method appropriate at all. Between the two lies every real problem, and the quantity that decides which case a matrix is in is the decay of its singular values, which is computable and is almost never reported.

A note on what “the same answer” would even mean #

There is a tempting repair to all of this: fix the seed, publish it, and the method becomes deterministic again. Every figure on this site does exactly that — the seeded generator in random.js is there so a figure is byte-identical on every build.

It repairs reproducibility and not the thing measured here. A fixed seed means this run can be repeated; it says nothing about whether the answer it produced was a typical draw or the 0.244 at the bottom of the band. A published seed with no band beside it is a stronger claim than the method supports, and it is the shape of claim the fleet’s acrossSeeds habit exists to prevent: one matrix is an anecdote, and one seed is too.

Which is why the figure at the top of this essay draws bars rather than a line, and why the assertion behind it requires the band to be wide somewhere — an assertion that the spread is always small would be asserting that the randomness does not matter, which is what the method’s own literature already implies and what the measurement denies.

The oversampling, which is the knob behind the knob #

Every run above uses p = 5 extra columns beyond the rank being sought, with no power iterations. That is the standard cheap setting and it is not a neutral choice: the oversampling is what turns a randomised factorisation from likely to be adequate into reliably adequate, and it is the parameter the method’s own theory is stated in.

The randomised field measured what it buys on the error bound — the published bound was not violated once in eighty seeds, forty at p = 5 and forty at p = 20, and it is loose by 5.43× against the median. What the band in this essay adds is the other half of that: at a fixed rank the answer varies by up to 1.84×, and the oversampling is what controls that variation rather than the bound.

So a practitioner has two knobs where the presentation suggests one. The rank decides how much of the problem is kept; the oversampling decides how reliably the subspace finds it. Confusing them produces a familiar failure — raising the rank to compensate for an unlucky draw, which costs a factor in the work and does not address the variance.

What a fixed seed does and does not repair #

There is a tempting repair to all of this: fix the seed, publish it, and the method becomes deterministic again. Every figure on this site does exactly that — the seeded generator in random.js exists so that a figure is byte-identical on every build, and a build whose figures moved would be a build whose assertions were about a different picture.

It repairs reproducibility and not the thing this essay measures. A fixed seed means this run can be repeated; it says nothing about whether the answer it produced was a typical draw or the 0.244 at the bottom of the band. A published number with a seed beside it and no band is a stronger claim than the method supports.

That is the fleet’s acrossSeeds habit, which exists for exactly this reason and is stated as one matrix is an anecdote. One seed is an anecdote too, and the difference between the two situations is that a matrix is part of the problem and a seed is not.

Where the method stops being worth it #

Two boundaries, both measured in this field rather than argued.

A flat spectrum. On a matrix whose singular values do not decay, the randomised rank-10 error is 1.0 and so is the optimal rank-10 error. Neither method achieved anything and the failure belongs to the matrix; no oversampling, no power iteration and no seed changes it. That is the randomised field’s standing refusal — randomisation does not create structure — and it is the first thing to check before any of this applies.

And a problem small enough to factorise. Everything the randomised method buys is measured in passes over the data. At n = 64 the exact SVD is a few milliseconds and the randomised route is a complication with a band attached. The method exists for the case where forming the factorisation is not an option, and the honest way to present the comparison at this size is as a measurement of the randomness, which is what this essay is, rather than as a recommendation.

What a report of this method should contain #

The measurements above suggest a short list, and it is short because most of what a randomised run produces is already reported and one thing is not.

The rank and the oversampling, separately. They are two parameters doing two jobs, and a report that gives only k has left out the one that controls the variation.

A band rather than a number. Three or four seeds at the chosen rank cost three or four times a method whose whole selling point is that it is cheap, which sounds prohibitive and is not: the comparison that matters is against the exact factorisation the method replaces, and four randomised runs are still a small fraction of one dense SVD at any size where the method is being used at all.

And the decay of the spectrum, which decides whether any of it applies. A matrix with no decay has no useful low-rank approximation, randomised or otherwise, and that is a computable property of the matrix rather than a judgement about the method.

None of the three is unusual as advice. What this essay adds is a number to the second: the band is 1.84 wide where the method is bad and 1.02 wide where it is good, so a report from a single seed at a well-chosen rank is nearly reproducible and the same report at a badly chosen one is nearly meaningless — and nothing inside a single run says which case it is in.

What is left #

The power iteration, which is the standard repair for a slowly decaying spectrum: multiply by AᵀA once or twice before orthonormalising, and the subspace sharpens. The randomised field draws it and this essay does not use it, because it changes both the accuracy and the spread and separating the two would need a second sweep over q as well as k.

A sketch with structure. Everything here uses a Gaussian Ω, which costs a dense product with A. The subsampled randomised Hadamard transform and the CountSketch families cost far less and have different — weaker, and differently shaped — guarantees. Whether the band above widens under them is the obvious next measurement and it needs those transforms written out, which is a phase’s work.

And a stopping rule for the rank. Every rank in the sweep above was tried and the best one read off with the exact answer in hand. A real run would have to choose k from the data, and the natural candidates are the same three rules the regularisation field scores — transposed, again, to an integer knob, exactly as the step count required. Nobody here has scored them on a method whose answer moves, and a rule scored against a moving target is a different measurement from the ones this site has made.