Numerical Linear Algebra
where the algebra stops being the arithmetic
When the index is a tuple

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.
37 min read 28 figures Where the algebra stops being the arithmeticMeasured, not assertedTwo routes to a number

Worth reading first: An iteration that walks out of the set · A nearest point that is not there · A bound that holds with probability.

Every essay in this field so far has been about something a tensor does worse than a matrix. The best approximation need not exist; the rank depends on the field; two typical ranks occur where a matrix has one; there is no decomposition that is orthogonal and diagonal at once; and an iteration over the natural model can walk out of the set it is searching.

This one is about the exception, and it is the reason the model is used at all.

How much two runs of the same fit agree about the factors, from 6 starting points eachEvery run here reaches its target to the rounding level — 3·10⁻¹³, 1.16·10⁻¹¹ and 2.39·10⁻¹⁵ at worst — so all three are successful factorisations. The bar is the worst agreement between any two of them about the *factors*, matched over permutations and scalings, which is exactly the freedom the uniqueness theorem allows. Kruskal's condition k_A + k_B + k_C ≥ 2r + 2 holds for the first (9 ≥ 8) and fails for the second (6 < 8), and the bars are 1.0000 and 0.0207. The matrix is the comparison the whole thing rests on: AB = (AM)(M⁻¹B) for every invertible M, so its runs agree to 0.1089 and its factors mean nothing on their own.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
Fig. 1 Three successful factorisations, from six starting points each. Only one of them is the same factorisation every time.

What a matrix does not have

A rank-r factorisation of a matrix is M = XYᵀ with X and Y having r columns. For any invertible r × r matrix P,

XYᵀ = (XP)(YP⁻ᵀ)ᵀ

which is another rank-r factorisation of the same matrix. So the factorisations form an r²-dimensional family, and no column of X means anything on its own: it can be replaced by any vector in the column space of X by a suitable choice of P.

This is not a defect and it is not usually noticed, because the decompositions anyone actually uses pin down the freedom with an extra requirement. The SVD asks for orthonormal columns and a decreasing diagonal, which leaves only sign flips and rotations within equal singular values. A QR asks for triangularity. A Cholesky asks for positive diagonal entries. In each case the decomposition is unique because a constraint was added; the factorisation was never unique.

The consequence is the one this collection’s spectra field states: the columns of a truncated SVD are a basis for a subspace, and reading them as components is reading a choice of basis as a fact about the data.

Error of the best rank-k approximation to a 12×12 matrixApproximation error against k on a logarithmic axis, with the measured error and the next singular value drawn as separate curves lying exactly on top of one another.123456789101110⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1rank k of the approximation‖A − Aₖ‖measured, 2-normσₖ₊₁, from theorymeasured, Frobeniusthe first two agreeto 2·10⁻⁸worst |‖A−Aₖ‖₂ − σₖ₊₁| / σₖ₊₁2·10⁻⁸worst Frobenius discrepancy2·10⁻⁸κ = 10⁹; 30 random rank-3 matrices, none closerthe error is σₖ₊₁
Fig. 2 The matrix decomposition that is unique, from the spectra field — and unique because two constraints were imposed rather than because a factorisation was.

What a tensor has

For three indices the situation reverses, and the reason is a counting argument that fails for matrices.

A rank-r CP model is Σ_j λ_j a_j ⊗ b_j ⊗ c_j. The obvious freedoms are permuting the r terms and rescaling the three vectors of a term so their product is unchanged — and those are unavoidable, because they do not change the tensor. Kruskal’s theorem says that under a condition on the factors, they are the only freedoms.

The condition is stated in terms of the k-rank of each factor matrix: the largest k such that every k of its columns are linearly independent. Writing k_A, k_B, k_C for the three,

k_A + k_B + k_C ≥ 2r + 2

is sufficient for uniqueness up to permutation and scaling.

Why the analogue fails for matrices is worth one line. Two factors give k_A + k_B ≥ 2r + 2, and a k-rank is at most r, so the left side is at most 2r. The condition cannot be met with two factors, ever. It becomes satisfiable at three, which is exactly where the extra index buys something.

Measuring it

A theorem about uniqueness is a statement about a set of solutions, and the way to measure it is to find several of them and ask how much they agree.

Six fits, from six random starting points, on each of three targets. Every run is checked to have reached its target — the worst residual across all of them is at the rounding level — so all of them are successful factorisations and the question is only whether they are the same one.

Agreement is scored by a congruence: match the terms of one factorisation to the terms of the other over all permutations, take the product of the cosines between corresponding columns in each mode, and report the worst term under the best permutation. It is 1 when the two differ only by permuting and scaling, and near 0 when they are different factorisations of the same object.

