Probabilistic bounds — where it appears
Named by 13 essays across 4 fields — each of them below, with the objects they name alongside it.
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.
The 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.
An 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.
Counting what cannot be looked at
The trace is n additions and one of the most expensive quantities in the subject to estimate, because the matrices whose trace is wanted are never stored. Hutchinson's estimator is unbiased with one line of algebra — and its variance depends on which random vector is used, by a factor that is a property of the matrix, and on a diagonal matrix one choice is exact from the first probe and the other is not.
A rate that belongs to the matrix
Hutchinson's fitted exponent sits near a half on every spectrum measured. Hutch++'s runs from −7.15 to −0.67 across the same four budgets, decided entirely by how fast the singular values fall — so one of the two methods has a convergence rate and the other has a rate per matrix. The ±1 probe's advantage moves the same way, from 1.56× at n = 10 to 1.09× at n = 120.
What a single draw cannot report
With no oversampling the construction's error is 11.6 to 50 times the best representation of the same rank, and the spread across five seeds runs from 16 to 146 per cent of the mean. Sixteen extra columns bring the excess to between 2.0 and 2.9 at every rank measured and the spread to between 4 and 20 per cent — and the second number is the one a single run cannot report and the one that decides whether the first is a measurement.
The split nobody is in a position to choose
Hutch++ spends two thirds of its budget on a sketch and a third on probes, and the third is published as a constant. Swept across six rates of spectral decay at a fixed budget of 48 products, the best share is 0.45 on the fastest and 0.00 on the slowest — sketch nothing at all — and the published third costs between 1.09 and 4.11 times the best error. The decay that decides it is readable from the sketch's own singular values, for products the estimator was going to spend anyway.
A rule that reads only its own probes
A trace estimator is a mean of independent samples, so its own standard error is estimable from the samples and a stopping rule needs nothing the estimator does not already have. Over forty draws it is calibrated in the middle and not at the edge: at a target relative standard error of 1% the median error reached is 5.3·10⁻³ and the worst of forty is 2.9·10⁻² — three times the target. And the cost of the target is the estimator's own square root: tightening it from 3% to 1% takes the median probe count from 75 to 696.
The 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.
A 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.
The variation that comes with a seed
A randomised low-rank approximation's error moves by 31% between draws and by 10⁻¹⁵ between partitionings of one draw. In the one field on this site whose answer already comes as a band, the machine is inside the width of the line — and it is still there.
The miss a normal table already priced
A trace estimator that stops when its own standard error reaches a target misses the target on about a third of draws, and the essay that measured it read the loose targets as the worst calibrated. Over 400 draws the loose target is the better covered — 76% at 10% against 64% at 3% — because the warm-up stops most of its runs with probes to spare. Where the criterion decides, the misses are a normal distribution's: a margin of c on the standard error buys what a normal table says, 94.8% at 1.96, and costs c² in probes, 3.86 times.
The tail a sample never reaches
Hager's estimator is exactly right on four random matrices in five, and that share is stable — between 80.5 and 87.5 per cent across nine sizes. The worst underestimate is not stable at all: it falls every time more matrices are drawn, from 0.746 at sixty to 0.377 at four hundred, and the matrix built to defeat the estimator sits five times below anything four hundred draws found.
Named alongside it
The objects these essays reach for when they reach for this one.
Spectral decayRandom projectionRandomised SVDHutchinson's estimatorMatrix-freeTrace estimationExact ground truthOversamplingRandom probeSketchingDeflationFlop count