Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Separability — where it appears

The property of a function or operator of several variables that it is a sum of a few products of one-variable pieces. It is what makes a Kronecker representation exact and a tensor format cheap, and it is a property of how a problem was posed rather than of its entries.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

03672108144180216024681012eigenvalues in orderλthe closed formmarks: the assembled matrix, decomposeda spectrum nobody computedrows of the matrix216numbers that describe it108λ smallest0.59λ largest11worst |computed − exact|7.1·10⁻¹³the matrix is never neededand neither is its decomposition

An index that is a pair

A discretisation on a two-dimensional grid of n points a side has n² unknowns and a matrix with n⁴ entries — 10⁸ at n = 100. What that matrix is instead is two Kronecker products of an n × n matrix, which is 2n² numbers, and nothing has been approximated: assembling it was the mistake.

tensor · kronecker 024681012141610⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹index of the singular value at the cutσ ⁄ σ₁eight digits10^-4: 5 Kronecker terms10^-8: 7 Kronecker terms10^-12: 8 Kronecker termsnot closed, and nearly closedrank at the cut8a Kronecker product's1terms at 10⁻⁴5terms at 10⁻⁸7terms a decade0.5the inverse leaves the formatby half a term a decade

A solve that is d decompositions

A Kronecker sum is closed under nothing useful — its inverse is not a Kronecker sum and no factorisation of it is one. What it has instead is eigenvectors that are Kronecker products, so a solve with 1,728 unknowns takes one decomposition of a 12 × 12 matrix and nothing else.

tensor · kronecker 110¹10²10³10⁻³10⁻²10⁻¹110¹10²10³n‖A_n − A‖ and the largest term's norm‖A_n − A‖the larger of its two termsan infimum that is not attainedn1024‖A_n − 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.

tensor · tensor rank 123456710¹10²10³10⁴10⁵number of indicesnumbersentries: 6^dstored: 4n(d − 1)exponential against linearentries at d = 64.7·10⁴numbers stored120ratio389slope against d24‖T − T_tt‖ ⁄ ‖T‖1.4·10⁻¹⁵one line is n^dthe other is a constant per index

The format that does not notice the dimension

A Tucker core is r^d numbers, so the format that repaired the definition still cannot go past five indices. Cutting between the indices rather than across them gives d − 1 ranks instead of d, storage linear in the number of indices, and a family whose ranks are two everywhere by an addition formula.

tensor · tensor train

Named alongside it

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

Exact ground truthUnfoldingCondition numberCurse of dimensionalityDiscrete laplacianKronecker productKronecker sumLow-rank approximationModel problemTruncated svdBorder rankEckart–Young

All concepts