Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

CP decomposition — where it appears

A tensor written as a sum of rank-one terms, each an outer product of one vector per index. It is the model whose factors can be read as components, and the only decomposition here whose best approximation of a given size need not exist.

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

smooth97.7%hilbert94.5%wave26.6%noise0.4%share of the core's energy on its 6 superdiagonal entrieskeeping only them: 0.152 against 7.94·10⁻⁶keeping only them: 0.235 against 1.77·10⁻⁶keeping only them: 0.857 against 1.34·10⁻¹⁵keeping only them: 0.998 against 0.842orthogonal, and not diagonalsmooth on-diagonal0.98hilbert on-diagonal0.94wave on-diagonal0.27noise on-diagonal0.0044worst slice pair3.5·10⁻¹⁶the slices are orthogonalthe core is not diagonal

The orthogonality that cannot be diagonal

A matrix decomposition hands over orthonormal factors and a diagonal middle at once. For three indices the two come apart, and there is no arrangement that has both — so the question stops being which decomposition to use and becomes which of the two properties the computation needs.

tensor · multilinear rank 110¹10²10³10⁴10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹sweeprelative error, and the largest term's sizerising: the swamp's largest rank-one termfalling, slowly: its errorfalling, once: a fit with an answera plateau with a rising floorswamp error0.0014swamp term10term growth2.2benign error9.7·10⁻¹⁵benign term growth1the error alone cannot tellthe size of the terms can

An iteration that walks out of the set

Every sweep of alternating least squares is the exact minimiser of its own subproblem, so the objective can only fall. What it cannot do is converge, when the target's nearest rank-r point is not in the rank-r set — and a plateau at a small residual looks identical to slow convergence unless the size of the terms is plotted beside it.

tensor · alternating least squares 6 × 6 × 6, rank 3 · 9 ≥ 81.00002 × 2 × 2, rank 3 · 6 < 80.02076 × 6 matrix, rank 3 · no condition0.1089worst agreement between two runs about the factors, 0 to 1every run fits to 3·10⁻¹³every run fits to 1.2·10⁻¹¹every run factorises to 2.4·10⁻¹⁵ and none agrees with anotherthe only thing that improvestensor, Kruskal holds1tensor, Kruskal fails0.021matrix0.11worst residual1.2·10⁻¹¹three successful fitsone recoverable answer

A factorisation that is unique for once

A rank-r factorisation of a matrix is never unique — AB is (AM)(M⁻¹B) for any invertible M, so no factor means anything on its own. For three indices a checkable condition on the factors' k-ranks makes the decomposition unique up to permuting and scaling the terms, and it holds generically.

tensor · uniqueness 110¹10²10⁻¹²10⁻⁸10⁻⁴110⁴ncondition number, and residual reachedmarks above: κ of the step · dashes: its closed formmiddle: a fit from a random startbelow: the same fit started at the answera decomposition that is ill-conditionedκ at n = 1283.3·10⁴its closed form3.3·10⁴cosine of the terms1from a random start0.012from the answer1.4·10⁻¹⁰the answer existsand cannot be found

A tensor that cannot be decomposed

Every member of a certain sequence is exactly a sum of two rank-one terms, and both terms are written down in closed form. A three-hundred-sweep fit from a random start does not find them, and gets further away as the sequence goes on — because the decomposition has a condition number of its own, and it is 2n².

error · conditioning

Named alongside it

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

Tensor rankAlternating least squaresLow-rank approximationBorder rankCondition squaringIll posed problemOrthogonalitySwampTruncated svdUnfoldingBackward errorCondition number

All concepts