Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Kruskal's condition — where it appears

A sufficient condition for a CP decomposition to be unique up to reordering and rescaling: its three factors' k-ranks sum to at least twice its rank plus two. It answers yes or no, and says nothing about how far the terms move when the tensor does.

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

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 per unit of perturbationtrue move, θ = 10⁻³200ALS off by, θ = 10⁻³200ALS off by, θ = 17.9·10⁻⁴10⁻³10⁻²10⁻¹110¹10²10³angle θ between two columns of the third factorchange ÷ perturbation110⁻¹10⁻²10⁻³true decomposition's moveALS's distance from itKruskal: unique at every θ hereθ closes to the leftunique, and not determined

Unique, and not determined

Kruskal's condition says a CP decomposition is unique, and it says it as a yes or a no. Turn two columns of one factor of a 4 × 4 × 4 rank-three tensor toward each other and the condition keeps saying yes at every angle above zero, by one to spare. What it does not say is how well the unique decomposition is determined. The Jacobian of the map from factors to tensor loses its smallest singular value in proportion to the angle, and the true decomposition of a tensor perturbed by one part in 10⁸ moves by 1.6 parts at θ = 0.1 and by 200 at θ = 10⁻³. Alternating least squares, started at the exact answer, finds the moved decomposition while the angle is large, slows by ten times or more on the way to θ = 0.1, and below θ = 0.03 never arrives: at θ = 10⁻³ its own stopping test fires after 11 to 65 sweeps with its terms 200 to 420 perturbations from the answer and its residual within a per cent of the answer's.

tensor · Uniqueness

Named alongside it

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

Alternating least-squaresCP decompositionSwampUniquenessCondition numberJacobianLow-rank approximationOrthogonalityTensor rankTruncated SVDUnfolding

All concepts