target k-ranks condition worst agreement
6 × 6 × 6, rank 3 3 + 3 + 3 = 9 ≥ 8, holds 1.0000
2 × 2 × 2, rank 3 2 + 2 + 2 = 6 ≥ 8, fails 0.0207
6 × 6 matrix, rank 3 — no condition exists 0.1089

The first row is the whole point: six independent fits, six independent starting points, and one answer. The second is the boundary — the same rank, the same code, and no agreement about anything. The third is the comparison, and it is the row that says the first is remarkable.

How much two runs of the same fit agree about the factors, from 10 starting points eachEvery run here reaches its target to the rounding level — 3·10⁻¹³, 1.16·10⁻¹¹ and 2.39·10⁻¹⁵ at worst — so all three are successful factorisations. The bar is the worst agreement between any two of them about the *factors*, matched over permutations and scalings, which is exactly the freedom the uniqueness theorem allows. Kruskal's condition k_A + k_B + k_C ≥ 2r + 2 holds for the first (9 ≥ 8) and fails for the second (6 < 8), and the bars are 1.0000 and 0.0207. The matrix is the comparison the whole thing rests on: AB = (AM)(M⁻¹B) for every invertible M, so its runs agree to 0.0432 and its factors mean nothing on their own.6 × 6 × 6, rank 3 · 9 ≥ 81.00002 × 2 × 2, rank 3 · 6 < 80.02076 × 6 matrix, rank 3 · no condition0.0432worst 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.043worst residual1.2·10⁻¹¹three successful fitsone recoverable answer
Fig. 3 Ten starting points instead of six. The top bar does not move, because there is one answer to find; the other two fall, because each new start is another chance to land somewhere else.
How much two runs of the same fit agree about the factors, from 3 starting points eachEvery run here reaches its target to the rounding level — 1.55·10⁻¹³, 3.59·10⁻¹² and 2.39·10⁻¹⁵ at worst — so all three are successful factorisations. The bar is the worst agreement between any two of them about the *factors*, matched over permutations and scalings, which is exactly the freedom the uniqueness theorem allows. Kruskal's condition k_A + k_B + k_C ≥ 2r + 2 holds for the first (9 ≥ 8) and fails for the second (6 < 8), and the bars are 1.0000 and 0.1450. The matrix is the comparison the whole thing rests on: AB = (AM)(M⁻¹B) for every invertible M, so its runs agree to 0.1089 and its factors mean nothing on their own.6 × 6 × 6, rank 3 · 9 ≥ 81.00002 × 2 × 2, rank 3 · 6 < 80.14506 × 6 matrix, rank 3 · no condition0.1089worst agreement between two runs about the factors, 0 to 1every run fits to 1.6·10⁻¹³every run fits to 3.6·10⁻¹²every run factorises to 2.4·10⁻¹⁵ and none agrees with anotherthe only thing that improvestensor, Kruskal holds1tensor, Kruskal fails0.15matrix0.11worst residual3.6·10⁻¹²three successful fitsone recoverable answer
Fig. 4 And three, where the two lower bars are highest — a continuum sampled three times looks more consistent than a continuum sampled ten times, which is what makes the count part of the claim.

What the score is, in detail

The congruence deserves a paragraph of its own, because a badly built agreement score would make this page say whatever it was asked to.

Three things have to be quotiented out and no more. Permutation of the terms: two factorisations that list the same terms in a different order are the same factorisation, so the score maximises over all r! orderings. Scaling within a term: the three vectors of a rank-one term can be rescaled so their product is unchanged, so every column is normalised before comparison. Sign: a cosine is taken in absolute value, because flipping two of a term’s three vectors leaves the term alone.

What is not quotiented out is any mixing between terms. A factorisation whose first term is a combination of another’s first two would score low, and should: that is exactly the freedom a matrix factorisation has and this one is claimed not to.

The score reported is the worst term under the best permutation, not the average. An average would hide the case where three of four terms match and one does not, which is the interesting failure — a fit that recovered most of the structure and invented one component.

How much two runs of the same fit agree about the factors, from 6 starting points eachEvery run here reaches its target to the rounding level — 3·10⁻¹³, 1.16·10⁻¹¹ and 2.39·10⁻¹⁵ at worst — so all three are successful factorisations. The bar is the worst agreement between any two of them about the *factors*, matched over permutations and scalings, which is exactly the freedom the uniqueness theorem allows. Kruskal's condition k_A + k_B + k_C ≥ 2r + 2 holds for the first (9 ≥ 8) and fails for the second (6 < 8), and the bars are 1.0000 and 0.0207. The matrix is the comparison the whole thing rests on: AB = (AM)(M⁻¹B) for every invertible M, so its runs agree to 0.1089 and its factors mean nothing on their own.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
Fig. 5 The same three bars, for reading against the description above: a worst-term score, matched over permutations, with scalings and signs removed.

