The rank a certificate charges

Every randomised factorisation measured in these essays so far was handed its rank. A bound that holds with probability swept the rank and drew a band at each value; an answer that changes with the seed tried every rank from 4 to 32 and read the best one off with the exact answer in hand. That essay ended by naming what a real run cannot do: it does not know the answer, it does not know the singular values, and it still has to decide how many columns to keep.

There is a standard way to decide, and it is attractive because it needs nothing the method does not already compute. Grow an orthonormal basis Q one column at a time. Keep ten spare random vectors ω, and after each new column project their images: $y_i = (I - QQ^{\mathsf T})A\omega_i$. When every one of the ten is short — when the largest $\|y_i\|$ falls below ε divided by a constant C — stop. With $C = 10\sqrt{2/\pi}$, about 7.98, a lemma of Halko, Martinsson and Tropp guarantees that the basis’s true spectral error ‖(I − QQᵀ)A‖ is at most ε with probability at least 1 − 10⁻¹⁰.

That guarantee held on every draw measured here. The question this essay asks is what it cost.

Four ranks where one was expected #

Reading the figure from left to right along the tolerance line gives four ranks, and each is a different question.

The optimal rank is eleven. $\sigma_{12}$ = 0.8¹¹ is the first singular value below 0.1, so the truncated singular value decomposition at rank eleven meets the tolerance and nothing of smaller rank can — that is the Eckart–Young floor, and no method crosses it.

The basis rank is fifteen. The adaptive basis is built from random products rather than singular vectors, so at rank eleven it has not yet found the eleven leading directions exactly; its true spectral error there is 2.37 times $\sigma_{12}$, and it takes four more columns before the error itself is below 0.1. That is not a cost of the stopping rule. An oracle that knew the true error of this particular basis would still stop at fifteen.

The probe rank is twenty: the first rank at which the largest of the ten projected probes is itself below ε. The rule cannot see the true error, only the probes, and the probes read high.

The certified rank is thirty on the median of five seeds, and thirty-four on the run drawn above. That is where the probes fall below ε/7.98.

So a user who asked for a tolerance of 0.1 received a rank-30 basis whose true error is about 0.0045 — twenty-two times better than requested — for a problem whose honest answer has rank eleven. The guarantee was kept, and it was kept by nearly tripling the work.

The first price is oversampling under another name #

The four columns between the optimal rank and the basis rank would be paid by any randomised range finder, adaptive or not, and they have a familiar name. A fixed-rank method asked for rank k draws k + p random vectors and keeps the range of all of them, because a basis spanned by exactly k random products captures the k leading directions only approximately: each product is a mixture of every singular direction, weighted by its singular value, and the directions just past the kth leak into the basis in place of part of the directions before it. The standard p is five to ten, and the extra columns are what bring the error down from a multiple of $\sigma_{k+1}$ to close to it.

The adaptive rule pays the same price by a different route. It never decides on a p; it simply keeps adding columns until the basis is good enough, and the columns past the optimal rank are the oversampling. Measured, they are four on the geometric spectrum at ε = 0.1, six at 0.01, and one to seven on the algebraic spectrum — the range a fixed-rank user would have chosen. That is reassuring, because it means the first price is not a defect of the stopping rule: a user who knew the optimal rank in advance and oversampled by the usual amount would have landed at about the same place.

It also means the first price is the only one of the three a better sketch could reduce. A power iteration sharpens the basis so that fewer columns reach the same error; nothing about the sketch changes how much a probe over-reads or what constant the certificate needs.

Why a probe reads more than the error it certifies #

The middle gap is the one worth understanding, because it is not a safety margin anybody chose.

For a Gaussian vector ω and any matrix B, the expected squared length of Bω is the sum of the squares of B’s singular values — the Frobenius norm squared, not the spectral norm squared. So a single probe of the residual (I − QQᵀ)A measures the whole of the residual’s spectrum rather than its largest singular value. On a spectrum falling by 0.8 a step, the tail’s Frobenius norm is $\sqrt{1/(1-0.64)} \approx 1.67$ times its first term, and at the optimal rank the measured ratio of the basis’s Frobenius to spectral error is 1.46. Taking the largest of ten probes adds the rest: an individual probe fluctuates around the Frobenius norm, and the largest of ten sits above it. Together, at rank eleven, the largest probe is 2.68 times the true spectral error.

