Randomisation does not create structure

Randomised numerical linear algebra is presented, more often than not, as a way of getting the same answers for less. The framing is not wrong and it hides the condition it depends on, and the condition is the whole thing.

Take a 60×60 matrix whose singular values are all exactly 1 — a flat spectrum, no decay at all — and ask for the best rank-ten approximation. The randomised method, with oversampling and two power iterations, returns an error of 1.0.

That looks like a damning result until the deterministic answer is computed. The optimal rank-ten approximation, from an exact SVD, has error 1.0 as well.

Neither method achieved anything, and the failure belongs to the matrix. Eckart–Young says the best possible rank-k error is $\sigmaₖ₊₁$, and here every singular value is 1, so the best possible error is the whole of σ₁. There is no low-rank structure to find and no algorithm can find it.

Three spectra and one knob say it in a column of numbers. The figure carries a geometric decay, an algebraic one whose exponent is the slider, and a flat one — and reports the best rank-ten error on each.

Across exponents of 0.25, 0.5, 0.75, 1, 1.25, 1.5, 1.75, 2 and 2.25 the algebraic spectrum’s best rank-ten error reads 0.549, 0.302, 0.166, 0.0909, 0.0499, 0.0274, 0.0151, 0.00826 and 0.00454; the geometric one reads 0.197 at every stop; and the flat one reads 1 at every stop.

One column responds to the knob and two do not, and the one that never responds is the one with no structure in it. A flat spectrum has a best rank-ten error of exactly one: the best ten columns of a matrix whose singular values are all equal capture nothing at all, and no exponent, no sketch and no oversampling changes that. That is this essay’s title as a measurement rather than as an argument.

The moving column is worth one more line, because it is exactly what the theorem says it should be. For σₖ = k^(−a) normalised, Eckart–Young puts the best rank-ten error at σ₁₁ = 11^(−a), and 11^(−0.25), 11^(−1) and 11^(−2) are 0.550, 0.0909 and 0.00826 against a measured 0.549, 0.0909 and 0.00826. The figure is not fitting anything; it is evaluating a formula and drawing what it gets.

What randomisation actually buys #

Stated precisely, because the imprecise version is what causes the trouble.

It buys passes over the data. It does not buy accuracy.

The error of the best rank-k approximation is $\sigmaₖ₊₁$ whatever produces it. A randomised method is therefore never more accurate than the deterministic one — the floor in every figure of this field is the proof, asserted at every seed and every k. What it offers is an approximation of comparable quality after one or two passes over A, where computing a full SVD requires many.

That is a statement about cost, and no statement about cost can rescue a matrix with no structure to find. The two claims get conflated because they are usually true together: the matrices people reach for these methods with do have decaying spectra, so the method is both cheap and effective, and the second gets attributed to the first.

The site’s refusal is exactly this. The claim that a rank-ten sketch approximates a matrix with a flat spectrum is fed the measured error and must throw. It does.

The three spectra #

The library builds matrices by choosing the singular values first, because the spectrum is the only property that matters to any claim in this field. Three shapes cover the range.

Geometric decay, $\sigma_j = 0.85^j$. The case randomisation is good at: the tail falls off fast, a rank-k approximation captures nearly everything, and a sketch with modest oversampling finds it.

Algebraic decay, $\sigma_j = (j+1)^{-p}$. The honest middle. At p = 1 the tail is substantial and the approximation is mediocre — good enough to be useful, poor enough that the choice of k matters. At p = 0.5 it is bad enough that power iteration is required to get anywhere, which is what a bound that holds with probability’s slider measures.

Flat, σⱼ = 1. The case where nothing works, included precisely so that it is shown rather than omitted.

Choosing the spectrum rather than the entries is what makes these comparisons honest. A figure built from a random matrix and then described as showing that a method works has confounded the method with whatever spectrum that random matrix happened to have.

Why a flat spectrum is not an exotic case #

It would be convenient if the flat spectrum were a constructed pathology, and it is not — it is what noise looks like.

A matrix of independent random entries has a spectrum described by the Marchenko–Pastur law, which for a square matrix spreads the singular values over a bounded range with no decay to speak of. So pure noise has an approximately flat spectrum, and any matrix that is mostly noise inherits it.

That is the practical form of the warning. A data matrix with genuine low-rank structure buried under substantial noise has a spectrum consisting of a few large values — the structure — followed by a broad flat shelf, which is the noise. Rank-k approximation with k inside the structure works well. Rank-k approximation with k reaching into the shelf is approximating noise, and every additional direction costs a pass over the data to capture something that means nothing.

Which is exactly rank is a decision’s subject arriving in this field: the cutoff is a judgement about where signal stops, the evidence for it is the gap, and a randomised method asked for a rank past the gap will return one without complaint. It has no way to know it has been asked for noise, and the error it reports will look reasonable — because approximating noise at rank k does have error $\sigmaₖ₊₁$, and $\sigmaₖ₊₁$ on the shelf is not a large number.