Why the narrow case fails

The 2 × 2 × 2 rank-three case is not a pathology chosen to break the theorem. It is the smallest case in which the condition cannot hold, and it fails for a reason worth stating.

A k-rank is at most the number of columns and at most the number of rows. Here the factor matrices are 2 × 3, so every k-rank is at most 2 and the sum is at most 6, against a required 2·3 + 2 = 8. The condition fails by two, and it fails for every 2 × 2 × 2 tensor at rank three.

What that means concretely is that the rank-three decompositions of such a tensor form a continuum. Any one of them is as good as any other, the fits find different members of it depending on where they started, and the congruence between two of them is whatever the geometry happens to give.

So unique is not a property of the model. It is a property of the model together with the shape and the rank, and the condition is checkable before any fitting is done.

A plane of 2 × 2 × 2 tensors, coloured by the sign of the hyperdeterminant that decides their rankTwo of the eight entries are varied over ±2 and the other six are held at the values that make the centre of the picture the rank-three tensor A = e₁⊗e₁⊗e₂ + e₁⊗e₂⊗e₁ + e₂⊗e₁⊗e₁. The light region is Δ > 0, where the tensor has real rank two and two real rank-one terms exist; the dark region is Δ < 0, where the real rank is three and the complex rank is two. 54.2 per cent of this window is rank two. The boundary between them is the curve Δ = 0, on which the rank is three and the distance to the rank-two set is zero — every point of it is a tensor with no nearest rank-two approximation.rank three, Δ = 0a₁₁₁ across, a₀₀₀ up, both over ±2light: two real roots, rank two · dark: a conjugate pair, rank threeone sign, two rankscells sampled4096rank two2222rank three1874Δ at the centre0rank at the centre3the rank is a signcomputed from eight numbers
Fig. 6 The shape where it fails, from earlier in this field, with the two rank regions and the boundary between them.
The three unfoldings of a 10 × 11 × 12 smooth tensor, and the singular values of eachA tensor has one matrix per index — put that index on the rows and every other index down the columns — and each of those matrices has an ordinary rank. Here they are 8, 8, 8 at a relative tolerance of 10⁻⁸, from a tensor of 1320 entries whose modes are of different lengths. Nothing requires the three numbers to agree, and nothing requires any of them to be the tensor's own rank: they are three different matrices built from one array. The leading singular values are 2.37, 2.37, 2.37, each normalised to its own mode below.02468101210⁻¹⁶10⁻¹²10⁻⁸10⁻⁴1index of the singular valueσ ⁄ σ₁the tolerance the ranks are read atmode 1 · rank 8mode 2 · rank 8mode 3 · rank 8smooth: three matrices, one arrayentries1320mode-1 rank8mode-2 rank8mode-3 rank8‖T‖2.4three ranksand none of them is the tensor's
Fig. 7 And what the k-ranks are read from: ordinary matrices, whose column independence is an ordinary question.

What generic means here

The condition holds generically, and that word is doing enough work to be worth unpacking.

For random factor matrices of size n × r with r ≤ n, every k-rank is r with probability one — any r columns of a random n × r matrix are independent. So the condition becomes 3r ≥ 2r + 2, that is r ≥ 2, which holds for every rank above one.

So for a target built from generic factors of a shape wide enough to hold them, uniqueness is the rule rather than the exception, and the cases where it fails are the ones where a mode is too narrow — as in the 2 × 2 × 2 case — or where the factors themselves are degenerate.

That last is not a corner. Two nearly collinear columns in a factor make the k-rank formally r and numerically less, and the numerical version of the theorem degrades with the collinearity. The error field’s essay on the conditioning of a decomposition measures exactly that quantity: the condition number of the step alternating least squares takes is the condition number of the entrywise product of the factors’ Gram matrices, and it diverges as two terms line up.

Along a sequence of exactly rank-two tensors: the step's condition number, and what a fit from a random start achievesEvery A_n on this sequence *is* a rank-two tensor and its two rank-one terms are written down, so nothing here is about existence. The rising curve is the condition number of the r × r system each alternating sweep solves, which on this sequence has a closed form in n whose asymptote is 2n² — the marks are measured and the dashed line is that closed form, agreeing to 4.5·10⁻¹³. The lower marks are what a three-hundred-sweep fit from a random start returns: 2.1·10⁻⁴ at n = 2 rising to 0.0118 at n = 128. Started at the answer instead, the same code stays within 1.4·10⁻¹⁰ of it at every n — not the rounding level, because the drift from an exact start is itself about κ times the unit roundoff, but nine orders below what a random start reaches. That is the control that says the failure is the conditioning and not the implementation. A tensor away from the boundary conditions its step at 6.03.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
Fig. 8 The numerical version, from the error field: a condition number that is a square in the distance to the degenerate case.
Alternating least squares on a tensor with a rank-two answer and on one without, over 20,000 sweepsThe steeply falling curve is a rank-three fit to a tensor built from rank-three factors: it reaches 9.74·10⁻¹⁵ in 58 sweeps and its largest term does not move — 12.202 at sweep twenty and 12.202 at the end. The other is a rank-two fit to the border-rank tensor, whose error goes from 0.00677 to 0.00141 and has not finished, while the rising curve is its largest term: 4.698 to 10.15, a factor of 2.16. Fitted over 199 points, the error falls as the 2.03 power of the term size — a better path than the explicit sequence's 1/n, and still one that leaves the set rather than converging inside it.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
Fig. 9 And what happens at the degenerate case itself, from the previous essay.

