Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Tensor rank — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 110¹10²10³10⁻³10⁻²10⁻¹110¹10²10³n‖Aₙ − A‖ and the largest term's norm‖Aₙ − A‖the larger of its two termsan infimum that is not attainedn1024‖Aₙ − A‖0.0017largest term1024their product1.7√31.7the distance goes to zeroand nothing reaches it

    A nearest point that is not there

    Eckart and Young guarantee that a matrix has a best rank-k approximation and that the truncated SVD is it. For three indices the guarantee is false in the strongest available way — there are tensors whose distance to the rank-two set is zero and which no rank-two tensor equals.

    part 1 · tensor
  2. 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.

    part 2 · tensor
  3. share of rank nn = 2 (π/4 = 0.785)0.79n = 30.5n = 80.004234567891010⁻⁴10⁻³10⁻²10⁻¹1n, the size of each sliceshare with rank n0 of 4000dashed: e to the minus 0.087 n squaredthe lower rank stops being typical in practice

    The rank that stops being typical

    A random 2 × 2 × 2 tensor has rank two with probability π/4 and rank three otherwise, and the sentence has no analogue for matrices. It is the first of a family. An n × n × 2 tensor is a pencil of two slices, and it has rank n exactly when the pencil's eigenvalues are all real, n + 1 otherwise. Over draws, the share of rank n is 0.786 at n = 2, 0.500 at 3, 0.264 at 4, 0.039 at 6, 0.004 at 8 and none of 4,000 at 10 — falling like e^(−0.087n²) — because the mean number of real eigenvalues grows only like the square root of n, to Edelman, Kostlan and Shub's closed form within two per cent. Both ranks stay typical in theory; in practice the lower one disappears.

    part 3 · tensor
  4. fit ÷ distance, less oneleast excess over the distance1.8·10⁻⁴greatest0.01510⁻²10⁻¹110⁻²10⁻¹1distance to the double-eigenvalue surfaceerror the fit settles atdashed: equalitytwo routes to one number

    A fit with no answer to find

    Half of all random 3 × 3 × 2 tensors, and most larger ones, have no rank-three decomposition, because their pencil has a complex pair. A rank-n fit to one of them does not wander and does not stall. Two starts settle at the same error to five digits, and that error is the distance from the tensor to the surface where its pencil has a double eigenvalue — found with no fitting at all, and matched to within one and a half per cent. Meanwhile the fit's terms grow without limit, like the square root of the sweep count, while the fitted pencil's two closest eigenvalues close on each other at exactly the rate the terms grow. The error has an answer; the decomposition does not.

    part 4 · tensor
  5. term size ÷ normτ 0.01, smallest term ratio3.8τ 0.003, smallest term ratio6.9τ 0.001, smallest term ratio1210⁻³10⁻²10⁻¹110¹stop when the error is within τ of the distancelargest term ÷ tensor's normmedianthree times the normgrey: one line per drawone per cent is not early enough

    A stop that knows the distance

    A rank-two fit to a random 2 × 2 × 2 tensor of rank three settles at the tensor's distance to the boundary of the rank-two set while its terms grow without limit, and the distance can be computed without fitting. So a fit can be stopped when its error is within a stated fraction of it, and the prediction was that at one per cent the terms would still be within three times the tensor's norm, because one per cent is reached early. On 23 random tensors the terms at the one-per-cent stop are 3.8 to 12.9 times the norm — none within three — and the reason is the law the earlier essay found: the excess falls as the inverse square of the term size, so the size at the stop is the square root of a constant over τ times the distance, and a tensor close to the boundary pays twice, in larger terms and in sweeps. The two closest tensors never reach one per cent in 20,000 sweeps. The stall test a code would use stops in the same range by accident. And one of the 24 computed distances was wrong, which the fit itself exposed.

    part 5 · tensor

All series