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.

Where the phenomenon is, and where it is not #

The essay is about a spread, and a spread is a property of a problem as much as of a method. Two knobs say which problems have one.

So the noise moves the optimum and the band at the optimum together, in opposite directions: at 0.1%, 1% and 10% noise the best rank is 28, 24 and 12 and the band there is 1.004, 1.022 and 1.095. The worse the data, the earlier the method is best and the less determined its answer is there. A randomised solve of a clean problem returns essentially one answer; a randomised solve of a dirty one returns a ten-per-cent range at the setting it is supposed to be run at.

And the figure refuses to draw the small case, which is the sharpest thing the two knobs say. At n = 32 the widest band anywhere in the range is 1.24, and the generator asserts that the seed changes the answer somewhere — so it throws rather than drawing a figure whose subject is absent. The phenomenon this essay is about needs the problem to be large enough to have one: at thirty-two points a randomised rank-k solve is, to within a quarter, a function of its input.

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.

Four seeds is what the figure can draw, not what the claim needs #

The table above is four draws a rank, and four is what the figure can show without becoming a smear. The essay’s own closing section says one seed is an anecdote; the same argument applies to four, and sharpening the measurement changes the finding rather than confirming it. The same sweep, max/min at each rank:

Every entry rises with the sample. That is not the method changing; it is what a range does. The largest of n draws grows with n and the smallest falls, so max/min is a spread multiplied by how many times anybody looked — and four seeds under-report every band in the figure.

The figure will draw three to eight of them and says the same thing over that range.

At 3, 4, 6 and 8 seeds the widest band reads 1.71, 1.84, 1.93 and 1.93 and the band at the optimum reads 1.007, 1.022, 1.028 and 1.036. The first column saturates by six draws and the second does not — which is the same order-statistic effect twice, and it is larger in relative terms exactly where the band is narrow. A quantity that is 1.007 at three draws and 1.036 at eight is not a small number that has been measured; it is a small number that has not been measured yet.

The consequence is not a constant, it is the shape. At four seeds the band appears to close at rank 12 and stay closed, so the story reads as a descent: the randomness costs most where the method is worst and fades away as the rank rises. At forty seeds the band closes at 16 to 24 and then re-opens, to 1.50 at rank 28 and 1.58 at rank 32 — as wide past the optimum as it was at rank 12 on the way in. The band is a U, and four draws show one arm of it.

A U is the more useful shape and it is the more alarming one, because the right arm is the side a parameter-choice rule errs onto. Rules that pick a rank tend to keep too many components rather than too few — that is what makes semiconvergence a hazard at all — so a rule landing at 28 rather than 24 puts the answer in a band that four seeds reported as 1.074 and is 1.500. The same asymmetry is why a parameter that counts steps treats stopping late as the expensive mistake and stopping early as the cheap one.

The methodological half is worth carrying past this essay. If a spread has to be quoted, quote a percentile ratio rather than a range: p90/p10 at 12, 40 and 80 seeds is 1.076, 1.129 and 1.121 at rank 12, and 1.008, 1.012 and 1.012 at rank 16 — settled to a few per cent while max/min is still climbing. It keeps the U, at 1.749, 1.783, 1.129, 1.012, 1.011, 1.034, 1.085 and 1.279 across the eight ranks, whose excesses over one span a factor of sixty-eight from the middle of the range to its left end. A range is not a spread. It is a spread and a sample size, added together. That is the same discipline one matrix is an anecdote applies to a single test matrix, arriving here about a statistic rather than about a sample.

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 — the floor the best approximation there is proves no method passes. 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.

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 range they find matches a Gaussian’s depends on the matrix as well as the sketch, which a sketch that finds the columns it can see measures; whether the band above widens under them is still unmeasured.

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. The standard rule from the method’s own literature — stop when fresh probes fall below a scaled tolerance — is measured in the rank a certificate charges; the regularisation rules transposed to the rank, scored against a moving target, are not.

An iteration whose answer changes with a scaling #

A randomised method’s answer moves with the seed. A deterministic one can move with something just as arbitrary: the scale its input happened to arrive at, which decides which of three fixed points an inverse-free orthogonalisation reaches.