Every essay — page 19
Randomised, and the guarantee that changes kind
Every other claim on this site is deterministic: the residual is below a bound or it is not. A randomised low-rank approximation has an error bound that holds with a probability, and the seed changes the answer — so the figures draw a band rather than a line. What sketching buys is the same quality for fewer passes over the data, which is a statement about cost. On a matrix with no structure to find it buys nothing, and neither does anything else.
A bound that holds with probability
Every other guarantee in this collection is deterministic.
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.
Randomisation does not create structure
On a matrix whose singular values are all equal, a rank-ten randomised approximation has error 1.0 — and so does the optimal deterministic one.
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.
The sketch that is not the answer
Sketch-and-solve throws away the original problem and keeps the small one's answer, which is why its answer moves with the seed.
The sketch that is spent
Every other object a sequence carries has a shelf life.
Built from products alone
A 512-square hierarchical representation, at a relative error of 4·10⁻⁷, from 256 applications of an operator that is never assembled.
Sketching what is never unfolded
A range finder multiplies its matrix by a few random vectors.
The half of a problem a sketch may touch
A sketch guarantees that a norm is preserved to within a factor.
Counting what is inside a circle
A trace of a matrix nobody wants to form, integrated around a contour, gives an integer — how many eigenvalues are inside.
A rate that belongs to the matrix
Hutchinson's fitted exponent sits near a half on every spectrum measured.
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.
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.
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.
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.
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.
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.
The leverage that did not move
A one-nonzero sketch fails on a matrix whose leading directions sit on ten particular columns, and coherence — the largest column leverage — is the statistic that names the failure.
A spread measured on probes it does not average
A trace estimator that stops on its own standard error misses its target a few points more often than a normal table says, because the runs that stop earliest are the ones that underestimated their noise.
A fade made of drops
A one-nonzero sketch's median error fell by about forty per cent for every factor of ten in how far a coherent matrix had been mixed toward an incoherent one, and nothing explained the rate.
The probe that refuses becomes the column
An adaptive range finder grows its basis from probes and stops when ten fresh ones come back short.
A spread carried from the trace before
A two-stage trace estimator spends a pilot of probes learning its spread, and a computation that needs many traces of a slowly changing operator would rather pay for that once.
A drift put back at the table's price
A trace estimator that carries its spread from the trace before loses one step of drift, and the drift is visible in the spreads themselves, so the repair proposed was to multiply the carried spread by the ratio of the last two.
Promotion buys rank, not safety
A range finder that grows its basis from cheap sparse probes and certifies it with dense ones was made safe on a coherent matrix by promoting a refusing dense probe into the basis — ten promotions for ten coherent directions, none for none.