The rule is therefore certifying a quantity that is already an overestimate before the constant is applied. This is the same fact counting what cannot be looked at uses in the other direction: Hutchinson’s trace estimator works precisely because a random probe’s quadratic form averages the whole spectrum. What is a feature when the trace is the target is a bias when the largest singular value is.

The three prices on five problems #

The same decomposition holds on every row, and the sizes of the three steps change in ways that follow from the spectrum.

On the geometric spectrum at ε = 0.1 the steps are 11 → 15 → 20 → 30: four columns for the random basis, five for the Frobenius reading, ten for the constant. Tightening to 0.01 moves everything right by about ten and leaves the steps at 6, 4 and 10. The constant costs a fixed number of columns because on a geometric spectrum a fixed factor in the error is a fixed number of steps: 7.98 is 0.8 raised to about −9.3.

On the algebraic spectrum $\sigma_j$ = $j^{-2}$, the same constant is not a fixed number of columns. At ε = 0.1 the steps are 3 → 4 → 8 → 24, and the certificate alone takes sixteen of the twenty-one extra columns. At ε = 0.01 the certified rule does not stop at all within sixty columns, while the basis reached the tolerance at sixteen and the probes at face value would have stopped at twenty-seven. On a spectrum falling like a power, dividing the target by eight asks for the rank to grow by a factor of $\sqrt{8}$, and the tail’s Frobenius norm falls more slowly than its first term, so both the second and third prices grow with the rank rather than staying put.

The slowest spectrum, $\sigma_j$ = $j^{-0.8}$, is the case that shows what the rule is for and what it cannot do. The optimal rank is seventeen and the basis reaches the tolerance at forty-nine: random products are poor at separating singular values that are close together, so the first price has become thirty-two columns. And neither the face-value nor the certified rule stops within sixty, although the basis has already been good enough for eleven columns. The probes read the tail’s Frobenius norm, which on this spectrum stays above 0.1 far past the point at which the spectral error falls below it. A rule that reads only probes cannot certify what the probes cannot see.

That is the same shape randomisation does not create structure found in the approximation itself, arriving one level up: a slowly decaying spectrum makes the randomised basis worse, and it also makes the method’s self-assessment worse by more.

Where the constant starts to matter #

The third price is the only one a user controls, so it is worth asking what happens if it is not paid.

At the published 7.98 the median stopping rank is 31 and the true error at that rank is 4.5 per cent of the tolerance. At C = 3 the rank is 26 and the error 13 per cent of the tolerance; at C = 1 — the probes read at face value — it is 20 and 39 per cent. None of those draws missed. Only below face value does the rule start to stop early: at C = 0.5, four of twelve draws come back with a true error above 0.1; at 0.3, nine; at 0.1, all twelve.

So on this matrix the safe region extends a factor of eight below the published constant, and the boundary is not at the constant but at C ≈ 1, where the Frobenius overestimate runs out. Face value is safe here because the probes were already reading high, and every column the constant adds beyond that buys protection against a failure that the draws did not produce.

That is not a recommendation to drop the constant, and the next panel is why.

Here the probes over-read by more — the Frobenius tail of $j^{-2}$ is fatter than that of 0.8ʲ — and the safe region reaches lower: C = 0.5 stops at rank 20 with no misses, while on the geometric spectrum the same constant missed on a third of the draws. The certified rule, meanwhile, never stops in the range at all. How far below the published constant a code could safely go depends on the spectrum, which is exactly the thing the rule was designed not to need to know.

The constant is not badly chosen. It is the constant that is safe for every matrix, including one whose residual has a single dominant singular value — where the probe’s Frobenius reading equals its spectral one and the only margin is the constant itself. The price of a certificate that holds without knowing the spectrum is paid in full on spectra that did not need it.

The same rule, a decade tighter #

On the geometric spectrum the picture translates. Optimal 21, face value 32, certified 41, misses from C = 0.5 downward, and the true error at the certified rank is 5.5 per cent of the tolerance — as it was 4.5 per cent a decade looser. A spectrum that falls by a fixed factor a step turns every multiplicative safety margin into an additive number of columns, and so the certificate costs the same ten columns whatever tolerance is asked for. On a problem where each column is a pass over a large matrix that is a fixed surcharge, which is easy to budget; on the algebraic spectrum it is not.

The trace on a slowly decaying matrix #

