Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Uniqueness — the series

2 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

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

    part 2 · tensor

All series