Why the congruence and not the residual

One methodological point, because it is the reason this page has a measurement at all.

Every one of the eighteen runs above reaches its target to the rounding level, so a residual comparison separates none of them. The residual measures whether the model reproduces the data, and every fit does. What is in question is a different property — whether two fits returned the same parameters — and no function of the residual can see it.

That is the same distinction as the orthogonality field’s. Two Gram–Schmidts reconstruct their matrix equally well and differ in ‖QᵀQ − I‖ by fifteen orders of magnitude, and the reconstruction error sees nothing. Here the quantity that has to be reported is a comparison between two runs rather than between a run and its input, which is not a form of measurement this collection has needed before.

Loss of orthogonality against condition number, in binary64A log–log plot of the norm of Q-transpose-Q minus the identity against condition number. Classical Gram–Schmidt rises steeply, modified Gram–Schmidt rises gently, and Householder is flat.110²10⁴10⁶10⁸10¹⁰10¹²10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)‖QᵀQ − I‖classicalmodifiedHouseholderκ²uκu8×8, eight seeds per κ, binary64all three reconstruct A
Fig. 10 The orthogonality field’s version: two algorithms with identical residuals and a measurement that separates them anyway.
What each round of sketch-and-deflate actually sees, for a sketch kept, half redrawn, and redrawnA randomised range finder forms Y = AΩ, takes Q spanning it, and deflates: A ← A − QQᵀA. With the same Ω the next sketch is A₂Ω = AΩ − QQᵀ(AΩ) = Y − QQᵀY, which is zero exactly, because Q spans Y. Measured, the kept sketch sees 2.62 at the first round and 9.03·10⁻¹⁵ at the second — the unit roundoff, which is to say nothing at all, and the subspace it produces after that is whatever the rounding error happened to point at. A fresh sketch stays at about 3.3, and redrawing half the columns sees about half as much. After 5 rounds of identical arithmetic the kept run is at 0.2845 and the redrawn one at 0.1126.012345610⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹round‖AΩ‖ ⁄ ‖A‖ at that roundredrawn each roundhalf redrawnkept: the sketch is now the zero matrixthe randomness is spentkept, round 12.6kept, round 29·10⁻¹⁵redrawn, round 23.1kept, final error0.28redrawn, final error0.11a random matrix used twiceis not random the second time
Fig. 11 And the randomised field’s version of a run-to-run comparison, from the essay that measures what a seed decides.

The two routes to the same verdict

The uniqueness claim can be checked two ways and this page uses both, which is the collection’s habit rather than belt and braces.

The condition is arithmetic on the factors: compute each factor matrix’s k-rank, add them, compare against 2r + 2. It costs three small rank computations and it is a prediction — it says what will happen before any fitting is done.

The experiment is six fits from six starting points and a congruence between every pair. It costs eighteen runs and it is a measurement — it says what did happen, without reference to any theorem.

They agree on both targets: the condition holds and the congruence is 1.0000; the condition fails and the congruence is 0.0207. A disagreement in either direction would be informative — a target satisfying the condition whose fits disagreed would mean a bug in the fitting, and a target failing it whose fits agreed would mean the condition is sufficient rather than necessary, which it is.

That last is worth being careful about. Kruskal’s condition is sufficient and not necessary: there are tensors that violate it and whose decomposition is unique anyway. So a failure of the condition predicts nothing on its own, and the reason the narrow case here does have a continuum of factorisations is measured rather than inferred.