Set beside the first figure, the difference is in the slopes. On the geometric matrix every curve falls at the same rate on the logarithmic axis, parallel lines separated by fixed factors, and a fixed factor is a fixed horizontal distance. On the algebraic matrix the curves flatten as the rank grows, and a fixed vertical factor becomes a horizontal distance that grows as the curve flattens. The published estimate crosses the tolerance at a shallow angle, and a shallow crossing is an expensive one.

On this run the basis is within tolerance from rank six and the rule keeps building until 24 — eighteen passes over the matrix to certify what the sixth pass had already achieved. On a problem where A is a 10⁶-row operator that is the whole budget of the method.

What the stopping rule is actually for #

Two uses of an adaptive rank are easily conflated, and the measurements separate them.

Certifying an error. If a downstream computation needs ‖A − QQᵀA‖ ≤ ε with high probability — because the low-rank approximation is standing in for A inside a solver whose own guarantee depends on it — then the constant is not negotiable and the rank it charges is the price of the guarantee. Nothing measured here undermines the lemma; it held on every draw.

Choosing a rank. If the goal is simply a reasonable rank for a given accuracy, the certificate answers a stronger question than was asked. The probes at face value never stopped early in thirty-six draws across the three sweeps, and they stopped ten columns earlier on the geometric matrix and more on the algebraic one. A cheaper route to a trustworthy answer is to stop at face value and then check once: the residual’s spectral norm can be estimated by a few steps of power iteration on (I − QQᵀ)A, which costs a handful of passes rather than ten more columns and each of their re-orthogonalisations. That is a two-stage rule, and like a stopping test that is a race, its value depends on what a wasted pass costs against a wrong stop.

This is also the same distinction a rule that reads only its own probes drew for the trace estimator, where a stopping rule based on the running standard error was calibrated in the median and three times over target in the worst of forty draws. The trace rule was optimistic in its tail; this one is pessimistic everywhere. Both read nothing but their own probes, and both are wrong by an amount set by a property of the matrix they cannot see — the spread of eigenvalues there, the weight of the spectral tail here.

What this rests on #

Eighty-by-eighty matrices built from a random orthogonal pair and a chosen spectrum; ten probes; two re-orthogonalisation passes for every projection; five seeds for the ranks and twelve for the constant sweeps. The true errors are computed from the basis with an exact singular value decomposition at each rank asked about. The matrices are dense and small, so the measurements say nothing about the cost of a pass, only about how many passes each rule asks for; on any matrix large enough to need the method, the rank is the cost.

Five seeds give a median and not a spread, and what a single draw cannot report is the reminder that a randomised quantity should be reported with its spread; the per-seed ranks behind each median differ by up to five columns. Twelve draws do not establish that face value is safe either. They establish that the published constant is not what stands between these matrices and an early stop — that the boundary sat near one on the geometric spectrum and below a half on the algebraic one — and that the boundary moves with the spectrum.

The claims that have to fail #

Two claims are published with this essay because each is a natural reading of the method.

The first is that a certified adaptive rank lands near the optimal one. On the geometric spectrum at ε = 0.1 the optimal rank is eleven and the certified rule stops at thirty; the refusal is fed the claim that it stops within five columns of eleven and fails.

The second is the opposite temptation, having seen how conservative the constant is: that the probes are so pessimistic they can be trusted at more than face value. At C = 0.3 the rule stops at rank 14 and nine of twelve draws leave a basis whose true error exceeds the tolerance; the refusal is fed the claim that none do and fails.

Still open: a rank chosen by a check, and a sketch that is cheaper to draw #

A two-stage rule, measured. The argument above says a face-value stop followed by a short power iteration on the residual should keep the guarantee’s reliability at a fraction of its rank. How many power steps the check needs, how often it sends the rule back for more columns, and whether the total number of passes actually beats the certificate on the algebraic spectrum are all unmeasured.

Block growth. Real implementations add columns in blocks of ten or twenty, not one at a time, because a block is one pass over the data. A block rule overshoots its stopping rank by up to a block, which on the geometric spectrum is comparable to the constant’s ten columns and on the algebraic one is small beside it.

A cheaper sketch. Every probe here is a dense Gaussian vector, and each costs a full matrix–vector product. Sparse and Hadamard-based sketches cost less to apply, and whether they find the same range — on matrices whose important directions are spread out and on matrices whose important directions are particular columns — is measured in a sketch that finds the columns it can see.