Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Random projection — where it appears

A multiplication by a random matrix that maps vectors into fewer dimensions while distorting their lengths by a bounded amount. The distortion is bounded with a probability that depends on the target dimension and not on how many vectors are being mapped, which is what makes it usable at scale.

Named by 10 essays across 2 fields — each of them below, with the objects they name alongside it.

10²10².³10².⁵⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁶10⁻¹10⁻⁰.⁵1rows in the sketchworst relative distortiondimension 64dimension 2565 seeds per point, band is best to worstthe dimension does not appear

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.

randomised · Sketching 0481216202428321rank keptrelative errormedianthe answer movesspread at rank 81.8spread at rank 241best median error0.14widest where the method is worstand the bound does not say so

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.

combination · Randomised 1112131415193111.365129.731148.096166.461probes takenrunning estimate of the tracenormal±1one probe, no errorthe exact trace99±1 variance, this matrix0±1 variance, rotated57normal variance545the same spectrum in a general basiscosts the ±1 probe its whole advantage

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.

randomised · Trace estimation 567891010¹10²10³10⁴10⁵10⁶log₂ nnumbers the construction touchedentries, n²products with the operatoran operator, applied a few hundred timesproducts at n = 512256entries at n = 5122.6·10⁵per doubling48relative compression error4·10⁻⁷excess over the compression7.3no entry of the matrixwas ever read

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. The compression route reads 262,144 entries; this one reads none, and pays for it with a factor of seven against the representation the entries would have given.

randomised · Sketching 2468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²log₁₀ τ‖Bx − d‖ / ‖d‖sketched with the objectiveweighted, not sketchedkept out of the sketchone power instead of twokept out — feasibility1.7·10⁻¹⁶sketched at τ = 10⁸1.7·10⁻⁸unsketched at τ = 10⁸1.7·10⁻¹⁶objective ÷ optimum1.2a sketch preserves a normand a constraint is not one

The half of a problem a sketch may touch

A sketch guarantees that a norm is preserved to within a factor. An equality constraint is a statement that a quantity is zero, and no multiplicative guarantee says anything about zero. Sketch a constrained problem written as a weighted one and the constraint is not destroyed — it is demoted, from a violation of 1/τ² to one of ε/τ, exactly half the exponent.

randomised · Sketching 10¹10²10⁻⁴10⁻³10⁻²10⁻¹1products with Arelative errorHutchinsonHutch++measured at equal costfitted rate, Hutchinson-0.5fitted rate, Hutch++-1.7error at 96, Hutchinson0.017error at 96, Hutch++0.0022both axes count products with Aso the sketch is paid for in the picture

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.

randomised · Trace estimation 48 products, 24 drawsbest share, decay 0.70.45best share, decay 0.950.2worst cost of a third2.800.10.20.30.410⁻³10⁻²10⁻¹share spent on the sketchmedian relative errorthe published thirddecay 0.7decay 0.85decay 0.95large dots: the best split on each curveand the dashed line is the one a library picks

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.

randomised · Trace estimation 111315171921232510⁻¹110¹sketch width l, for rank 10‖(I − QQᵀ)A‖ ÷ σ₁₁GaussianHadamardone nonzero a rowthree nonzeros a rowcoherent, geometric 0.8, width 20, twenty seedsGaussian: median 0.41, worst0.78Hadamard: median 0.37, worst0.94one nonzero a row: median 3.3, worst7.1three nonzeros a row: median 0.41, worst0.99solid: median · dashed: worst of twentybelow one: better than the best rank-10 error

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.

randomised · Randomised median ratioone nonzero, t = 03.5one nonzero, t = 0.011.210⁻⁴10⁻³10⁻²10⁻¹11mixture t (t = 0 at the left edge)error ÷ σ₁₁one nonzero a rowheavy columns reservedthree nonzeros a rowGaussianthe left edge is exact coherencethe failure fades over four decades of mixing

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. Turn the directions away from their columns by a hundredth of a radian and the sketch's median error falls from 3.47 to 1.23 times σ₁₁ while the coherence stays at 6.40 to three figures. Giving the heaviest columns buckets of their own repairs the rest, but only when it reserves more buckets than the rank: ten reserved leave 1.16, sixteen reach 0.36, below the Gaussian's 0.41.

randomised · Randomised fraction left after a decademedian, t = 10⁻³ → 10⁻²0.57median, t = 10⁻² → 10⁻¹0.6210⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1110¹mixing angle terror ÷ σ₁₁median of 80single drawseach draw drops once, somewherethe median's slope is where they drop

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. Followed one draw at a time, no draw fades at that rate. Each holds its coherent error — as large as the singular value of the direction its hash lost — and then drops, within one to three decades of mixing, never faster than one decade of error per decade of mixing. The median's steady slope is where the drops happen to fall. Change the spectrum and they fall elsewhere: at a decay of 0.9 there is no slope, only a cliff.

randomised · Randomised

Named alongside it

The objects these essays reach for when they reach for this one.

Probabilistic boundsSketchingRandomised SVDSpectral decayMatrix-freeRange finderHutchinson's estimatorLeverageOversamplingSubspace embeddingTrace estimationDeflation

All concepts