Three routes to the error of a rank-k approximation of one block, at q = 0.5The upper line is q^(p+1)/(1 − q), which used four numbers about two intervals and no entry of the matrix. The middle line is the truncated expansion actually evaluated — a rank p + 1 matrix written down as a table of powers, with no decomposition anywhere in it — and it falls at -0.36 decades a column, close to the log₁₀ q = -0.30 the bound predicts. The lower line is the decomposition, which is optimal by construction, and it falls at -1.74 — 4.8 times as fast. Two of these curves share no arithmetic. What they agree on is that the error is geometric in the rank; what they disagree on is the base, by a factor in the exponent rather than a constant, and the disagreement is why a partition allocated from the bound is safe and wasteful at the same time.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹rank of the approximationrelative errorthe boundthe expansion, evaluatedthe decompositiontwo routes, one shapebound at rank 50.063expansion at rank 50.0048decomposition at rank 52.8·10⁻⁹written, decades a column0.36best, decades a column1.7one route used the matrixand the other used four numbers
Fig. 12 The hierarchy field’s version of the same discipline, from the essay that introduced it: a rank obtained by a decomposition and by arithmetic, made to agree.

What uniqueness is worth

The practical value is the whole reason the model survives its other problems.

A subspace format — the Tucker core, the train — returns a basis for a space. Two runs of it would return two bases for the same space, and asking which basis vector is which component is a question with no answer. Every essay in this field about those formats has been careful to call them projections rather than decompositions for that reason.

A CP model returns terms, and under Kruskal’s condition the terms are the same terms whoever fits them. That is what allows the columns to be read as chemical species, or as sources in a mixture, or as factors in an experimental design — and it is a property no matrix factorisation has.

The whole of this field is therefore a trade with two sides. The subspace formats have existence, computability and quasi-optimality and return objects that mean nothing individually. The component model has none of the three and returns objects that mean something, when a checkable condition holds. Neither is the better format; they answer different questions.

The truncation error of a smooth tensor against the rank kept, between the two bounds the theorem givesThe middle curve is the measured error of the projection; the upper dashed one is √(Σ_k tail_k²), which the theorem says it cannot exceed, and the lower one is max_k tail_k, which the best possible error cannot fall below. They are a factor of √3 apart. The measurement is that the projection sits on the upper one, and not between them: the ratio of error to bound runs 0.688, 0.717, 0.879, 0.933 … 0.999982, so by rank 10 the bound is attained to five decimals and the ratio to the lower bound is 1.7320 against √3 = 1.7321. That reads as a bad result and is not one — what it says is that the lower bound is weak, which only a second measurement can establish.024681010⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹rank kept in every moderelative errordashes above: √(Σ tail²), the upper bounddashes below: max tail, a floor under the bestsolid: what the projection returnssmooth: pinned to the upper boundrank 10 error1.1·10⁻¹¹its upper bound1.1·10⁻¹¹the lower bound6.3·10⁻¹²error ⁄ bound1error ⁄ lower1.7inside the boundand sitting on it
Fig. 13 The other side of the trade: a projection with a bound either side of it, whose factors are a basis.
Train ranks at each of the 4 cuts of a 5-index tensor on 6 points a side, four familiesCut the index list after position k, put the first k indices on the rows and the rest on the columns, and take the rank of the matrix that results. There are 4 such cuts and each rank is an ordinary matrix rank. sin(x₁ + … + x_d) has rank exactly two at every one of them, for every d, because the addition formula separates it into two terms at every cut — a rank written down rather than measured, and the computed values are 2, 2, 2, 2. The reciprocal family climbs to 9, the product family is one everywhere, and independent normal entries reach 36, which is the largest rank the cut allows. Storage runs sinsum 96, reciprocal 1,206, product 30, noise 10,440 against 7,776 entries.012345061218243036cut after index krank of the reshapesinsum · 2 2 2 2reciprocal · 6 9 9 6product · 1 1 1 1noise · 6 36 36 64 cuts, 4 rankssinsum stored96reciprocal stored1206product stored30noise stored10⁴entries7776one rank per cutand one of them is a theorem
Fig. 14 And its long-chain version, whose cores are a bookkeeping device rather than a set of components.

Where the same question sits elsewhere on this site

Two other fields ask a version of it and neither gets an answer this clean.

The regularisation field asks which of a family of solutions the data supports, and the answer is that it supports all of them and something outside the data has to choose. That is non-uniqueness of a different kind — not of a factorisation of a fixed object, but of the object itself — and every rule for resolving it is a heuristic scored against a truth that exists only because the problem was constructed.

The spectra field asks when an eigenvector is determined, and the answer is that it is determined to the extent that its eigenvalue is separated: an invariant subspace is well conditioned and the individual vectors inside it are not. That is the closest analogue, because it is also a statement that a set is determined and its basis is not.

Against both, the Kruskal case is unusually favourable: a checkable sufficient condition, generically true, with the conclusion that the parameters themselves are determined. It is the only place in this collection where a decomposition’s factors are the answer rather than a coordinate system for it.

