Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Randomised SVD — where it appears

A low-rank factorisation computed inside a subspace found by multiplying the matrix by a random one, at the cost of a few passes over it. The subspace is found from a handful of products with a random matrix, so the cost is passes over the data rather than arithmetic, and the guarantee holds with a probability.

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

04812162010⁻¹10⁻⁰.⁵1target rank k‖A − Aₖ‖₂published boundrandomisedσₖ₊₁, optimalhow far apart the three areworst seed spread1.6bound / median at k = 125.9median / optimum at k = 121.960×60, 6 seeds, oversampling p = 5band is best to worst

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.

randomised · Randomised 00.250.50.75110⁻¹110¹10²10³fraction of the method's own rangerelative errorfloor 0.141truncation KTikhonov λCGLS steprandomised rankfour methods, one floortruncation K0.14Tikhonov λ0.14CGLS step0.14randomised rank0.14four knobs from four fieldsand one obstruction underneath them

Four knobs and one floor

A truncation, a Tikhonov parameter, a step count and a randomised rank, on one problem with an answer that is known. Their best errors are 0.1445, 0.1406, 0.1426 and 0.1449 — a spread of 3% across four methods that share no arithmetic.

combination · Parameter choice 04812162010⁻¹10⁻⁰.⁵1target rank k‖A − Aₖ‖₂published boundrandomisedσₖ₊₁, optimalhow far apart the three areworst seed spread1.1bound / median at k = 1211median / optimum at k = 12160×60, 6 seeds, oversampling p = 5band is best to worst

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. Neither achieved anything, and only one of them is usually sold with the implication that it might.

randomised · Randomised 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 012345610⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹round‖AΩ‖ ⁄ ‖A‖ at that roundredrawn each roundhalf redrawnkept: the sketch is now the zero matrixthe randomness is spentkept, round 12.6kept, round 29·10⁻¹⁵redrawn, round 23.1kept, final error0.28redrawn, final error0.11a random matrix used twiceis not random the second time

The sketch that is spent

Every other object a sequence carries has a shelf life. A random sketch has one use. Deflate what its first round found and apply it again, and it returns the zero matrix — 9.0·10⁻¹⁵ where the first round saw 2.62 — because the input has been made orthogonal to the very draw the guarantee is over.

randomised · Sketching 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 12345678910¹10³10⁵10⁷number of indicesrandom numbers drawna dense Gaussian sketchdashes: the tensor's own entriesa Khatri–Rao sketcha random matrix nobody can afforddense at d = 81.5·10⁸structured4032the tensor's entries1.7·10⁷dense ⁄ structured3.7·10⁴crossing at d2the sketch outgrows its tensorand the structured one does not

Sketching what is never unfolded

A range finder multiplies its matrix by a few random vectors. For a mode-k unfolding those vectors have nᵈ⁻¹ entries, so the random object is the size of the tensor divided by n — and by six indices it is larger than the tensor it is sketching.

randomised · Sketching 048121610⁻⁸10⁻⁷10⁻⁶10⁻⁵extra columns in the sample, prelative compression errorthe best rank-8 representationfive draws, mean and rangea band, not a lineexcess at p = 012excess at p = 83spread at p = 00.44spread at p = 80.12the optimum of this rank7.8·10⁻⁸one seed shows the meanand five show the risk

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.

randomised · Sketching 051015202530354010⁻⁴10⁻³10⁻²10⁻¹110¹rank of the basiserror, and what the rule readsprobe × 7.98largest probetrue error, Frobeniustrue error, spectralσₖ₊₁, the floorgeometric 0.8, one run, ten probesoptimal rank for ε = 0.111basis reaches ε at rank15probe below ε at rank20published estimate below ε at rank34ε = 0.1the dotted line across is ε = 0.1each rule stops where its curve crosses it

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.

randomised · Randomised 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 00.10.20.30.40.50.60.70.80.9110⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹decay rate of the spectrumrelative spread of the rank-k errorthe seedthe machinetwo kinds of variationseeds drawn8partitionings7seed spread0.31machine spread9.8·10⁻¹⁶ratio3.1·10¹⁴one of these is recordedand it is the large one

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 whose answer already comes as a band, the machine is inside the width of the line — and it is still there.

machine · Run-to-run variation 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 all Gaussian30incoherentcost 1.0030coherentcost 1.00all sparse30incoherentcost 0.0410812coherentcost 0.08sparse, checked30incoherentcost 0.291218coherentcost 0.33sparse, promoted30incoherentcost 0.2930coherentcost 0.54green: certified, error under ε · red: certified, over · grey: refuseddense probes keep it honest

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. Sparse probes cost a twentieth as much and fail on a matrix whose important directions sit on particular columns. Used for both jobs on such a matrix they certify falsely on eight draws of thirty, with the error ten times the tolerance. Let Gaussian probes do the certifying and the sparse basis is never certified falsely — but on eighteen draws of thirty it is never certified at all. The repair is to let a certifying probe that sees eight times more, per unit of its own length, than the next sparse candidate become the column instead. On the incoherent matrix that never happens and the rule costs 29 per cent of the all-Gaussian one; on the coherent matrix it happens a median ten times — about once for each direction the sparse probes cannot find — and every draw certifies correctly at 54 per cent.

randomised · Randomised 00.10.20.30.40.50.6mixture angle tprobe cost over the all-Gaussian rule's00.050.10.20.30.50.81.2π/2303030313132303030583836333232303031promoteddense certificate, no promotionsparse certificatenumbers: median rank; the unpromoted rule refuses at t = 0promotion buys rank, not safety

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. On matrices mixed between the two, the promotions fade as predicted: ten at the coherent end, nine at a mixture angle of 0.1, none from 0.8. But the danger they guard against does not fade with them. It is gone at an angle of 0.05, where the rule that never promotes already certifies every draw correctly. What promotion buys there is rank — a basis of 30 columns instead of 38 — for four fifths more probe work, and the threshold that decides it is a price, not a safety margin.

randomised · Randomised

Named alongside it

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

SketchingRange finderLow-rank approximationProbabilistic boundsRandom projectionOversamplingLeverageSingular valuesSpectral decaySeeded generatorTruncated SVDBlack box construction

All concepts