Sketch-and-solve, and what it costs #

The other application worth measuring, because it is the one where a number can be attached to “worse but cheaper”.

An overdetermined least-squares problem with 400 rows and 12 columns: sketch the rows down to 60 and solve the small problem instead. The saving is direct — a QR of a 60×12 system rather than a 400×12 one — and the question is what the answer is worth.

Across twenty seeds, the residual of the sketched solution relative to the exact least-squares residual has a median of 1.10 and a worst case of 1.27. And the minimum across all twenty seeds is 1.00: no sketch ever beats the exact solution.

All three numbers are asserted, and the third is the important one. The exact least-squares solution minimises the residual over all x, so nothing can do better — a sketched solve returning a smaller residual would mean the exact solve was not exact, and the assertion would catch it. It is the same floor as Eckart–Young’s, in the least-squares setting.

Ten per cent worse for a seventh of the work, with a tail reaching 27%. Whether that is a good trade is not a numerical question, and the point of measuring it is that the trade can be stated rather than guessed at.

It is also worth noticing which quantity is 10% worse. The residual is 10% larger; the coefficients can be much further off than that, and by a factor governed by the conditioning of the design matrix. A small residual is not a small error is the essay for that gap, and it applies here unchanged — a sketched solve reporting a residual within 10% has said nothing about how close its coefficients are to the ones the full problem would have given.

There is a refinement worth naming: sketch-and-precondition. Use the sketch not to produce the answer but to build a preconditioner for an iterative solve of the full problem — the sketched R factor makes AR⁻¹ well conditioned, and a few iterations then give the exact answer rather than a 10%-worse one. It is the same move changing the condition number on purpose describes, with the preconditioner built by sampling, and it converts a fast approximate method into a fast exact one.

Where the flat spectrum shows up in this site’s own machinery #

The claim that a flat spectrum defeats approximation has a companion elsewhere on the site, and putting them together makes both sharper.

The valley with no bottom measures a fit whose coefficients can move 39% of their own size along one direction before the residual changes in the sixth digit. That is a small singular value: one direction in which the problem determines almost nothing.

A flat spectrum is the opposite extreme — no direction is more determined than any other — and it produces the opposite pathology. There is nothing to discard, so any truncation loses as much as any other, and the matrix cannot be summarised at all.

Between them is where every useful matrix sits, and the quantity that says where is the shape of the spectrum rather than any single number drawn from it. The condition number reports the ratio of the two ends and says nothing about the middle; a matrix with κ = 10⁶ might have one small singular value and a tight cluster, or a smooth decay across six decades, and those are entirely different situations for every method in this field.

That is a limitation of κ worth carrying back to the fields that use it. The rate the condition number predicts finds the conjugate gradient bound loose by an order of magnitude for exactly this reason — κ discards the middle of the spectrum, and the middle is what the method responds to. Here the same discarding makes κ useless as a predictor of approximability: the flat matrix has κ = 1, the best possible value, and is the least approximable matrix in this essay.

The seed spread, which is what a flat spectrum still has #

One observation from the flat-spectrum experiment that is worth keeping, because it is a little counterintuitive.

The method returns error 1.0 on the flat matrix at every seed, so on that matrix it is reproducible in the only sense that matters — uselessly, but consistently. On a matrix with algebraic decay, thirty seeds give rank-k errors spanning a factor of 1.79.

That is where the refusal for this essay lives. The claim that the randomised SVD returns the same error at every seed is fed those thirty values and must throw, and it does.

It was not the first refusal written. The first fed the published bound a small oversampling and expected some seed to exceed it; no seed did, in thirty runs, because the bound is conservative enough that a violation is not something a build can rely on catching. An assertion that depends on observing a rare event is an assertion that will fail on somebody else’s Tuesday, so it was replaced by one that is reliably false — and the replacement happens to state the property that distinguishes this field from every other one on the site.

What is asserted here #

On a flat spectrum the randomised error equals the optimal one, to within 5%, and the optimal one is the whole of σ₁, to 10⁻⁶.

No sketch beats the exact least-squares residual, across twenty seeds.

A sketch of 60 rows from 400 stays within 30% of it, at the median.

And it has a tail, with the worst seed above the median — asserted, because a random method whose worst case equalled its median would not be a random method.

The refusals: the claim that sketching finds structure in a flat spectrum must throw, and so must the claim that a randomised method returns one answer. Both do.

When to reach for it, and when not #

The decision is not subtle once the two claims are kept apart, and it comes down to three questions.

Does the matrix have a decaying spectrum? If not, nothing here helps, and neither does anything else — the answer is that a low-rank approximation is the wrong tool, not that a better algorithm is needed. Rank is a decision is about how to tell, and the answer is the gap in the spectrum, which is a measurement rather than a hope.