Two filters on one sum, λ = 0.001The weight each term of the solution is given, against its index. Truncation is a step: one for the first 32 terms and zero after. Tikhonov is σ²/(σ² + λ²), which falls smoothly through the same place. The unregularised solution is the constant one, which is why it divides noise by a σ of 1.7·10⁻¹³.081624324048566400.250.50.751index kfilter factor fₖno regularisation: fₖ = 1truncationTikhonovthe same sum, three weightsTikhonov, relative error0.16truncation, relative error0.13no filter at all5.5·10⁸both filters are one expression with a different weightfₖ = 1 is the catastrophe
Fig. 15 The regularisation field’s version, from the essay that prices it: a family of answers the data cannot choose between.
What a perturbation of 10⁻⁶ moves, against the gap it is applied acrossThree curves against the gap between two eigenvalues, both axes logarithmic. Two are flat; the third rises steeply as the gap closes and then levels off.10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻⁸10⁻⁵10⁻²gap between the two eigenvalueshow far it movedthe eigenvectorsthe eigenvaluestheir plane‖E‖ / gapone perturbation, three answerseigenvalue shift, spread over the sweep1plane angle, spread over the sweep1eigenvector angle, spread1.6·10⁵the dashed line is Davis–Kahan's ‖E‖/gaptwo of the three never noticed
Fig. 16 The spectra field’s version, from the essay that measures it: a subspace that is determined and vectors inside it that are not.

The refusal

The claim under test is the one the theorem is most often quoted as saying: that a CP decomposition is unique, full stop, and therefore its factors can be read as components.

Six fits are run on the 2 × 2 × 2 rank-three tensor, where the k-ranks sum to six against a required eight. All six reach the tensor to the rounding level. The assertion that every pair agrees to 0.99 is fed the worst pair, which is 0.021, and fails.

What the refusal protects is not the theorem but the conditional. A gate that only checked the wide case would confirm uniqueness on the tensors where it holds and say nothing about the ones where it does not — and the failure mode this field actually has is a practitioner quoting the theorem for a shape it does not cover.

The file’s other refusals cover the neighbours. One is fed a swamp run and required to refuse the claim that its terms stay bounded. The other is fed a benign run and required to refuse the claim that alternating least squares can go uphill, which keeps the monotonicity measurement honest.

At other settings

