Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Seeded generator — where it appears

A pseudo-random number generator written out in the site's own code and started from a stated seed. It makes every figure that draws a random matrix byte-identical on every build, so a claim about typical behaviour can be re-run rather than believed.

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

10¹10²10³10⁴00.050.10.150.20.250.30.350.40.450.50.550.60.650.70.750.80.850.90.951drawsshare with real rank twoπ/4 = 0.78539815,705 of 19,953 have rank twoa probability with a closed formdraws2·10⁴rank two1.6·10⁴share0.79π/40.79standard errors out0.59two typical ranksand the split is π/4

A rank that is not a property of the tensor

The same eight real numbers have rank three over the reals and rank two over the complexes, and a random 2 × 2 × 2 tensor has rank two with probability exactly π/4. Neither sentence has an analogue for matrices, where the rank is one number and a random matrix has the largest one.

tensor · tensor rank 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^{d−1} 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

Named alongside it

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

Low-rank approximationBorder rankEckart–YoungExact ground truthHigher-order SVDHyperdeterminantKhatri–Rao productMultilinear rankNumerical rankOversamplingRandomised SVDSketching

All concepts