Is a pass over the data the expensive thing? These methods pay for themselves when A is too large for memory, distributed across machines, arriving as a stream, or available only as a routine that applies an operator with no entries to factorise. In every one of those the deterministic method is not slower, it is unavailable. When the matrix fits comfortably in memory — which is the situation the technique is most often reached for — an exact SVD is fast, deterministic, and gives a better answer.

Is an approximate answer acceptable? If the result feeds a decision that tolerates a few per cent, yes. If it feeds something where a 27% tail matters, either run it several times and look at the spread, or use sketch-and-precondition and get the exact answer anyway.

The cost model, spelled out once #

The claim “randomisation buys passes over the data” deserves the arithmetic behind it, since the whole argument rests on cost and cost is the thing this essay has so far only asserted.

A full SVD of an m×n matrix costs O(mn²) operations, and — more to the point on a large problem — it requires the matrix to be available for repeated access. A bidiagonalisation touches every entry many times, in an order that is not sequential.

The randomised range finder touches A twice: once for AΩ, once for QᵀA. With q power iterations it is 2q + 2 times. Everything else happens on matrices of width k + p, which is small, and costs O(mk²) rather than O(mn²).

So on a matrix of 10⁶ rows and 10⁴ columns where a rank-50 approximation is wanted, the deterministic route is 10¹⁴ operations against the randomised route’s 10⁹ — and the deterministic route additionally needs the whole matrix resident, which at that size it is not.

That argument has two halves, and only one of them can be checked at a size that fits in a measurement. It is worth doing both, because this essay’s whole method is to interrogate a claim where its domain and its success coincide, and the cost claim is one of those.

The pass count is exact, and independent of n. Wrapping every row of A in a counting proxy and running the range finder at k = 10, p = 5:

Exactly 33.0 at every size — which is 2(k + p) + 3, the two sweeps of the argument, each reading every entry once per column of the sketch, plus three. The constant is set by the rank asked for and by nothing else, so the total work against A is O(mnk) and the fitted exponent in n is 2.00 on this family. The claim holds exactly, and the quantity it holds for is the one the deployment cares about.

The flop advantage is not visible at any size a measurement reaches. Wall clock, same family:

The full decomposition is two and a half to eight times faster across the whole range, and the ratio has stopped moving by n = 200 rather than climbing towards one. The fitted exponents are 3.05 and 3.92, so a crossover exists in principle; it is nowhere near any size this can reach.

None of that contradicts the arithmetic above. The comparison is asymptotic, and the sentence about residency is the one carrying the practical weight. What the measurement adds is that the constant is large enough to invert the ordering over every size a reader could check for themselves — so a flop count is the wrong evidence to offer for the method at this scale, and the pass count is the right one. Which is this essay’s own general form, turned on this essay: a method that is faster only on problems too large to run has not been shown to be faster either.

assertThePassCountHoldsAndTheFlopAdvantageDoesNot measures both tables and requires the per-entry read count to be exactly 2(k + p) + 3 at every size and the full decomposition to win on the clock.

It is also worth noticing that the argument never mentions accuracy at any point. Both routes are approximating the same object with the same Eckart–Young floor. The randomised one gets close to it in two passes; the exact one attains it in many. Whether two passes is the deciding constraint is a property of the deployment rather than of the mathematics, which is why the same method is indispensable in one setting and pointless in another.

That is the same distinction the dimension does not appear draws about the sketch itself: what the lemma guarantees is one thing, and what a computation needs is another.

The general form #

The reframing this essay is for, stated so it survives outside the subject.

A method that is faster on the problems where the answer is easy has not been shown to be faster. Randomised low-rank approximation works on matrices with decaying spectra, and matrices with decaying spectra are the ones where a rank-k approximation is worth computing at all. The technique’s domain and its success are the same set, which makes the success very hard to interrogate from the outside.

The way to interrogate it is the one this essay takes: find the case where the problem has no answer, and check that the method reports that rather than producing one. The flat spectrum is that case. Both methods return 1.0, both are correct to do so, and the only thing separating an honest account of the field from an advertisement is whether that number appears.

One more consequence of that framing, and it is the least comfortable one. Because the technique’s value depends on the deployment rather than on the matrix, the decision cannot be made by looking at the matrix alone — which is where every other decision on this site is made. Whether to pivot, whether to use Householder rather than Gram–Schmidt, whether the normal equations are safe: all of those are settled by properties of A. Whether to sketch is settled by how A is stored, on what hardware, reached how often, and none of that is in the numbers.

The one preconditioner an entryless operator can still have #

A randomised preconditioner is built from products with random vectors, which is precisely the interface a matrix-free operator offers. It is one of the very few general options where every deterministic preconditioner has stopped existing.