How much two runs of the same fit agree about the factors, from 4 starting points eachEvery run here reaches its target to the rounding level — 3·10⁻¹³, 3.59·10⁻¹² and 2.39·10⁻¹⁵ at worst — so all three are successful factorisations. The bar is the worst agreement between any two of them about the *factors*, matched over permutations and scalings, which is exactly the freedom the uniqueness theorem allows. Kruskal's condition k_A + k_B + k_C ≥ 2r + 2 holds for the first (9 ≥ 8) and fails for the second (6 < 8), and the bars are 1.0000 and 0.1026. The matrix is the comparison the whole thing rests on: AB = (AM)(M⁻¹B) for every invertible M, so its runs agree to 0.1089 and its factors mean nothing on their own.6 × 6 × 6, rank 3 · 9 ≥ 81.00002 × 2 × 2, rank 3 · 6 < 80.10266 × 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 3.6·10⁻¹²every run factorises to 2.4·10⁻¹⁵ and none agrees with anotherthe only thing that improvestensor, Kruskal holds1tensor, Kruskal fails0.1matrix0.11worst residual3.6·10⁻¹²three successful fitsone recoverable answer
Fig. 17 Four starting points, between the settings the argument is made at.
How much two runs of the same fit agree about the factors, from 8 starting points eachEvery run here reaches its target to the rounding level — 3·10⁻¹³, 1.16·10⁻¹¹ and 2.39·10⁻¹⁵ at worst — so all three are successful factorisations. The bar is the worst agreement between any two of them about the *factors*, matched over permutations and scalings, which is exactly the freedom the uniqueness theorem allows. Kruskal's condition k_A + k_B + k_C ≥ 2r + 2 holds for the first (9 ≥ 8) and fails for the second (6 < 8), and the bars are 1.0000 and 0.0207. The matrix is the comparison the whole thing rests on: AB = (AM)(M⁻¹B) for every invertible M, so its runs agree to 0.0432 and its factors mean nothing on their own.6 × 6 × 6, rank 3 · 9 ≥ 81.00002 × 2 × 2, rank 3 · 6 < 80.02076 × 6 matrix, rank 3 · no condition0.0432worst 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.043worst residual1.2·10⁻¹¹three successful fitsone recoverable answer
Fig. 18 And eight, where the two lower bars have nearly settled.
Alternating least squares on a tensor with a rank-two answer and on one without, over 200 sweepsThe steeply falling curve is a rank-three fit to a tensor built from rank-three factors: it reaches 9.74·10⁻¹⁵ in 58 sweeps and its largest term does not move — 12.202 at sweep twenty and 12.202 at the end. The other is a rank-two fit to the border-rank tensor, whose error goes from 0.00677 to 0.00616 and has not finished, while the rising curve is its largest term: 4.698 to 4.918, a factor of 1.05. Fitted over 149 points, the error falls as the 2.07 power of the term size — a better path than the explicit sequence's 1/n, and still one that leaves the set rather than converging inside it.110¹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.0062swamp term4.9term growth1benign error9.7·10⁻¹⁵benign term growth1the error alone cannot tellthe size of the terms can
Fig. 19 The benign run alone, which is what every fit on this page is doing before the congruence is taken.
Along a sequence of exactly rank-two tensors: the step's condition number, and what a fit from a random start achievesEvery A_n on this sequence *is* a rank-two tensor and its two rank-one terms are written down, so nothing here is about existence. The rising curve is the condition number of the r × r system each alternating sweep solves, which on this sequence has a closed form in n whose asymptote is 2n² — the marks are measured and the dashed line is that closed form, agreeing to 1.1·10⁻¹¹. The lower marks are what a three-hundred-sweep fit from a random start returns: 2.1·10⁻⁴ at n = 2 rising to 0.0118 at n = 1024. Started at the answer instead, the same code stays within 9.2·10⁻⁹ of it at every n — not the rounding level, because the drift from an exact start is itself about κ times the unit roundoff, but nine orders below what a random start reaches. That is the control that says the failure is the conditioning and not the implementation. A tensor away from the boundary conditions its step at 6.03.110¹10²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 = 10242.1·10⁶its closed form2.1·10⁶cosine of the terms1from a random start0.012from the answer9.2·10⁻⁹the answer existsand cannot be found
Fig. 20 The conditioning followed further along the degenerate sequence.
The share of random 2 × 2 × 2 tensors with real rank two, against the number drawn, and π/4Each draw is eight independent standard normal entries and its rank is decided exactly, by the sign of the hyperdeterminant, with no iteration involved. Over 19,953 draws 15,705 have rank two — a share of 0.7871 against the exact value π/4 = 0.7854, inside 0.6 standard errors. The band is ±2 of them. A random matrix has one typical rank; this is the picture of a random object having two, each with a probability that is a number rather than an experiment.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
Fig. 21 How often a random target of the narrow shape has rank three at all, which is when the condition becomes relevant.
The share of a HOSVD core's energy on its superdiagonal, by family, at rank 6A matrix SVD hands over orthonormal factors and a diagonal middle at the same time. For three indices they come apart, and this is the half that does not survive. Every core here is all-orthogonal — the largest inner product between two slices perpendicular to a mode, relative to the core's own energy, is 3.5·10⁻¹⁶ — and none of them is diagonal. The bars are the fraction of the squared norm carried by the 6 entries on the superdiagonal: smooth 97.7%, hilbert 94.5%, wave 26.6%, noise 0.4%. Keeping only those entries costs 0.152, 0.235, 0.857, 0.998 in relative error against the full core's 7.94·10⁻⁶, 1.77·10⁻⁶, 1.34·10⁻¹⁵, 0.842.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
Fig. 22 The property the subspace formats keep instead, from three essays back.
How far |r_nn| sits above σ_min on Kahan's matrix, against the size and the parameter3 curves of |r_nn| ÷ σ_min against n, one per Kahan parameter. Every curve rises without turning over, reaching 4·10⁶ at n = 40, c = 0.5. Column pivoting makes no interchange at any point on any of them, so the failure is not a poor choice — there is nothing to choose.815222936110¹10²10³10⁴10⁵10⁶10⁷10⁸size of the matrix|r_nn| ÷ σ_minthe two agreec = 0.2c = 0.35c = 0.5no ceilingratio at n = 1021ratio at n = 404·10⁶interchanges, anywhere0the greedy rule never had a choiceand the gap grows with every row
Fig. 23 The spectra field’s example of a rank verdict that is a decision rather than a fact, for comparison.
Classical and modified Gram–Schmidt: the same subtraction, in a different orderTwo panels of pseudocode differing in one argument, with the resulting pairwise dot products of the computed columns listed beneath each.for each previous column i, subtract the projection of column j onto qᵢclassicalr[i][j] = qᵢ · a[j] ↑ the ORIGINAL columnv = v − r[i][j] · qᵢthe three worst |qᵢ · qⱼ|:columns 7 and 8: 1columns 6 and 8: 0.13columns 6 and 7: 0.13modifiedr[i][j] = qᵢ · v ↑ what is LEFT of itv = v − r[i][j] · qᵢthe three worst |qᵢ · qⱼ|:columns 1 and 8: 4.4·10⁻⁷columns 2 and 8: 2.7·10⁻⁷columns 3 and 8: 2.4·10⁻⁸The two R factors agree to 1.2·10⁻⁶ relative. The two Q factors do not.the 8×8 Hilbert matrixone word, eight orders
Fig. 24 And an orthogonality measured pair by pair, which is the shape the congruence score borrows.
Numbers stored against the number of indices, at n = 20 and rank 4: the tensor, its core, and a trainThe tensor is n^d, which at d = 20 is 1.05·10²⁶. A Tucker representation of it is r^d + d·n·r — the core is still exponential in d, so at rank 4 it is 1.1·10¹², smaller than the tensor by 9.54·10¹³ and still unstorable. A train is (d − 2)nr² + 2nr, which is 5,920 — linear in d. The three lines are the field's whole argument: fixing the definition of the decomposition does not fix the size of what it returns, and the second fix is the same projection cut in a different place.15913172110¹10⁶10¹¹10¹⁶10²¹10²⁶number of indicesnumbers storedthe tensor: n^dthe core: r^d + dnrthe train: (d − 2)nr² + 2nrthe curse, movedentries at d = 2010²⁶core1.1·10¹²train5920core ⁄ train1.9·10⁸entries ⁄ core9.5·10¹³the definition is repairedthe size is not
Fig. 25 What the alternative costs in numbers, for the reader deciding between the two halves of the trade.
Entries against numbers stored, for sin of a sum on 6 points a side, as indices are addedThe upper line is the tensor: 6^d entries, which is a straight line on a logarithmic axis and reaches 46,656 at d = 6. The lower one is the train, which for this family is 4n(d − 1) exactly — 24, 48, 72, 96, 120 — a straight line on a *linear* axis and therefore a logarithm on this one. Its fitted slope against d is 24.0, which is 4n. The two are the same object to within 1.39·10⁻¹⁵, so nothing has been given up: the ratio at d = 6 is 389, and it grows by a factor of n with every index added.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
Fig. 26 The storage the other half of the trade buys, which is what a code gives up interpretability for.
A rank-two sequence approaching a rank-three tensor: the residual falls like 1/n and the terms grow like nA_n = n(e₁ + e₂/n)⊗³ − n·e₁⊗³ has rank two for every n and converges to a tensor of rank three. The falling curve is ‖A_n − A‖, which is √(3/n² + 1/n⁴) exactly and reaches 0.00169 at n = 1024; the rising one is the norm of the larger of its two rank-one terms, 1024. Their product runs 2.519, 1.917, 1.777 … 1.73205, descending onto √3 = 1.73205. So getting one digit closer costs a factor of ten in the size of the pieces, for ever, and the infimum of the distance is zero while no rank-two tensor attains it.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
Fig. 27 And the geometry that makes the trade necessary, from the field’s third essay.
The three unfoldings of a 10 × 11 × 12 hilbert tensor, and the singular values of eachA tensor has one matrix per index — put that index on the rows and every other index down the columns — and each of those matrices has an ordinary rank. Here they are 8, 8, 8 at a relative tolerance of 10⁻⁸, from a tensor of 1320 entries whose modes are of different lengths. Nothing requires the three numbers to agree, and nothing requires any of them to be the tensor's own rank: they are three different matrices built from one array. The leading singular values are 3.2, 3.2, 3.2, each normalised to its own mode below.02468101210⁻¹⁶10⁻¹²10⁻⁸10⁻⁴1index of the singular valueσ ⁄ σ₁the tolerance the ranks are read atmode 1 · rank 8mode 2 · rank 8mode 3 · rank 8hilbert: three matrices, one arrayentries1320mode-1 rank8mode-2 rank8mode-3 rank8‖T‖3.3three ranksand none of them is the tensor's
Fig. 28 Three ordinary spectra, which is where every k-rank on this page is read from.

Where this goes next

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. 12345678910⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1rank k of the approximation‖A − Aₖ‖measured, 2-normσₖ₊₁, from theorymeasured, Frobeniusthe first two agreeto 4.3·10⁻⁹worst |‖A−Aₖ‖₂ − σₖ₊₁| / σₖ₊₁4.3·10⁻⁹worst Frobenius discrepancy4.3·10⁻⁹κ = 10⁹; 30 random rank-3 matrices, none closerthe error is σₖ₊₁ The best approximation there is The error of the best rank-k approximation is not bounded by the next singular value. It is equal to it. That is an unusually sharp theorem, and it makes the theorem itself usable as an independent check on the computation. 1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision Rank is a decision A floating-point matrix does not have a rank. It has a spectrum of singular values, and somewhere in that spectrum is a place where the values stop being signal and start being noise. Deciding where is a judgement, and the evidence for it is a gap.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Alternating least squaresCP decompositionKruskal's conditionLow-rank approximationOrthogonalitySwampTensor rankTruncated svdUnfoldingUniqueness